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).
Advertisements