Wszystkie wyrazy ciągu, oprócz pierwszych dwu, są sumą dwu poprzednich elementów. Oto kilka pierwszych wartości ciągu Fibonacciego:
Pierwsze pytanie - póki co - wydaje się dość beznadziejne.
Przykład
Na ile sposobów można ułożyć domina na prostokącie o rozmiarze \( 2 \times n \)?
Oznaczmy, tę liczbę przez \( d_n \) w zależności od \( n \).
- ustawiamy obie kostki poziomo, lub obie pionowo,
a zatem \( d_2=2 \).
Czyli łącznie jest \( d_n = d_{n-1}+d_{n-2} \) sposobów pokrycia tablicy \( 2 \times n \).
Rozpoznajemy w tym łatwo ciąg Fibonacci'ego \( d_n = f_{n+1} \) (bo oczywiście pusty prostokąt \( 2 \times 0 \) można pokryć na dokładnie jeden sposób, \( d_0=1 \)).
Obserwacja 2.1
\( f_0+f_1+\ldots+f_n=f_{n+2}-1. \)
Dowód
Polecamy jako ćwiczenie bardzo łatwy dowód powyższej równości przez indukcję. Przedstawimy alternatywny dowód posługujący się intuicją z poprzedniego przykładu. Wiemy zatem, że prostokąt wielkości \( 2\times n \) można pokryć kostkami domina na \( f_{n+1} \) sposobów.
Dla dowodu obserwacji, policzmy na ile sposobów można ułożyć prostokąt wielkości \( 2 \times (n+1) \) w taki sposób aby było tam chociaż jedno domino ustawione poziomo. Policzymy to dwiema różnymi metodami:
To dowodzi, iż jest dokładnie \( f_n+f_{n-1}+\ldots+f_0 \) sposobów ułożenia prostokąta \( (n+1)\times2 \) z chociaż jednym dominem poziomym.
Policzyliśmy na dwa różne sposoby to samo, otrzymując obie strony postulowanej równości. To kończy dowód.
Obserwacja 2.2
\( f_0^2+f_1^2+\ldots+f_n^2=f_n\cdot f_{n+1}. \)
Dowód
Dowód przez indukcję po \( n \):
co kończy dowód kroku indukcyjnego.
Twierdzenie 2.3 [wzór Eulera-Bineta]
Dowód
Rozważmy równanie:
Mnożąc je obustronnie przez \( x^n \) otrzymujemy:
\( f^{n+2}=f^{n+1}+f^n. \)
Oznacza to, że jeśli \( x \) jest pierwiastkiem równania \( f^2-f-1=0 \), to ciąg \( f_n = x^n \) spełnia zależność rekurencyjną Fibonacci'ego:
\( f_{n+2} = f_n+f_{n+1}. \)
Tyle, że równanie ma dwa rzeczywiste rozwiązania:
\( x_1 = \frac{1+\sqrt{5}}{2} \ \ \ \ \ \ \ \ \ \ x_2 = \frac{1-\sqrt{5}}{2}. \)
Który więc z ciągów \( x_1^n, x_2^n \) jest ciągiem Fibonacci'ego? Okazuje się, że żaden, bo na przykład ilorazy kolejnych wyrazów ciągu Fibonacci'ego nie są stałe, a takie musiałyby być dla ciągów geometrycznych \( x_1^n, x_2^n \). Co więcej:
Oznacza to w szczególności, że zbiór \( F \) ciągów spełniających zależność \( f^{n+2}=f^{n+1}+f^n \) jest podprzestrzenią wektorową przestrzeni \( \mathbb{R}^\mathbb{N} \).
Ćwiczenie: Przestrzen \( F \) jest dwuwymiarowa o bazie \( \varphi, 1-\varphi \)
Przypuśćmy na chwilę, że jakaś kombinacja liniowa ciągów \( x_1^n, x_2^n \), tzn.
\( c_1 \cdot x_1^n + c_2 \cdot x_2^n \)
jest poszukiwanym ciągiem Fibonacci'ego. Aby wyznaczyć stałe \( c_1, c_2 \) zauważmy, że muszą one spełniać układ równań:
\( f_0 = c_1 + c_2 \ \ \ \ \ \ \ f_1 = c_1\cdot x_1 + c_2 x_2 \)
co po rozwiązaniu daje:
\( \begin{align*} c_1 & = \frac{f_1 - f_0x_2}{x_1-x_2}= \frac{1}{\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}} =\frac{1}{\sqrt{5}} \\ c_2 & = \frac{f_1 - f_0x_1}{x_2-x_1}= \frac{1}{\frac{1-\sqrt{5}}{2}-\frac{1+\sqrt{5}}{2}} =-\frac{1}{\sqrt{5}} \end{align*} \)
i ostatecznie dostajemy ciąg:
\( F(n) = \frac{1}{\sqrt{5}}\cdot[(\frac{1+\sqrt{5}}{2})^{n} - (\frac{1-\sqrt{5}}{2})^{n}], \)
jako potencjalnego kandydata na ciąg Fibonacci'ego. W istocie potrzebujemy indukcyjnego dowodu, że \( F(n)=f_n \). Dla wygody oznaczmy \( \varphi=\frac{1+\sqrt{5}}{2} \).
\( \begin{align*} F(k+2) & =\frac{1}{\sqrt{5}}\varphi^{k+2}-\frac{1}{\sqrt{5}}(1-\varphi)^{k+2} \\ & =\frac{1}{\sqrt{5}}(\varphi^{k}+\varphi^{k+1})-\frac{1}{\sqrt{5}}((1-\varphi)^{k}+(1-\varphi)^{k+1}) \\ & =\frac{1}{\sqrt{5}}(\varphi^{k}-(1-\varphi)^{k})+\frac{1}{\sqrt{5}}(\varphi^{k+1}-(1-\varphi)^{k+1}) \\ & =F(k)+F(k+1) \\ & =f_k+f_{k+1} \\ & =f_{k+2}. \end{align*} \)
Liczba \( \varphi=\frac{1+\sqrt{5}}{2} \) jest powszechnie znana jako złota liczba. Opisuje ona tak zwane złote proporcje w sztuce. Pojawia się ona również bardzo często przy okazji różnych obiektów kombinatorycznych. Występuje również w kolejnym wniosku, który po raz pierwszy zaobserwował Johannes Kepler.
Wniosek 2.4
Dowód
gdzie ostatnia równość wynika z faktu, iż
jako że \( \vert\frac{1-\varphi}{\varphi}\vert < 1 \).
Rozważając specjalne kwadratowe macierze \( 2\times2 \) liczb Fibonacci'ego postaci
łatwo zauważamy, że
Ponieważ równocześnie:
to łatwo indukcyjnie łatwo udowodnić, że
\( \bigg [ \begin{array} {cc} f_{n+1} & f_n \\ f_n & f_{n-1} \end{array} \bigg ] = \bigg [ \begin{array} {cc} 1 & 1 \\ 1 & 0 \end{array} \bigg ]^n. \)
Przyrównując wyznaczniki obu macierzy otrzymujemy tożsamość, którą jako pierwszy opublikował Jean-Dominique Cassini w 1680 roku.
Obserwacja 2.5
\( f_{n+1}f_{n-1}-f_n^2=(-1)^n. \)
Korzystając z kolei z faktu, że \( A^mA^n=A^{m+n} \) dla dowolnej kwadratowej macierzy \( A \), otrzymujemy:
Obserwacja 2.6
\( \begin{align*} f_n^2+f_{n-1}^2 & =f_{2n-1}, \\ f_{n+1}f_m+f_nf_{m-1} & =f_{m+n}. \end{align*} \)
Rozumowanie dotyczące ciągu Fibonacci'ego możemy uogólnić. Chwilowo skupimy się jedynie na przypadku, gdy dla rozwiązania równania rekurencyjnego
\( s_n = a\cdot s_{n-1} + b\cdot s_{n-2}, \)
równanie kwadratowe
\( x^2 = ax+b \)
ma dokładnie dwa różne pierwiastki \( x_1, x_2 \). Wtedy bowiem łatwo pokazać, że ciąg
\( s_n = c_1 \cdot x_1^n + c_2 \cdot x_2^n \)
ze stałymi
\( c_1 = \frac{s_1 - s_0x_2}{x_1-x_2} \ \ \ \ \ \ \ \ c_2 = \frac{s_1 - s_0x_1}{x_2-x_1} \)
jest poszukiwanym rozwiązaniem.
Gdy równanie \( x^2 = ax+b \) ma tylko jeden pierwiastek \( x_0 \) (podwójny, gdy \( a^2=4b \)), to wkrótce pokażemy, że rozwiązaniem jest
\( s_n = c_1 \cdot x_0^n + c_2 \cdot n \cdot x_0^n \)
ze stałymi wyznaczonymi, jak poprzednio, poprzez dwa pierwsze wyrazy początkowe:
\( c_1 = s_0 \ \ \ \ \ \ \ \ c_2 = \frac{s_1 - s_0x_0}{x_0}. \)