Liczby Fibonacciego

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} \)

  • Jak odgadnąć wzór na ogólny wyraz ciągu?
  • Jeśli nie można odgadnąć, to jak oszacować szybkość wzrostu tego ciągu?
  • Czy rośnie on wielomianowo czy raczej wykładniczo?

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 \).

  • Dla \( n=1 \) jest to możliwe na dokładnie jeden sposób, tzn. \( d_1=1 \)
  • Dla \( n=2 \) są już dwa takie sposoby:

- ustawiamy obie kostki poziomo, lub obie pionowo,
a zatem \( d_2=2 \).

  • Dla \( n=3 \) są trzy sposoby,
  • Pokrywając większy prostokąt \( 2 \times n \) musimy jakoś pokryć dwa skrajne pola przylegające do krótszej krawędzi o długości \( 2 \). Można to zrobić na dwa sposoby:
    • ułożyć jedno domino pionowo - pozostanie prostokąt \( 2 \times (n - 1) \), który można pokryć na \( d_{n-1} \) sposobów,
    • ułożyć dwa domina poziomo - pozostanie prostokąt \( 2 \times (n - 2) \), który można pokryć na \( d_{n-2} \) sposobów.

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:

  • Jest tylko jedna metoda ułożenia prostokąta \( 2 \times (n+1) \) bez poziomych klocków. A zatem jest \( f_{n+2}-1 \) sposobów ułożenia prostokąta \( 2 \times (n+1) \) z chociaż jednym dominem poziomym.
  • Rozważmy kolejne możliwe miejsca pierwszego poziomego domina (tak naprawdę pary domin) w prostokącie \( 2 \times (n+1) \) od lewej:
    • jeśli na samym początku jest para poziomych domin, to pozostaje prostokąt \( 2\times (n-1) \), który możemy wypełnić dowolnie na \( f_{n} \) sposobów;
    • jeśli na początku jest \( i \) (gdzie \( 0\leq i\leq n \)) pionowych domin, a potem następuje para poziomych, to pozostaje prostokąt \( 2\times (n-i-1) \), który można wypełnić na \( f_{n-i} \) sposobów;
    • para poziomych domin może się pojawić najdalej po \( i=n-1 \) pionowych dominach

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 \):

  • dla \( n=0 \) mamy \( f_0^2=0=f_0\cdot f_1 \),
  • do założonej indukcyjnie równości \( f_0^2+f_1^2+\ldots+f_k^2=f_k\cdot f_{k+1} \) dodajmy obustronnie \( f_{k+1}^2 \) otrzymując

\( 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:

  • jeśli ciąg \( a_n \) spełnia zależność \( f^{n+2}=f^{n+1}+f^n \), to dla dowolnej liczby rzeczywistej \( \alpha \) ciąg \( \alpha\cdot a_n \) też spełnia tę zależność,
  • jeśli ciągi \( a_n \) i \( b_n \) spełniają zależność \( f^{n+2}=f^{n+1}+f^n \), to ich suma \( a_n+b_n \) też spełnia tę zależność.

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} \).

  • Ponieważ liczby Fibonacci'ego są zadane wzorem odwołującym się do dwóch poprzednich elementów sprawdzamy dwie pierwsze wartości:
    • \( F(0)=\frac{1}{\sqrt{5}}\varphi^0-\frac{1}{\sqrt{5}}(1-\varphi)^0=\frac{1}{\sqrt{5}}-\frac{1}{\sqrt{5}}=0=f_0 \),
    • \( F(1)=\frac{1}{\sqrt{5}}\varphi-\frac{1}{\sqrt{5}}(1-\varphi)=\frac{1}{\sqrt{5}}(2\cdot\frac{1+\sqrt{5}}{2}-1)=1=f_1 \),
  • Aby pokazać, że \( F(k+2)=f_{k+2} \) użyjemy pod koniec naszych obliczeń założenia indukcyjnego, że \( F(k+1)=f_{k+1} \) i \( F(k)=f_{k} \), a także tego, że zarówno \( \varphi \) jak i \( 1-varphi \) spełniają zależność \( x^{k+2}=x^{k+1}+x^k \):


\( \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 \).

Macierze liczb Fibonacci'ego

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*} \)

Rozwiązywanie liniowych równań rekurencyjnych - metoda ogólna

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}. \)