XXXI - III - Zadanie 6

Zawody matematyczne:

XXXI OM, 1979-1980

Etap:

III

Dowieść, że dla każdej liczby naturalnej $n$ zachodzi równość

$ \sum_{s=n}^{2n} 2^{2n-s} \binom{s}{n} = 2^{2n} $

Rozwiązanie

\spos{I} Przeprowadzimy dowód indukcyjny równości otrzymanej z danej równości przez podzielenie obu stron przez $2^{2^n}$ :

$ (1) \qquad \sum_{s=n}^{2n} 2^{-s} \binom{s}{n} =1. $

W dowodzie wykorzystamy następującą własność współczynników dwumianowych.

Lemat. Dla każdych liczb całkowitych $r$ , $s$ spełniających nierówności $0 \leq s \leq r$ jest

$ (2) \qquad \binom{r}{s+1} = \binom{r+1}{s+1} - \binom{r}{s} $

(gdy $s = r$ przyjmujemy $\binom{r}{s+1} = 0$ ).

Dowód lematu. Jeśli $s = r$ , to $\binom{r}{s} =1$ , $\binom{r+1}{s+1} = 1$ , $\binom{r}{s+1}=0$ , więc równość (2) jest oczywiście spełniona. Załóżmy, że $s < r$ .

$ \begin{split} \binom{r+1}{s+1} - \binom{r}{s} &= \frac{(r+1)!}{(s+1)! [(r+1) - (s+1)]!}- \frac{r!}{s! (r-s)!} = \\ & = \frac{(r+1)!}{(s+1)! (r - s)!}- \frac{r!}{s! (r-s)!} = \frac{(r+1)! - r!(s+1)}{(s+1)! (r - s)!} =\\ & = \frac{r! [(r+1) - (s+1)]}{(s+1)! (r - s)!} = \frac{r! (r-s)}{(s+1)! (r - s)!} = \\ & = \frac{r!}{(s+1)! (r - s-1)!} = \binom{r}{s+1}. \end{split} $

Dowód lematu został więc zakończony. Powróćmy do dowodu równości (1).
Dla $n = 1$

$ \sum_{s=1}^2 2^{-s} \binom{s}{1} = 2^{-1} \cdot \binom{1}{1} + 2^{-2} \cdot \binom{2}{1} = \frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 = \frac{1}{2} + \frac{1}{2} = 1. $

Załóżmy, że równość (1) jest spełniona dla pewnej liczby naturalnej $n$ i rozważmy sumę

$ (3) \qquad S= \sum_{s=n+1}^{2(n+1)} 2^{-s} \binom{s}{n+1}. $

Na mocy lematu zastosowanego do współczynnika $\binom{s}{n+1}$ jest

$ \begin{split} S & = \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s}{n+1}= \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s+1}{n+1} - \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s}{n}=\\ &= 2 \cdot \sum_{s=n+1}^{2n+2} 2^{-s-1} \binom{s+1}{n+1} - \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s}{n} = 2 \cdot \sum_{s=n+2}^{2n+3} 2^{-s} \binom{s}{n+1} +\\ &\quad - \sum_{s=n}^{2n} 2^{-s} \binom{s}{n}+ 2^{-n} \binom{n}{n} - 2^{-2n-1} \binom{2n+1}{n} - 2^{-2n-2} \binom{2n+2}{n}. \end{split} $

Ponieważ na mocy założenia indukcyjnego $\sum_{s=n}^{2n} 2^{-s} \binom{s}{n}=1$ , ponadto $\binom{n}{n}=1$ , więc

$ \begin{split} S & = 2 \cdot \sum_{s=n+2}^{2n+3} 2^{-s} \binom{s}{n+1} - 1 + 2^{-n} - 2^{-2n-2} \left[ 2 \binom{2n+1}{n} + \binom{2n+2}{n} \right]=\\ & = 2 \cdot \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s}{n+1} - 2 \cdot 2^{-n-1} \binom{n+1}{n+1} + 2 \cdot 2^{-2n-3} \binom{2n+3}{n+1} +\\ &\quad- 1 + 2^{-n} - 2^{-2n-2} \left[ \binom{2n+2}{n} + 2 \binom{2n+1}{n} \right] = 2S - 2^{-n} + \\ &\quad + 2^{-2n-2} \left[ \binom{2n+3}{n+1} - \binom{2n+2}{n} - 2\cdot \binom{2n+1}{n} \right] -1 + 2^{-n}. \end{split} $

Wobec tego

$ S = 2S - 1 + 2^{-2n-2} \left[ \binom{2n+3}{n+1} - \binom{2n+2}{n} - 2\cdot \binom{2n+1}{n} \right], $

a więc

$ S = 1 - 2^{-2n-2} \left[ \binom{2n+3}{n+1} - \binom{2n+2}{n} - 2\cdot \binom{2n+1}{n} \right]. $

Na mocy lematu $\binom{2n+3}{n+1} - \binom{2n+2}{n} = \binom{2n+2}{n+1}$ , $\binom{2n+2}{n+1} - \binom{2n+1}{n} = \binom{2n+1}{n+1}$ , ponadto
$\binom{2n+1}{n+1} = \binom{2n+1}{n} = \frac{(2n+1)!}{n!(n+1)!}$ , więc wyrażenie występujące w nawiasie kwadratowym w równości (4) jest równe $0$ . Ostatecznie więc $S=1$ . Z założenia indukcyjnego wynikła prawdziwość równości (3). Na mocy zasady indukcji równość (1) jest spełniona dla każdej liczby naturalnej $n$ .