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

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź