\(\displaystyle{ \sum_{k=0}^n F_{2k}\cdot F_{n-k} =\frac{F_{2n+1} -F_{n+2}}{2},}\)
gdzie \(\displaystyle{ F_n}\) oznacza \(\displaystyle{ n-}\) ty wyraz ciągu fibonacciego.Tożsamość dotycząca liczb fibonacciego
-
Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
Tożsamość dotycząca liczb fibonacciego
Łatwo pokazać, że ciąg \(\displaystyle{ a_n = F_{2n}}\) spełnia \(\displaystyle{ a_{n+2} = 3a_{n+1}-a_n}\), skąd możemy wyznaczyć, że jego funkcją tworzącą jest \(\displaystyle{ \frac{x}{1-3x+x^2}}\). Funkcją tworzącą \(\displaystyle{ F_n}\) jest oczywiście \(\displaystyle{ \frac{x}{1-x-x^2}}\). Po lewej stronie mamy splot tych dwóch ciągów, więc jego funkcja tworząca to iloczyn funkcji tworzących \(\displaystyle{ F_{2n}}\) oraz \(\displaystyle{ F_{n}}\) czyli \(\displaystyle{ \frac{x^2}{(1-3x+x^2)(1-x-x^2)}}\).
Teraz prawa strona, ciąg \(\displaystyle{ F_{2n+1}}\) spełnia to samo równanie rekurencyjne co \(\displaystyle{ F_{2n}}\) tylko z innymi warunkami brzegowymi, skąd też łatwo wyznaczamy, że funkcją tworzącą tego ciągu jest \(\displaystyle{ \frac{1-x}{1-3x+x^2}}\). Podobnie f.t \(\displaystyle{ F_{n+2}}\) jest \(\displaystyle{ \frac{1+x}{1-x-x^2}}\). Pozostaje więc sprawdzić, że \(\displaystyle{ \frac{x^2}{(1-3x+x^2)(1-x-x^2)} = \frac{\frac{1-x}{1-3x+x^2} - \frac{1+x}{1-x-x^2}}{2}}\), co jest dość proste.
Teraz prawa strona, ciąg \(\displaystyle{ F_{2n+1}}\) spełnia to samo równanie rekurencyjne co \(\displaystyle{ F_{2n}}\) tylko z innymi warunkami brzegowymi, skąd też łatwo wyznaczamy, że funkcją tworzącą tego ciągu jest \(\displaystyle{ \frac{1-x}{1-3x+x^2}}\). Podobnie f.t \(\displaystyle{ F_{n+2}}\) jest \(\displaystyle{ \frac{1+x}{1-x-x^2}}\). Pozostaje więc sprawdzić, że \(\displaystyle{ \frac{x^2}{(1-3x+x^2)(1-x-x^2)} = \frac{\frac{1-x}{1-3x+x^2} - \frac{1+x}{1-x-x^2}}{2}}\), co jest dość proste.