Fibonacci Problem

The Fibonacci Problem is a very well known computer science problem in which the program must calculate the nth term in the Fibonacci Sequence. The Fibonacci Sequence is as follows:

(1)
\begin{align} \begin{align*} F_0&=1\\ F_1&=1\\ F_n&=F_{n-1}+F_{n-2} \end{align}

Note that some sources may prefer to use $F_1=F_2=1$
One of the most common uses of the Fibonacci problem is to demonstrate the different methods of Dynamic Programming.

Using various mathematical methods, one can obtain an exact formula for the Fibonacci sequence. However, this method is not suitable for computers due to its use of $\phi = \frac{1+\sqrt{5}}{2}$. An alternative method is outlined below.

Consider the matrix $\begin{pmatrix}1&1\\1&0\end{pmatrix}$. When applied to the vector $\begin{pmatrix}F_n\\F_{n-1}\end{pmatrix}$, one obtains $\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}F_n\\F_{n-1}\end{pmatrix} = \begin{pmatrix}F_n+F_{n-1}\\F_n\end{pmatrix} = \begin{pmatrix}F_{n+1}\\F_{n}\end{pmatrix}$. Then one can inductively show that $\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix}^n\begin{pmatrix}1\\1\end{pmatrix}$. One may then apply any method to raise the matrix to the appropriate power, the most common being repeated squaring.

page revision: 2, last edited: 12 Nov 2007 01:03