XXXI - III - Zadanie 6

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

\[<br />
\sum_{s=n}^{2n} 2^{2n-s} \binom{s}{n} = 2^{2n}<br />
\]

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

\[<br />
(1) \qquad \sum_{s=n}^{2n} 2^{-s} \binom{s}{n} =1.<br />
\]

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

\[<br />
(2) \qquad<br />
\binom{r}{s+1} = \binom{r+1}{s+1} - \binom{r}{s}<br />
\]

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

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

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

\[<br />
\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.<br />
\]

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

\[<br />
(3) \qquad<br />
S= \sum_{s=n+1}^{2(n+1)} 2^{-s} \binom{s}{n+1}.<br />
\]

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

\[<br />
\begin{split}<br />
S & = \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s}{n+1}=<br />
 \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s+1}{n+1} -<br />
 \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s}{n}=\\<br />
&= 2 \cdot \sum_{s=n+1}^{2n+2} 2^{-s-1} \binom{s+1}{n+1} -<br />
 \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s}{n} =<br />
2 \cdot \sum_{s=n+2}^{2n+3} 2^{-s} \binom{s}{n+1} +\\<br />
&\quad - \sum_{s=n}^{2n} 2^{-s} \binom{s}{n}+<br />
2^{-n} \binom{n}{n} - 2^{-2n-1} \binom{2n+1}{n}<br />
 - 2^{-2n-2} \binom{2n+2}{n}.<br />
\end{split}<br />
\]

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

\[<br />
\begin{split}<br />
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]=\\<br />
& = 2 \cdot \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s}{n+1} -<br />
2 \cdot 2^{-n-1} \binom{n+1}{n+1} + 2 \cdot 2^{-2n-3} \binom{2n+3}{n+1} +\\<br />
&\quad- 1 + 2^{-n}  - 2^{-2n-2} \left[ \binom{2n+2}{n} + 2 \binom{2n+1}{n} \right] =<br />
2S - 2^{-n} + \\<br />
&\quad + 2^{-2n-2} \left[ \binom{2n+3}{n+1} - \binom{2n+2}{n} - 2\cdot \binom{2n+1}{n} \right] -1 + 2^{-n}.<br />
\end{split}<br />
\]

Wobec tego

\[<br />
S = 2S - 1 + 2^{-2n-2} \left[ \binom{2n+3}{n+1} - \binom{2n+2}{n} - 2\cdot \binom{2n+1}{n} \right],<br />
\]

a więc

\[<br />
S = 1 - 2^{-2n-2} \left[ \binom{2n+3}{n+1} - \binom{2n+2}{n} - 2\cdot \binom{2n+1}{n} \right].<br />
\]

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

Komentarze

Dodaj nową odpowiedź