Exercise 7

The Fibonacci numbers form the sequence of numbers that begins $0, 1, 1, 2, 3, 5, 8, 13, \ldots$. If we let $F_n$ denote the $n^{th}$ Fibonacci number, then $$F_0 =0, F_1 =1, F_2 =1, F_3 =2, F_4 =3,\ldots$$. In general, a Fibonacci number is the sum of the previous two Fibonacci numbers; that is, $F_{n+2} = F_{n}+F_{n+1}$ so that we have $$\begin{aligned} F_{n+2} & {}={} F_{n} + F_{n+1} \\ F_{n+1} & {}={} F_{n+1}\text{.} \\ \end{aligned}$$

1. If we write $\xvec_n = \twovec{F_{n+1}}{F_n}$, find the matrix $A$ such that $\xvec_{n+1} = A\xvec_n$.

2. Show that $A$ has eigenvalues $$\begin{aligned} \lambda_1 & {}={} \frac{1+\sqrt{5}}{2}\approx 1.61803\ldots \\ \lambda_2 & {}={} \frac{1-\sqrt{5}}{2}\approx -0.61803\ldots \\ \end{aligned}$$ with associated eigenvectors $\vvec_1=\twovec{\lambda_1}{1}$ and $\vvec_2=\twovec{\lambda_2}{1}$.

3. Classify this dynamical system as one of the six types that we have seen in this section. What happens to $\xvec_n$ as $n$ becomes very large?

4. Write the initial vector $\xvec_0 = \twovec{1}{0}$ as a linear combination of eigenvectors $\vvec_1$ and $\vvec_2$.

5. Write the vector $\xvec_n$ as a linear combinations of $\vvec_1$ and $\vvec_2$.

6. Explain why the $n^{th}$ Fibonacci number $$F_{n} = \frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]\text{.}$$

7. Use this relationship to compute $F_{20}$.

8. Explain why $F_{n+1}/F_{n}\approx \lambda_1$ when $n$ is very large.

The number $\lambda_1=\frac{1+\sqrt{5}}{2} = \phi$ is called the golden ratio and is one of mathematics' special numbers.