LI OM - I - Zadanie 8

Zawody matematyczne:

LI OM, 1999-2000

Etap:

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

$ c(n,0) = c(n,n) = 1\ \textrm{dla każdej liczby}\ n \geq 0, $

$ c(n+1,k) = 2^kc(n,k) + c(n,k-1)\ \textrm{dla}\ n\geq k \geq 1. $

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:

$ f(0) = 1,\ f(m) = (2^1-1)(2^2-1)\cdots(2^m - 1)\ \textrm{dla}\ m\geq 1. $

Niech ponadto

$ a(n,k)=\frac{f(n)}{f(k)f(n-k)}\ \textrm{dla}\ n\geq k\geq 0. $

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

$ \begin{split} 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&\\ \begin{split} &=\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)}=\\ &=f(n)\cdot\frac{2^{k}(2^{n-k+1}-1)+(2^{k}-1)}{f(k)f(n-k+1)}=\\ &=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), \end{split}& \end{split} $

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