2. Explore Some Fibonacci Sequence Math

The Fibonacci numbers form a sequence {a_n}, where {a_0=0}, {a_1=1}, and {a_i = a_{i-1} + a_{i-2}} for { i>1}.

I. Show ratios of consecutive Fibonacci numbers converge. Derive their limit {\phi}.

i) Rearrange the recurrence equation to resemble the first convergent in a simple continued fraction.

Define {b_0=1} and for {n>0} let:

{b_n = \dfrac{a_{n+1}}{a_n} = \dfrac{a_n+a_{n-1}}{a_n} = 1 + \dfrac{a_{n-1}}{a_n} = 1 + \dfrac{1}{\dfrac{a_n}{a_{n-1}}}=1 + \dfrac{1}{b_{n-1}}}.

ii) Construct the continued fraction for a few terms, observing that the sequence of convergents form the Fibonacci ratios.

{b_1=1+\dfrac{1}{1}=\dfrac{2}{1}}

{b_2=1+\dfrac{1}{b_1}=1+\cfrac{1}{1+\cfrac{1}{1}}=\dfrac{3}{2}}

{b_3=1+\dfrac{1}{b_2}=1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1}}}=\dfrac{5}{3}}

Continuing with {b_4=\dfrac{8}{5}}, {b_5=\dfrac{13}{8}},…, one constructs a simple infinite continued fraction consisting of all 1’s. It is known that any infinite continued fraction uniquely represents an irrational number, and the sequence of convergents has this number as a limit, with alternate terms forming two subsequences that converge from above and below (see Problem 3 solution).

iii)Deduce the infinite fraction’s closed form quadratic equation, which can then be solved for real roots {\phi} and {\varphi=1-\phi}.

With proof of convergence given, let {\phi = \displaystyle \lim_{n \rightarrow \infty} b_n \ne 0}; then one obtains {\phi = 1 + \dfrac{1}{\phi}}. Rewriting this quadratic polynomial as {\phi^2 - \phi - 1 = 0} one obtains the positive root as the desired limit value:

{\phi = \dfrac{1 + \sqrt{5}}{2}} is called the Golden Mean; the other root is {\varphi = \dfrac{1 - \sqrt{5}}{2}}.

II): Derive a closed-form solution for the nth Fibonacci number.

i) Observe the interesting relations for {n>0}:

{\phi^n = \phi a_n + a_{n-1}}
{\varphi^n = \varphi a_n + a_{n-1}}

Verify by induction. For case {n=2}, {\phi^2=\dfrac{3+ \sqrt{5}}{2}=\phi+1} is immediately true. Assume it is true for {n}. Then using {\phi^2=\phi+1} and rewriting {a_{n-1}} in terms of {a_n} and {a_{n+1}} from the recursion equation,

{\phi^{n+1}=\phi( \phi^n)=\phi^2 a_n+\phi a_{n-1}=\phi a_n + a_n + \phi a_{n+1} - \phi a_n = \phi a_{n+1} + a_n}.

With the {\varphi} equation proved via the same mechanism, these equations are verified.

ii) Combine these equations (i) to remove the {a_{n-1}} term and express {a_n} in terms of {\phi} and {\varphi}.

{\phi^n -\varphi^n = a_n(\phi-\varphi)} or

{a_n=\dfrac{\phi^n -\varphi^n}{\sqrt{5}}} (Binet’s Formula).

That’s one of the great integer disguises, don’t you think?

iii) Alternatively, one can write simultaneous linear equations to express the numerators and denominators in the sequence of ratios above, then use linear algebra.

Write the nth fractional convergent in terms of distinct variables: {\dfrac{a_n}{a_{n-1}}=\dfrac{x_n}{y_n}}.

Then {\dfrac{x_{n+1}}{y_{n+1}}=1+\dfrac{y_n}{x_n}=\dfrac{x_n+y_n}{x_n}}, giving

{x_{n+1}=x_n + y_n}
{y_{n+1}=x_n}

In matrix form:

{\begin{bmatrix} x_{n+1}\\y_{n+1}\end{bmatrix}=\begin{bmatrix} 1&&1 \\ 1&&0 \end{bmatrix}\begin{bmatrix}x_n\\y_n\end{bmatrix}}.

Thus to go from one convergent to the next in sequence involves multiplication by a matrix, and this can be repeated {n} times to express the nth convergent in terms of the initial values :

{\begin{bmatrix} a_{n+1}\\a_n\end{bmatrix}=\begin{bmatrix} 1&&1 \\ 1&&0 \end{bmatrix}^n\begin{bmatrix}1\\{0}\end{bmatrix}}.

Call our matrix F. Surprise, the characteristic polynomial of {F} is {\phi^2-\phi-1}; solving it gives the eigenvalues {\phi} and {\varphi} and eigenvectors {\begin{bmatrix}\phi\\1\end{bmatrix}} and {\begin{bmatrix}\varphi \\ 1\end{bmatrix}}.

Diagonalize {F} via {F=TDT^{-1}}, so that {F^n=TD^nT^{-1}}, where

{D=\begin{bmatrix}\phi&&0\\{0}&& \varphi \end{bmatrix}}, {D^n=\begin{bmatrix}\phi^n&&0\\{0}&&\varphi^n \end{bmatrix}}, {T=\begin{bmatrix}\phi&&\varphi\\ 1&&1 \end{bmatrix}}, {T^{-1}=\dfrac{1}{\phi-\varphi}\begin{bmatrix}1&&-\varphi \\-1&&\phi \end{bmatrix}}.

Then {\begin{bmatrix} a_{n+1}\\a_n\end{bmatrix}=TD^nT^{-1}\begin{bmatrix}1\\{0}\end{bmatrix}=\dfrac{1}{\sqrt{5}}TD^n\begin{bmatrix}1\\-1\end{bmatrix}=\dfrac{1}{\sqrt{5}}T\begin{bmatrix}\phi^n\\-\varphi^n\end{bmatrix}=\dfrac{1}{\sqrt{5}}\begin{bmatrix}\phi^{n+1}-\varphi^{n+1}\\\phi^n-\varphi^n\end{bmatrix}}.

There it is again, the Binet Formula: {a_n=\dfrac{\phi^n -\varphi^n}{\sqrt{5}}}.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s