The Fibonacci Sequence is given by the recursive definition:

$\displaystyle F(n)=\begin{cases}1 & \text{ if }n=1\text{ or }n=2\\ F(n-1)+F(n-2) & \text{ otherwise } \end{cases}$

## Exercises

• Prove that if $F(n)=x^n$ satisfies the recurrence relation

$F(n+2)=F(n+1)+F(n)$,

that $x=\frac{1\pm \sqrt{5}}{2}$.

• If the Fibonacci Sequence is given by:

$\displaystyle F(n)=\frac{\phi^n-\psi^n}{\sqrt{5}}$,

where $\phi=\frac{1+\sqrt{5}}{2}$ and $\psi=\frac{1-\sqrt{5}}{2}$, prove that for large $n$:

$F(n+1)\approx \phi\cdot F(n)$

• Use ten terms of the Fibonacci Sequence to write down a sequence of rational approximations to $\phi$.

• Using $\displaystyle F(n)=\frac{\phi^n-\psi^n}{\sqrt{5}}$, where $\phi=\frac{1+\sqrt{5}}{2}$ and $\psi=\frac{1-\sqrt{5}}{2}$, or otherwise, find $F(22)$.