somme sui binomiali

[andrea91]

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 $.

[FeddyStra]

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} $.

Supponiamo che tu debba estrarre dalla serie $ \sum_{k} a_k $ i termini con indice congruo a $ i\pmod m $. Sfruttando la relazione sopra citata, si ha che

• $ \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 $.

Nel nostro caso,

• $ \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 $.

La sommatoria può essere riscritta come

• $ \displaystyle \frac{2^n}{m} + \frac1m \sum_{j=1}^{m-1} \omega_j^{-i}(1+\omega_j)^n $.

Cerchiamo ora di stimare il valore assoluto della sommatoria:

• $ \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 $.

Poniamo $ \lambda=|1+\omega_1| $. Si ha chiaramente $ \lambda<2 $, quindi segue che

• $ \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 $.

Ciò significa che, quando $ n $ cresce, $ 2^n/m $ fornisce un'approssimazione sempre migliore per la sommatoria.

[andrea91]

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?

[andrea91]

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?

[FeddyStra]

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?

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.

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?

$ \omega_j $ e $ \omega_{m-j} $ sono coniugati.

[andrea91]

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 $.

hai ragione, era una domanda idiota avevo provato 2 o 3 casi ma mi sa che avevo sempre scelto m=4

$ \omega_j $ e $ \omega_{m-j} $ sono coniugati.

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.
Tra l'alrto, ma forse ora rompo troppo le scatole, è anche razionale

[FeddyStra]

Tra l'alrto, ma forse ora rompo troppo le scatole, è anche razionale

Meglio ancora: è intero. Lo puoi vedere a partire dall'identità
$ \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 $.