si sa che
$ \sum_{k \equiv 0 (mod)2}\binom{n}{k}=\sum_{k \equiv 1 (mod)2}\binom{n}{k}=2^{n-1} $.
mi chiedevo se comunque fissati $ n, m, i $ con $ m|n $ si può calcolare
$ \sum_{k \equiv i (mod)m}\binom{n}{k} $.
inoltre volevo chiedere se ed in quale senso si potrebbe dire che quella quantità (almeno per qualche valore particolare di i in funzione di m) è circa $ 2^{n}/m $.
somme sui binomiali
Ti suggerisco un'idea abbastanza generale che si applica quando vuoi "estrarre" alcuni termini di una serie. Chiama $ \omega_1,\dots,\omega_m=1 $ le radici $ m $-esime dell'unità. La relazione importante di cui si fa uso è
- $ \displaystyle \sum_{j=1}^{m} \omega_j^k = \begin{cases} 0 & \text{se $m \nmid k$} \\ m & \text{se $m \mid k$} \end{cases} $.
- $ \displaystyle \frac1m \sum_{j=1}^{m}\sum_{k} a_k\omega_j^{k-i} = \frac1m \sum_{k} \left( a_k \sum_{j=1}^{m} \omega_j^{k-i} \right) = \frac1m \sum_{m \mid k-i} ma_k = \sum_{k \equiv i \bmod m} a_k $.
- $ \displaystyle \sum_{k \equiv i \bmod m} \binom{n}{k} = \frac1m \sum_{j=1}^{m}\sum_{k=0}^{n} \binom{n}{k}\omega_j^{k-i} = \frac1m \sum_{j=1}^{m} \omega_j^{-i}(1+\omega_j)^n $.
- $ \displaystyle \frac{2^n}{m} + \frac1m \sum_{j=1}^{m-1} \omega_j^{-i}(1+\omega_j)^n $.
- $ \displaystyle \left| \frac1m \sum_{j=1}^{m-1} \omega_j^{-i}(1+\omega_j)^n \right| \le \frac1m \sum_{j=1}^{m-1} \left| \omega_j^{-i}(1+\omega_j)^n \right| = \frac1m \sum_{j=1}^{m-1} |1+\omega_j|^n \le $
$ \displaystyle \le \frac1m \sum_{j=1}^{m-1} |1+\omega_1|^n = \frac{m-1}{m}|1+\omega_1|^n < |1+\omega_1|^n $.
- $ \displaystyle \lim_{n \to \infty} \left| \sum_{k \equiv i \bmod m} \binom{n}{k} - \frac{2^n}{m} \right| / \left( \frac{2^n}{m} \right) \le \lim_{n\to\infty} m \frac{\lambda^n}{2^n} = 0 $.
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
re: somme sui binomiali
MAMMA MIA!!!!!! davvero bella, complimenti! molto chiara e tra l'altro molto eusariente, considerato ciò che avevo chiesto...
una curiosità: ma una diavoleria del genere ti è venuta in mente sul momento oppure l'hai letta da qualche parte? ma questi trucchi si imparano da qualche parte a scuola oppure all'università?
domanda bonus dato che sei stato così bravo: fissati comunque $ m, n $ come prima esiste sempre un $ i $ per cui per cui quella serie è esattamente un m-esimo del totale?
una curiosità: ma una diavoleria del genere ti è venuta in mente sul momento oppure l'hai letta da qualche parte? ma questi trucchi si imparano da qualche parte a scuola oppure all'università?
domanda bonus dato che sei stato così bravo: fissati comunque $ m, n $ come prima esiste sempre un $ i $ per cui per cui quella serie è esattamente un m-esimo del totale?
Ultima modifica di andrea91 il 21 set 2009, 15:48, modificato 1 volta in totale.
Innanzi tutto, un $ m $-esimo del totale è intero se e solo se $ m $ è una potenza di $ 2 $ minore o uguale a $ 2^n $ (che è il totale). In generale, quindi, la risposta è no. Un caso poco interessante è quando $ m=2^n $. Posto infatti $ i=0 $ si ha che la somma in questione vale proprio $ 2^n/m=1 $. Un caso un po' più degno di nota è $ m=4 $. Si verifica infatti che per tutti i valori pari di $ n $ esiste un siffatto $ i $, il quale è $ 0 $ o $ 1 $ a seconda della parità di $ n/2 $. Non dovrebbe esserti difficile da dimostrare.andrea91 ha scritto:domanda bonus dato che sei stato così bravo: fissati comunque $ m, n $ come prima esiste sempre un $ i $ per cui per cui quella serie è esattamente un m-esimo del totale?
$ \omega_j $ e $ \omega_{m-j} $ sono coniugati.andrea91 ha scritto:tra l'altro questo siginifica che $ \displaystyle \sum_{j=1}^{m-1} \omega_j^{-i}(1+\omega_j)^n $ è reale: è una banalità che ora non colgo?
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
hai ragione, era una domanda idiota avevo provato 2 o 3 casi ma mi sa che avevo sempre scelto m=4FeddyStra ha scritto:Innanzi tutto, un $ m $-esimo del totale è intero se e solo se $ m $ è una potenza di $ 2 $ minore o uguale a $ 2^n $....Un caso un po' più degno di nota è $ m=4 $.
e quindi in quella somma se c'è l'elemento j c'è anche quello m-j: li sommi e ottieni a 2 a 2 un reale.FeddyStra ha scritto:$ \omega_j $ e $ \omega_{m-j} $ sono coniugati.
Tra l'alrto, ma forse ora rompo troppo le scatole, è anche razionale
Meglio ancora: è intero. Lo puoi vedere a partire dall'identitàandrea91 ha scritto:Tra l'alrto, ma forse ora rompo troppo le scatole, è anche razionale
$ \displaystyle \sum_{k \equiv i \bmod m} \binom{n}{k} = \frac{2^n}{m} + \frac1m \sum_{j=1}^{m-1} \omega_j^{-i}(1+\omega_j)^n $.
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]