XXXIII OM - I - Zadanie 4

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

\[<br />
2^n\binom{n}{0} + 2^{n-1}\binom{n+1}{1} + 2^{n-2}\binom{n+2}{2} + \ldots + \binom{2n}{n} = 2^{2n}.<br />
\]

Rozwiązanie

Przeprowadzimy dowód indukcyjny.

Dla $ n = 1 $ lewa strona przyjmuje wartość $ 2 + 2 = 4 $, prawa strona również przyjmuje wartość $ 4 $.

Załóżmy, że dla pewnego naturalnego $ n $ zachodzi nierówność

\[<br />
2^{n} \binom{n}{0} +<br />
2^{n-1} \binom{n+1}{1} +<br />
2^{n-2} \binom{n+2}{2} +<br />
\ldots + \binom{2n}{n} = 2^{2n}.<br />
\]

Udowodnimy, że

\[<br />
2^{n+1} \binom{n+1}{0} + 2^{n} \binom{n+2}{1} + 2^{n-2} \binom{n+3}{2} + \ldots + \binom{2n+2}{n+1} = 2^{2n+2}.<br />
\]

Niech

\[x = 2^{n+1} \binom{n+1}{0} + 2^{n} \binom{n+2}{1} + 2^{n-1} \binom{n+3}{3} +<br />
\ldots + \binom{2n+2}{n+1}.<br />
\]

Na podstawie tożsamości $ \binom{m+1}{k+1}= \binom{m}{k+1} + \binom{m}{k} $, którą możemy uzasadnić przez bezpośredni rachunek:

\[<br />
\begin{split}<br />
& \binom{m}{k+1} + \binom{m}{k} = \frac{m!}{(k+1)!(m-k-1)!} +<br />
\frac{m!}{k!(m-k)!} =<br />
\frac{m!(m-k)+m!(k+1)}{(k+1)!(m-k)} =\\<br />
& =\frac{m!(m+1)}{(k+1)!(m-k)!}=<br />
 \frac{(m+1)!}{(k+1)!((m+1)-(k+1)!)}=\ \binom{m+1}{k+1},<br />
\end{split}<br />
\]

obliczamy

\[<br />
\begin{split}<br />
 x & = 2^{n+1} \binom{n+1}{0} + 2^{n} \binom{n+2}{1} + 2^{n-1} \binom{n+3}{2} + \ldots + \binom{2n+2}{n+1}=\\<br />
& = 2^{n+1} + 2^n \binom{n+1}{0} + 2^{n} \binom{n+1}{1} + 2^{n-1} \binom{n+2}{1} 2^{n-1} \binom{n+2}{2} + \\<br />
&+ \ldots +  \binom{2n+1}{n} + \binom{2n+1}{n+1} = 2^{n+1} + \left[ 2^n \binom{n+1}{0} + 2^{n-1} \binom{n+2}{1} + \right.\\<br />
& \left. + \ldots + \binom{2n+1}{n} \right] + 2^{n} \binom{n+1}{1} + 2^{n-1} \binom{n+2}{2}+ \ldots +  \binom{2n+1}{n+1} =\\<br />
& = 2^{n+1} + \frac{1}{2} \left[ 2^{n+1} \binom{n+1}{0} + 2^{n} \binom{n+2}{1} + \ldots + 2 \binom{2n+1}{n} + \binom{2n+2}{n+1} \right] +\\<br />
& - \frac{1}{2} \binom{2n+2}{n+1} + 2 \left[ 2^{n} \binom{n}{0} + 2^{n-1} \binom{n+1}{1}+ 2^{n-2} \binom{n+2}{2} + \ldots +  \binom{2n}{n}\right] +\\<br />
& -2^{n+1} + \binom{2n+1}{n+1} = \frac{1}{2}x - \frac{1}{2} \binom{2n+2}{n+1} + 2 \cdot 2^{2n} + \binom{2n+1}{n+1}.<br />
\end{split}<br />
\]

Otrzymujemy stąd równanie

\[<br />
\frac{1}{2}x = 2^{2n+1} - \frac{1}{2} \binom{2n+2}{n+1} + \binom{2n+1}{n+1}.<br />
\]

Ponieważ

\[<br />
 \frac{1}{2} \binom{2n+2}{n+1} = \frac{1}{2} \frac{(2n+2)!}{(n+1)!(n+1)!}=<br />
\frac{(2n+1)!2(n+1)}{2(n+1)!(n+1)!} = \frac{(2n+1)!}{(n+1)!n!} = \binom{2n+1}{n+1}<br />
\]

więc powyższe równanie przyjmuje postać

\[<br />
\frac{1}{2} x = 2^{2n+1},<br />
\]

a zatem $ x = 2^{2n+1} $.

Na mocy zasady indukcji matematycznej dana nierówność spełniona jest dla każdego naturalnego $ n $.

Komentarze

Alternatywne rozwiązanie

Wykażemy, że wyrażenie $ \sum_{i=0}^{n} 2 ^{n-i} {n+i \choose i} $ jest równe liczbie podzbiorów zbioru $ X=\{1,2,\ldots,2n\} $, czyli $ 2^{2n} $. Oznaczmy $ S_i=\{1, 2,\ldots,i\} $. Niech funkcja $ f $ każdemu podzbiorowi $ Y $ zbioru $ X $ przyporządkuje największy taki indeks $ k\in\{0,1\ldots,n\} $, że moc co najmniej jednego ze zbiorów $ Y \cap S_{n+k} $ lub $ (S_{2n}\backslash Y) \cap S_{n+k} $ wynosi $ n $. Mówiąc obrazowo, szukamy największego $ k\leq n $ takiego, że spośród liczb $ 1,2,\ldots , n+k $ dokładnie $ n $ należy do $ Y $ lub dokładnie $ n $ z nich do niego nie należy. Funkcja ta jest w oczywisty sposób dobrze określona i tak dalej :P Prosto wykazać, że moc rodziny $ f^{-1}(k) $ wynosi $ 2^{n-k} {n+k \choose k} $, ponieważ każdy zbiór $ Y'' $ z tej rodziny możemy rozpisać na sumę dowolnego podzbioru zbioru $ S_{2n}\backslash S_{n+k+1} $ (jest ich $ 2^{n-k-1} $) oraz $ k $ lub $ n $ - elementowego podzbioru zbioru $ S_{n+k} $ (liczba $ n+k+1 $ - o ile należy do $ X $ - musi należeć do $ Y'' $ jeżeli $ \overline{\overline{Y''  \cap S_{n+k}}}=n $ oraz nie może należeć gdy $ \overline{\overline{Y''  \cap S_{n+k}}}=k $ ). To oznacza, że $ \overline{\overline{f^{-1}(k)}}=2^{n+k-1}{n+k\choose k}+2^{n+k-1}{n+k\choose n}=2^{n-k}{n+k\choose k} $.
Podzbiory o innej postaci nie pozwolą nam uzyskać wartości $ k $ dla funkcji $ f $. Ponieważ zbiorem wartości funkcji $ f $ jest zbiór $ \{0,1,\ldots,n\} $ to liczba podzbiorów $ X $ będzie równa $ 2^{2n}=\sum_{k=0}^n\overline{\overline{f^{-1}(k)}}=\sum_{k=0}^n 2^{n-k}{n+k\choose k} $, co kończy dowód.

PS. Wybaczcie, że w kilku miejscach trochę zamachałem rękami, ale rozpisywanie tego dokładnie zajęłoby mi chyba z pół godziny :P

Dodaj nową odpowiedź