Spośród ciągów zdefiniowanych rekurencyjnie, jednym z najsłynniejszych jest ciąg Fibonacciego \( {\{ {f_i} \}\ }_{i\in\mathbb{N}} \) zadany przez
\( \begin{align*} f_0 & =0, \\ f_1 & =1, \\ f_{n+2} & =f_n+f_{n+1}. \end{align*} \)
Wszystkie wyrazy ciągu, oprócz pierwszych dwu, są sumą dwu poprzednich elementów. Oto kilka pierwszych wartości ciągu Fibonacciego:
\( \begin{array} {c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ \hline 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 & 377 & 610 \\ \end{array} \)
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 \)?
\( \begin{array} {|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \hline & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \hline \end{array} \)
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 \):
\( f_0^2+f_1^2+\ldots+f_k^2+f_{k+1}^2 = f_k\cdot f_{k+1}+f_{k+1}^2 = f_{k+1}\cdot(f_k+f_{k+1}) = f_{k+1}\cdot f_{k+2}, \)
co kończy dowód kroku indukcyjnego.
Twierdzenie 2.3 [wzór Eulera-Bineta]
\( f_n=\frac{1}{\sqrt{5}} \left[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n\right]. \)
Dowód
Rozważmy równanie:
\( f^2-f-1=0. \)
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 \left[(\frac{1+\sqrt{5}}{2})^{n} - (\frac{1-\sqrt{5}}{2})^{n} \right], \)
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
\( \lim_{n \to \infty}\frac{f_{n+1}}{f_n}=\varphi. \)
Dowód
\( \begin{align*} \lim_{n \to \infty}\frac{f_{n+1}}{f_n} & =\lim_{n \to \infty}\frac{\frac{1}{\sqrt{5}}(\varphi^{n+1}-(1-\varphi)^{n+1})}{\frac{1}{\sqrt{5}}(\varphi^n-(1-\varphi)^n)} \\ & =\lim_{n \to \infty}\frac{\frac{1}{\sqrt{5}}\varphi-\frac{1}{\sqrt{5}}(1-\varphi)(\frac{1-\varphi}{\varphi})^n}{\frac{1}{\sqrt{5}}-\frac{1}{\sqrt{5}}(\frac{1-\varphi}{\varphi})^n} \\ & =\varphi, \end{align*} \)
gdzie ostatnia równość wynika z faktu, iż
\( \lim_{n \to \infty}(\frac{1-\varphi}{\varphi})^n=0, \)
jako że \( \vert\frac{1-\varphi}{\varphi}\vert < 1 \).
Rozważając specjalne kwadratowe macierze \( 2\times2 \) liczb Fibonacci'ego postaci
\( \left[ \begin{array} {cc} f_{n+2} & f_{n+1} \\ f_{n+1} & f_n \end{array} \right] \)
łatwo zauważamy, że
\( \left[ \begin{array} {cc} f_{n+2} & f_{n+1} \\ f_{n+1} & f_n \end{array} \right] \left[ \begin{array} {cc} 1 & 1 \\ 1 & 0 \end{array} \right] = \left[ \begin{array} {cc} f_{n+3} & f_{n+2} \\ f_{n+2} & f_{n+1} \end{array} \right]. \)
Ponieważ równocześnie:
\( \left[ \begin{array} {cc} f_2 & f_1 \\ f_1 & f_0 \end{array} \right] = \left[ \begin{array} {cc} 1 & 1 \\ 1 & 0 \end{array} \right], \)
to łatwo indukcyjnie łatwo udowodnić, że
\( \left[ \begin{array} {cc} f_{n+1} & f_n \\ f_n & f_{n-1} \end{array} \right] = \left[ \begin{array} {cc} 1 & 1 \\ 1 & 0 \end{array} \right]^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}. \)