Matematyka.pl

Jak pokazać, że
\(\displaystyle{ F_{2n}= \sum_{k=0}^{n-1} \binom{n}{k}F_{n-k}}\)
Potrzebuje małej wskazówki.

Sorry, ale usunąłem bardzo brzydki szkic bardzo nieeleganckiego rozwiązania indukcyjnego.

Pokażę, jak się z tym można uporać za pomocą funkcji tworzących. Ładne to nie jest, ale już chyba lepsze już niż bezpośrednia indukcja.

Fakt: dla \(\displaystyle{ |x|<1}\) mamy \(\displaystyle{ \sum_{n=k}^{ \infty } \frac{n!}{(n-k)!}x^{n-k}= \frac{k!}{(1-x)^{k+1}}}\)
Dowód faktu: indukcja, różniczkujemy szereg potęgowy wyraz po wyrazie. Startujemy od
\(\displaystyle{ \sum_{n=0}^{ \infty }x^n=\frac 1 {1-x}}\)

Fakt nr 2: funkcją tworzącą ciągu Fibonacciego \(\displaystyle{ F_n}\) jest \(\displaystyle{ G(x)= \frac{x}{1-x-x^2}}\)
Dowód faktu nr 2:
\(\displaystyle{ G(x)= \sum_{n=0}^{ \infty }F_n x^n=F_0+F_1 x+ \sum_{n=2}^{ \infty }F_n x^n=\\=F_0+F_1 x+ \sum_{n=2}^{ \infty }(F_{n-1}+F_{n-2})x^n=\\=x+xG(x)+x^2G(x)}\)
i mamy równanie \(\displaystyle{ G(x)(1-x-x^2)=x}\)

Teraz zmienimy (odwrócimy) kolejność sumowania:
\(\displaystyle{ \sum_{k=0}^{n-1} \binom{n}{k}F_{n-k}= \sum_{k=1}^{n}{n \choose n-k}F_k= \sum_{k=1}^{n}{n \choose k}F_k}\)
Oczywiście możemy też sumować od zera, bo \(\displaystyle{ F_0=0}\).

OK, policzymy funkcję tworzącą ciągu \(\displaystyle{ a_n=\sum_{k=1}^{n}{n \choose k}F_k}\):
\(\displaystyle{ \sum_{n=0}^{ \infty }x^n a_n= \\=\sum_{n=0}^{ \infty }x^n\left( \sum_{k=0}^{n}{n \choose k}F_k \right)=\\= \sum_{n=0}^{ \infty } \sum_{k=0}^{n}{n \choose k}F_k x^n=\\= \sum_{k=0}^{ \infty } \sum_{n=k}^{ \infty } {n \choose k}F_k x^n=\\= \sum_{k=0}^{ \infty } \frac{F_k}{k!}x^k \sum_{n=k}^{ \infty } \frac{n!}{(n-k)!}x^{n-k}=\\= \frac{1}{1-x} \sum_{k=0}^{ \infty }\left( \frac{x}{1-x} \right)^k F_k=\\= \frac{1}{1-x} \cdot \frac{ \frac{x}{1-x} }{1- \frac{x}{1-x}-\left( \frac{x}{1-x} \right)^2 }=\\= \frac{x}{x^2-3x+1}}\)
Uff...
Pozostaje znaleźć funkcję tworzącą ciągu \(\displaystyle{ F_{2n}}\) i przekonać się, że jest ona tożsama z funkcją tworzącą ciągu \(\displaystyle{ a_n}\). Otóż:
\(\displaystyle{ \sum_{n=0}^{ \infty }(F_{2n}+F_{2n+1})x^n= \sum_{n=0}^{ \infty }F_{2n+2}x^n\\ \sum_{n=0}^{ \infty }(F_{2n+1}+F_{2n+2})x^n= \sum_{n=0}^{ \infty }F_{2n+3}x^n}\)
A zatem oznaczając \(\displaystyle{ s_1(x)= \sum_{n=0}^{ \infty }F_{2n}x^n , s_2(x)= \sum_{n=0}^{ \infty }F_{2n+1}x^n}\), mamy:
\(\displaystyle{ \begin{cases}s_1(x)+s_2(x)=\frac 1 xs_1(x) \\ s_2(x)+ \frac{1}{x}s_1(x)= \frac{1}{x}s_2(x)-\frac 1 x \end{cases}}\)

Po rozwiązaniu tego układu równań otrzymujemy \(\displaystyle{ s_1(x)= \frac{x}{x^2-3x+1}}\),
co kończy dowód.

Dzięki, ładne rozwiązanie