##### Exercise7

The Fibonacci numbers form the sequence of numbers that begins $$0, 1, 1, 2, 3, 5, 8, 13, \ldots\text{.}$$ If we let $$F_n$$ denote the $$n^{th}$$ Fibonacci number, then

\begin{equation*} F_0 =0, F_1 =1, F_2 =1, F_3 =2, F_4 =3,\ldots \text{.} \end{equation*}

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{equation*} \begin{aligned} F_{n+2} \amp {}={} F_{n} + F_{n+1} \\ F_{n+1} \amp {}={} F_{n+1}\text{.} \\ \end{aligned} \end{equation*}

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

2. Show that $$A$$ has eigenvalues

\begin{equation*} \begin{aligned} \lambda_1 \amp {}={} \frac{1+\sqrt{5}}{2}\approx 1.61803\ldots \\ \lambda_2 \amp {}={} \frac{1-\sqrt{5}}{2}\approx -0.61803\ldots \\ \end{aligned} \end{equation*}

with associated eigenvectors $$\vvec_1=\twovec{\lambda_1}{1}$$ and $$\vvec_2=\twovec{\lambda_2}{1}\text{.}$$

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\text{.}$$

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

6. Explain why the $$n^{th}$$ Fibonacci number

\begin{equation*} 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{.} \end{equation*}
7. Use this relationship to compute $$F_{20}\text{.}$$

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.

in-context