XXVII OM - I - Zadanie 2

Zawody matematyczne:

XXVII OM, 1975-1976

Etap:

Dowieść, że

$ \sum_{i=0}^{24} \binom{100}{4i+1} = 2^{98}. $

Rozwiązanie

Udowodnimy, że dla każdej liczby naturalnej $n$ zachodzi wzór

$ (1) \qquad \sum_{i=0}^{n-1} \binom{4n}{4i+1} = 2^{4n-2} $

Przy $n = 25$ wynika zeń wzór podany w zadaniu. Na mocy wzoru dwumianowego mamy

$ 2^{4n-1} = (1+i)^{4n-1} = \sum_{j=0}^{4n-1} \binom{4n-1}{j}. $

Grupując kolejno składniki otrzymanej sumy parami i wykorzystując wzór

$ \binom{m+1}{k} = \binom{m}{k} + \binom{m}{k-1}, \ \textrm{gdzie} \ 1 \leq k \leq m, $

stwierdzamy, że

$ 2^{4n-1} = \sum_{i=0}^{2n-1} \left[ \binom{4n-1}{2i} + \binom{4n-1}{2i+1} \right] = \sum_{i=0}^{2n-1} \binom{4n}{2i+1}. $

Tę ostatnią sumę zapisujemy w postaci sumy dwóch sum. Składniki pierwszej odpowiadają parzystym wartościom $i$ , $i = 2k$ , gdzie $0 \leq k \leq n - 1$ ; składniki drugiej - nieparzystym wartościom $i$ , $i = 2k + 1$ , gdzie $0 \leq k \leq n - 1$ . Mamy więc

$ (2) \qquad 2^{4n-1} = \sum_{k=0}^{n-1} \binom{4n}{4n+1} + \sum_{k=0}^{n-1} \binom{4n}{4n+3}. $

Ponieważ $\displaystyle \binom{m}{r} = \binom{m}{m-r}$ dla $0 \leq r \leq m$ , więc $\displaystyle \binom{4n}{4n+3} = \binom{4n}{4(n-k-1)+1}$ . Przy tym dla $0 \leq k \leq n-1$ mamy $0 \leq n-1-k \leq n-1$ . Wobec tego ostatnia suma po prawej stronie wzoru (2) jest równa

$ \sum_{k=0}^{n-1} \binom{4n}{4(n-1-k)+1} = \sum_{s=0}^{n-1} \binom{4n}{4s+1}. $

Zatem z (2) otrzymujemy

$ 2^{4n-1} = 2\sum_{k=0}^{n-1} \binom{4n}{4k+1} $

i stąd - wzór (1).