XXXIII OM - I - Zadanie 4

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

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

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

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ść

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

Udowodnimy, że

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

Niech

$x = 2^{n+1} \binom{n+1}{0} + 2^{n} \binom{n+2}{1} + 2^{n-1} \binom{n+3}{3} + \ldots + \binom{2n+2}{n+1}. $

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:

$ \begin{split} & \binom{m}{k+1} + \binom{m}{k} = \frac{m!}{(k+1)!(m-k-1)!} + \frac{m!}{k!(m-k)!} = \frac{m!(m-k)+m!(k+1)}{(k+1)!(m-k)} =\\ & =\frac{m!(m+1)}{(k+1)!(m-k)!}= \frac{(m+1)!}{(k+1)!((m+1)-(k+1)!)}=\ \binom{m+1}{k+1}, \end{split} $

obliczamy

$ \begin{split} 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}=\\ & = 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} + \\ &+ \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.\\ & \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} =\\ & = 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] +\\ & - \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] +\\ & -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}. \end{split} $

Otrzymujemy stąd równanie

$ \frac{1}{2}x = 2^{2n+1} - \frac{1}{2} \binom{2n+2}{n+1} + \binom{2n+1}{n+1}. $

Ponieważ

$ \frac{1}{2} \binom{2n+2}{n+1} = \frac{1}{2} \frac{(2n+2)!}{(n+1)!(n+1)!}= \frac{(2n+1)!2(n+1)}{2(n+1)!(n+1)!} = \frac{(2n+1)!}{(n+1)!n!} = \binom{2n+1}{n+1} $

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

$ \frac{1}{2} x = 2^{2n+1}, $

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

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