W rękopisie z 1202 roku Leonarda z Pizzy zwanego Fibonaccim znajduje się zadanie:
Ile par królików może być spłodzonych przez parę płodnych królików i jej potomstwo w ciągu roku. jeśli każda para w ciągu miesiąca daje żywot jednej parze, para staje się płodna po miesiącu, króliki nie zdychają w ciągu roku.
Po miesiącu mamy już dwie pary przy czym jedna z nich jest płodna, a druga jeszcze nie. Po dwóch miesiącach żyją już trzy pary królików: dwie płodne , jedna jeszcze nie. Po trzech miesiącach żyje już pięć par królików: trzy płodne dwie jeszcze nie. Po czterech miesiącach jest osiem par królików pięć płodnych trzy jeszcze nie. Kontynuując to postępowanie stwierdzamy, że po roku żyje \(\displaystyle{ 377 = 233 + 144 }\) par królików.
Naturalnym problemem jest znaleźć wzór na liczbę \(\displaystyle{ a_{n} }\), jeśli \(\displaystyle{ a_{0} = 1, \ \ a_{1} = 2, \ \ a_{n} = a_{n-1} + a_{n-2}, }\) dla \(\displaystyle{ n = 2,3,4,... \ \ (*) }\)
Parę liczb możemy potraktować jako punkt płaszczyzny \(\displaystyle{ (a_{1}, a_{2}) }\) Mając dany ten punkt znajdujemy punkt \(\displaystyle{ (a_{2}, a_{3}) = (a_{2}, a_{1}+ a_{2}), }\) potem \(\displaystyle{ (a_{3}, a_{4}) = (a_{3}, a_{2} +a_{3}) ...}\)
Mamy więc przekształcenie na płaszczyźnie, które punktowi \(\displaystyle{ \left( \begin{matrix} x \\ y \end{matrix} \right) }\) przypisuje punkt
\(\displaystyle{ \left( \begin{matrix} y \\ x +y \end{matrix} \right) = \left( \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)\left( \begin{matrix} x \\ y \end{matrix} \right). }\)
Chodzi o znalezienie wzoru na \(\displaystyle{ a_{n}, }\) czyli formalnie rzecz biorąc o rozwiązanie potęgowego równania macierzowego:
\(\displaystyle{ \left( \begin{matrix} a_{n} \\ a_{n+1} \end{matrix} \right) = \left( \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)^{n-1} \left( \begin{matrix} 1\\ 1 \end{matrix} \right). }\)
Zaczniemy od znalezienia wartości i wektorów własnych macierzy \(\displaystyle{ \left( \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right) }\)
Trzeba rozwiązać równanie
\(\displaystyle{ 0 = \left | \begin{matrix} 0 -\lambda & 1 \\ 1 & 1 - \lambda \end{matrix} \right| -\lambda(1- \lambda) -1 = \lambda^2 - \lambda -1. }\)
Równanie to ma dwa pierwiastki : \(\displaystyle{ \lambda_{1} = \frac{1 + \sqrt{5}}{2}, \ \ \lambda_{2} = \frac{1 + \sqrt{5}}{2}. }\)
Odpowiadają im wektory własne np. \(\displaystyle{ \vec{v_{1}} = ( 1, \lambda_{1}), \ \ \vec{v_{2}} = ( 1 , \lambda_{2}). }\)
Można każdy z nich pomnożyć przez dowolną liczbę różną od zera.
Zauważmy, że \(\displaystyle{ \left(\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)\vec{v_{1}} = \lambda_{1}\vec{v_{1}},}\)
zatem
\(\displaystyle{ \left(\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)^2 \vec{v_{1}} = \left(\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)\left[ \left( \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right) \vec{v_{1}}\right] = \left(\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)(\lambda_{1}\vec{v_{1}}) =\lambda_{1}\left( \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)\vec{v_{1}} = \lambda_{1}^2\vec{v_{1}}}\)
Powtarzając ten rachunek wielokrotnie, otrzymujemy
\(\displaystyle{ \left(\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)^{n-1}\vec{v_{1}}= \lambda_{1}^{n-1}\vec{v_{1}} }\) i analogicznie
\(\displaystyle{ \left(\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)^{n-1}\vec{v_{2}}= \lambda_{2}^{n-1}\vec{v_{2}} }\)
Znaleźliśmy jakieś równania ale nie te o które nam chodzi. Poprawimy się. W tym celu znajdziemy liczby \(\displaystyle{ b, c }\) takie, że
\(\displaystyle{ ( 1, 1) = b\cdot \vec{v_{1}} + c\cdot \vec{v_{2}} }\)
Bardziej naukowo znajdziemy współrzędne wektora \(\displaystyle{ (1, 1) }\) w bazie wektorów \(\displaystyle{ \vec{v_{1}}, \vec{v_{2}},}\)
\(\displaystyle{ \left( \begin{matrix} 1\\ 1\end{matrix} \right) = \left( \begin{matrix} 1 & 1 \\ \lambda_{1} & \lambda_{2} \end{matrix} \right) \left( \begin{matrix} b \\ c \end{matrix}\right), }\)
Stąd
\(\displaystyle{ \left( \begin{matrix} b \\ c \end{matrix}\right) = \left( \begin{matrix} 1 & 1 \\ \lambda_{1} & \lambda_{2} \end{matrix} \right)^{-1}\left( \begin{matrix} 1 \\ 1 \end{matrix} \right) = \frac{1}{\lambda_{2} - \lambda_{1}} \left( \begin{matrix} \lambda_{2} & -1\\ -\lambda_{1} & 1\end{matrix}\right) \left( \begin{matrix} 1 \\ 1 \end{matrix} \right) = \frac{1}{\lambda_{2} -\lambda_{1}} \left( \begin{matrix} \lambda_{2}& -1\\ 1& -\lambda_{1} \end{matrix} \right) = \frac{1}{\lambda_{2} - \lambda_{1}} \left( \begin{matrix} -\lambda_{1} \\ \lambda_{2} \end{matrix} \right). }\)
Skorzystaliśmy z równości \(\displaystyle{ \lambda_{1} + \lambda_{2} = 1 }\)(wzoru Viete'a)
Wobec tego mamy
\(\displaystyle{ \left( \begin{matrix} a_{n} \\ a_{n+1} \end{matrix} \right) = \left(\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)^{n-1} \left( \begin{matrix} 1\\ 1 \end{matrix} \right) = \left( \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)^{n-1} \left( \frac{-\lambda_{1}}{\lambda_{2} - \lambda_{1}} \vec{v_{1}} + \frac{\lambda_{2}}{\lambda_{2} - \lambda_{1}} \vec{v_{2}} \right) = \frac{-\lambda_{1}}{\lambda_{2}-\lambda_{1}} \left( \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)^{n-1}\vec{v_{1}} + \frac{\lambda_{2}}{\lambda_{2} - \lambda_{1}} \left( \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)^{n-1}\vec{v_{2}} = }\)
\(\displaystyle{ = \frac{-\lambda_{1}^{n}}{\lambda_{2} - \lambda_{1}}\vec{v_{1}} + \frac{\lambda_{2}^{n}}{\lambda_{2} - \lambda_{1}} \vec{v_{2}} }\)
Uwzględniając równość
\(\displaystyle{ \lambda_{2} - \lambda_{1} = -\sqrt{5} }\),
otrzymujemy
\(\displaystyle{ a_{n} = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2}\right)^{n} - \left( \frac{1 -\sqrt{5}}{2} \right)^{n} \right] }\)
Uzyskany wzór jest wzorem matematyka francuskiego Jacque'a Bineta ( 1786 - 1856).
Zadziwiającym jest fakt, że musiało upłynąć wiele setek lat zanim znaleziono ten wzór.
Literatura:
Michał Krych. Twierdzenie o wartościach własnych i wielomianie charakterystycznym - wykłady dla studentów ekonomii. MiMUW Warszawa
2008-2010.
Dodano po 48 minutach 4 sekundach:
Metoda równania różnicowego.
\(\displaystyle{ F_{1} = 1, \ \ F_{2} = 2, \ \ F_{n} = F_{n-1} - F_{n-2} }\)
Równanie charakterystyczne:
\(\displaystyle{ x^2 -x - 1 = 0 }\)
ma pierwiastki
\(\displaystyle{ x_{1}= \frac{1 +\sqrt{5}}{2}, \ \ x_{2} = \frac{1-\sqrt{5}}{2} }\)
Rozwiązanie ogólne równania:
\(\displaystyle{ F_{n} = K_{1}\alpha^{n} + K_{2}\beta^{n} }\)
gdzie:
\(\displaystyle{ \alpha = \frac{1}{2}( 1 + \sqrt{5}), \ \ \alpha_{2} = \frac{1}{2}( 1 -\sqrt{5}) }\)
Uwzględniając warunki początkowe:
\(\displaystyle{ F_{1} = 1, \ \ F_{2} = 2, }\) otrzymujemy wartości stałych:
\(\displaystyle{ K_{1}= \frac{\alpha}{\sqrt{5}}\ \ \ K_{2} = \frac{-\beta}{\sqrt{5}} }\)
Stąd
\(\displaystyle{ F_{n} = \frac{1}{\sqrt{5}} \alpha^{n+1} - \frac{1}{\sqrt{5}} \beta^{n+1} = \frac{1}{\sqrt{5}} \left(\frac{1 +\sqrt{5}}{2}\right)^{n+1} - \frac{1}{\sqrt{5}} \left(\frac{1 +\sqrt{5}}{2}\right)^{n+1} }\)
Dodano po 5 minutach 15 sekundach:
Metoda funkcji generujących
Dodano po 17 godzinach 13 minutach 40 sekundach:
Znajdziemy funkcję generującą ciąg Fibonacciego:
\(\displaystyle{ F(x) = \sum_{n=0}^{\infty} F_{n}x^{n} = \sum_{n=1}^{\infty} F_{n-1}x^{n} = F_{1}x + \sum_{n=2}^{\infty} F_{n}x^{n} = x + \sum_{n=2} (F_{n-1}x^{n} + F_{n-2}) x^{n} = x + \sum_{n=2}^{\infty} F_{n-1}x^{n} + \sum_{n=2}^{\infty} F_{n-2} x^{n} = }\)
\(\displaystyle{ = x + x\sum_{n=1}^{\infty}F_{n-1}x^{n-1} +x^2 \sum_{n=2}^{\infty}F_{n-2} x^{n-2} = x + x F(x) + x^2 F(x)}\)
Stąd
\(\displaystyle{ F(x) - xF(x) - x^2 F(x) = x }\)
\(\displaystyle{ F(x) = \frac{x}{1 -x - x^2} }\) - funkcja generująca ciąg Fibonacciego.
Postać iloczynowa trójmianu kwadratowego
\(\displaystyle{ 1 - x - x^2 = -( x +\alpha)( x + \beta), }\)
gdzie liczby
\(\displaystyle{ -\alpha = \frac{1 +\sqrt{5}}{2}, \ \ -\beta = \frac{1 -\sqrt{5}}{2} }\)
są pierwiastkami trójmianu kwadratowego.
Rozkładamy funkcję \(\displaystyle{ F }\) na sumę ułamków prostych
\(\displaystyle{ F(x) = -\frac{x}{(x +\alpha)(x + \beta)} = \frac{A}{x +\alpha} + \frac{B}{ x + \beta} }\)
\(\displaystyle{ -x = A(x +\beta) + B(x +\alpha) }\)
Kładąc \(\displaystyle{ x = - \alpha, }\) dostajemy \(\displaystyle{ A = -\frac{\alpha}{\sqrt{5}} }\)
Kładąc \(\displaystyle{ x = -\beta , }\) dostajemy \(\displaystyle{ B = \frac{\beta}{\sqrt{5}} }\)
Stąd
\(\displaystyle{ F(x) = \frac{1}{\sqrt{5}} \left( \frac{\beta}{x +\beta} - \frac{\alpha}{x+\alpha} \right) }\)
Korzystając z faktu, że \(\displaystyle{ \alpha = -\frac{1}{\beta} }\) wyrazimy funkcję \(\displaystyle{ F }\) jako różnicę sum szeregów geometrycznych.
\(\displaystyle{ \frac{\beta}{x+\beta} = \frac{1}{1 +\frac{x}{\beta}} = \frac{1}{1-\alpha x} = \sum_{n=0}^{\infty} \alpha^{n}x^{n} }\)
Podobnie
\(\displaystyle{ \frac{\alpha}{x+\alpha} = \sum_{n=0}^{\infty} \beta^{n} x^{n} }\)
Zatem
\(\displaystyle{ F(x) = \sum_{n=0}^{\infty} \frac{1}{\sqrt{5}} \left(\alpha^{n} - \beta^{n} \right )x^{n} \ \ (1)}\)
Porównując \(\displaystyle{ (1) }\) z postacią funkcji generującej, otrzymujemy wzór na \(\displaystyle{ n - }\) ty wyraz ciągu Fibonacciego:
\(\displaystyle{ F_{n} = \frac{1}{\sqrt{5}} \left(\alpha^{n} - \beta^{n}\right) = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 +\sqrt{5}}{2}\right)^{n} - \left(\frac{1 -\sqrt{5}}{2}\right)^{n} \right] }\)