LI OM - I - Zadanie 8

Liczby $ c(n,k) $ są określone dla liczb całkowitych nieujemnych $ n\geq k $ w ten sposób, że zachodzą równości:

\[<br />
c(n,0) = c(n,n) = 1\ \textrm{dla każdej liczby}\ n \geq 0,<br />
\]
\[<br />
c(n+1,k) = 2^kc(n,k) + c(n,k-1)\ \textrm{dla}\ n\geq k \geq 1.<br />
\]

Dowieść, że $ c(n,k) = c(n,n-k) $ dla $ n\geq k \geq 0 $.

Rozwiązanie

Niech $ f $ będzie funkcją określoną na zbiorze liczb całkowitych nieujemnych zdefiniowaną wzorami:

\[<br />
f(0) = 1,\ f(m) = (2^1-1)(2^2-1)\cdots(2^m - 1)\ \textrm{dla}\  m\geq 1.<br />
\]

Niech ponadto

\[<br />
a(n,k)=\frac{f(n)}{f(k)f(n-k)}\ \textrm{dla}\ n\geq k\geq 0.<br />
\]

Wówczas $ a(n,k) = a(n,n-k) $. Wykażemy, że $ a(n,k) = c(n,k) $.

Ponieważ warunki dane w treści zadania wyznaczają jednoznacznie liczby $ c(n,k) $, więc wystarczy dowieść, że liczby $ a(n,k) $ spełniają te same warunki.

Oczywiście $ a(n,0) = a(n,n) = 1 $. Ponadto

\[<br />
\begin{split}<br />
2^{k}a(n,k)+a(n,k-1)=\frac{2^{k}f(n)}{f(k)f(n-k)}+\frac{f(n)}{f(k-1)f(n-k+1)}=\qquad&\\<br />
\begin{split}<br />
&=\frac{2^{k}f(n)(2^{n-k+1}-1)}{f(k)f(n-k)(2^{n-k+1}-1)}+\frac{f(n)(2^{k}-1)}{f(k-1)(2^{k}-1)f(n-k+1)}=\\<br />
&=f(n)\cdot\frac{2^{k}(2^{n-k+1}-1)+(2^{k}-1)}{f(k)f(n-k+1)}=\\<br />
&=f(n)\cdot\frac{2^{n+1}-1}{f(k)f(n+1-k)}=\frac{f(n+1)}{f(k)f(n+1-k)}=a(n+1,k),<br />
\end{split}&<br />
\end{split}<br />
\]

co dowodzi, że $ a(n,k) = c(n,k) $.

Komentarze

Dodaj nową odpowiedź