## Golden Nature: Closed-form Formula for Fibonacci Sequence

May 13, 2009 13:56 by scibuff

Almost everyone has heard of this sequence: $1,\ 1,\ 2,\ 3,\ 5,\ 8,\ etc$. It is named after Leonardo of Pisa who introduced it to the western world in one of the most influential books ever published in mathematics – Liber Abaci. This book introduced Europe to the Hindu numerals 0 through 9, the word zero, the notion of an algorithm and the subject of algebra.

The beauty of the Fibonacci sequence and the golden ratio (which is intimately connected to it) lies in that they are not just another mathematical construct, but occur throughout the nature.

Have you ever taken a look at a pine cone and noticed that the scales of the cone are in spirals? Have you ever counted the spiral in the clockwise and counterclockwise directions? I would be surprised if you have … but the counts turn out to be 5 and 8 (or 8 and 13 for bigger cones).

Pine Cone Spirals

How about these? Care to count the petals?

13 petals

21 petals

… intriguing stuff indeed.

So, once again, I was reading through problems on Yahoo Answers. Most of the questions “reduce” (lol) to plugging numbers into well known equations, or using a calculator such as TI-89, or Mathematics, Maple, or even Google – basically, what engineers do. Yeah, you “heard” me right! It takes some effort to found a meaningful question that actually requires some knowledge and skills – see the difference between a mathematician and an engineer now? That said, here’s a one I couldn’t resist:

Problem: Find the term $F_{386}$ in the following sequence $F_{0}=-4,\ F_{1}=5,\ F_{2}=1,\ F_{3}=6,\ F_{4}=7,\ F_{5}=13$

There is a more “elegant” way to tackle this problem and I may write about in the future (maybe quite soon actually), but for now I’ll ignore matrices, diagonalization and eigenspaces (although the reason why the following solution gives the correct result is tightly connected to linear algebra) and focus, instead, on the recursive nature of the Fibonacci sequence.

Solution: To find the term, “all” that is needed is to find the closed form for the n-th terms of the sequence $F_{n}$. In general, a Fibonacci sequence is given by

$F_{n} = F_{n-1} + F_{n-2}\ (1)$

and any particular sequence is fully determined by the initial two terms

$F_{0}$ and $F_{1}$

In our example, we have

$F_{0}=-4$ and $F_{1}=5$

To find the closed form, let’s assume

$F_{n}=(-4)\times t^{n}$

Then using our recursive formula $(1)$ we get

$(-4)t^{n+1}=(-4)\left ( t^{n} + t^{n-1}\right )$

and so

$t^{2}=t + 1\Rightarrow t^{2} - t - 1 = 0\ (2)$

Solving the quadratic from $(2)$ gives

$t_{1,2}=\frac{1\pm \sqrt{5}}{2}$

Using this result, we can write the closed form formula for the n-th term of our sequence as

$F_{n}=-4\left ( \ C_{1}\left ( \frac{1+\sqrt{5}}{2} \right )^{n}+C_{2}\left ( \frac{1-\sqrt{5}}{2} \right )^{n}\ \right ) (3)$

where $C_{1}$ and $C_{2}$ are constant parameters determined by our initial conditions,

$F_{0}=-4$ and $F_{1}=5$

We can calculate these values by solving the following system of equations

$F_{0} = -4\times t^{0}=-4 \left ( C_{1}\times t_{1}^{0} + C_{2}\times t_{2}^{0} \right )$

$F_{1} = -4\times t^{1}=-4 \left ( C_{1}\times t_{1}^{1} + C_{2}\times t_{2}^{1} \right )$

Plugging in known values gives us

$-4 = -4 \left (C_{1} \left ( \frac{1+\sqrt{5}}{2} \right )^{0} + C_{2} \left ( \frac{1-\sqrt{5}}{2} \right )^{0} \right )$

$5 = -4 \left (C_{1} \left ( \frac{1+\sqrt{5}}{2} \right )^{1} + C_{2} \left ( \frac{1-\sqrt{5}}{2} \right )^{1} \right )$

Simplifying turns the above into

$1 = C_{1} \left ( \frac{1+\sqrt{5}}{2} \right )^{0} + C_{2} \left ( \frac{1-\sqrt{5}}{2} \right )^{0} = C_{1} + C_{2} \ (4)$

$\frac{-5}{4} = C_{1} \left ( \frac{1+\sqrt{5}}{2} \right ) + C_{2} \left ( \frac{1-\sqrt{5}}{2} \right ) \ (5)$

Now we need to solve $(4)$ and $(5)$ for $C_{1}$ and $C_{2}$. Although I said I was going to leave matrices alone, this is a perfect situation to use them. I prefer to use the procedure described below for a system of two equations with coefficients such as these. Substitution or elimination method would, of course, work, but they involves messy arithmetic which can be so easily error prone in situations such as this one.

We have the following system:

$\begin{pmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix}C_{1}\\ C_{2}\end{pmatrix} = \begin{pmatrix}1\\ \frac{-5}{4}\end{pmatrix}\ (6)$

In general, to solve the equation

$Au=v$

we use

$A^{-1}Au=A^{-1}v$

which turns into

$u=A^{-1}v$

Hence, to solve $(6)$ we need to find the inverse of our matrix. This is fairly simple for a 2 by 2 matrix … Let

$A=\begin{pmatrix}a & b\\ c & d\end{pmatrix}$

then

$A^{-1}=\frac{1}{ad-bc}\begin{pmatrix}d & -b\\ -c & a\end{pmatrix}$

and so

$\begin{pmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \end{pmatrix}^{-1} =\frac{-1}{\sqrt{5}}\begin{pmatrix} \frac{1-\sqrt{5}}{2} & -1 \\ \frac{-1-\sqrt{5}}{2} & 1 \end{pmatrix}$

Our equation $(6)$ then becomes

$\begin{pmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \end{pmatrix}^{-1}\begin{pmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix}C_{1}\\ C_{2}\end{pmatrix} = \begin{pmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \end{pmatrix}^{-1} \begin{pmatrix}1\\ \frac{-5}{4}\end{pmatrix}$

$\begin{pmatrix}C_{1}\\ C_{2}\end{pmatrix} = \frac{-1}{\sqrt{5}}\begin{pmatrix} \frac{1-\sqrt{5}}{2} & -1 \\ \frac{-1-\sqrt{5}}{2} & 1 \end{pmatrix} \begin{pmatrix}1\\ \frac{-5}{4}\end{pmatrix}$

which gives us

$C_{1}=\frac{-2(1-\sqrt{5})-5}{4\sqrt{5}}\ (7)$

$C_{2}=\frac{2(1+\sqrt{5})+5}{4\sqrt{5}}\ (8)$

Finally, by plugging $(7)$ and $(8)$ into $(3)$ we get

$F_{n}=-4\left (\left ( \frac{-2(1-\sqrt{5})-5}{4\sqrt{5}} \right )\left ( \frac{1+\sqrt{5}}{2} \right )^{n}+\left ( \frac{2(1+\sqrt{5})+5}{4\sqrt{5}} \right )\left ( \frac{1-\sqrt{5}}{2} \right )^{n}\right ) (9)$

We can now “easily” compute $F_{386}$ which is given by

$F_{386}=-4\left (\left ( \frac{-2(1-\sqrt{5})-5}{4\sqrt{5}} \right )\left ( \frac{1+\sqrt{5}}{2} \right )^{386}+\left ( \frac{2(1+\sqrt{5})+5}{4\sqrt{5}} \right )\left ( \frac{1-\sqrt{5}}{2} \right )^{386}\right )$

Google returns $F_{386} \cong 5.2783459\times 10^{80}$ which is just an approximation, but now we have a formula for the precise answer.

If you wish to check for yourself that out formula $(9)$ is indeed correct, click on the terms below to see the computation by Google:

$F_{0}=-4$

$F_{1}=5$

$F_{2}=1$

$F_{3}=6$

$F_{4}=7$

$F_{5}=13$

On a side note – Raising a number to the power of 386 may seem like a long computation but it really requires only 10 multiplications! Don’t believe me?

Consider this:

$\left ( \frac{1+\sqrt{5}}{2} \right )^{386}=\left ( \frac{1+\sqrt{5}}{2} \right )^{256}\left ( \frac{1+\sqrt{5}}{2} \right )^{128}\left ( \frac{1+\sqrt{5}}{2} \right )^{2}$

To calculate

$\left ( \frac{1+\sqrt{5}}{2} \right )^{256}$

we use the fact that

$1.)\ \left ( \frac{1+\sqrt{5}}{2} \right )^{2} = \left ( \frac{1+\sqrt{5}}{2} \right )\left ( \frac{1+\sqrt{5}}{2} \right )$

$2.)\ \left ( \frac{1+\sqrt{5}}{2} \right )^{4} = \left ( \frac{1+\sqrt{5}}{2} \right )^{2} \left ( \frac{1+\sqrt{5}}{2} \right )^{2}$

$3.)\ \left ( \frac{1+\sqrt{5}}{2} \right )^{8} = \left ( \frac{1+\sqrt{5}}{2} \right )^{4} \left ( \frac{1+\sqrt{5}}{2} \right )^{4}$

$8.)\ \left ( \frac{1+\sqrt{5}}{2} \right )^{256} = \left ( \frac{1+\sqrt{5}}{2} \right )^{128} \left ( \frac{1+\sqrt{5}}{2} \right )^{128}$

As you can see, in every step (multiplication) we use the result from the previous one and so it takes only 8 steps (multiplications) to calculate

$\left ( \frac{1+\sqrt{5}}{2} \right )^{256}$

Finally, in the process of calculating

$\left ( \frac{1+\sqrt{5}}{2} \right )^{256}$

we get

$\left ( \frac{1+\sqrt{5}}{2} \right )^{128}$ and $\left ( \frac{1+\sqrt{5}}{2} \right )^{2}$

as a bonus, and so to calculate

$\left ( \frac{1+\sqrt{5}}{2} \right )^{386}$

we now only need to use two more multiplications

$\left ( \frac{1+\sqrt{5}}{2} \right )^{386}=\left ( \frac{1+\sqrt{5}}{2} \right )^{256}\left ( \frac{1+\sqrt{5}}{2} \right )^{128}\left ( \frac{1+\sqrt{5}}{2} \right )^{2}$

This idea can be generalized to any

$x\epsilon \Re$

The (maximal) number of multiplications required to compute

$x^{n}\ where\ 2^{p}

is given by

$p+(p+1) = 2p + 1$

To put this result in a little bit of perspective, consider

$x = 2^{43112609}-1$

This number is the currently largest known (Mersenne) prime. It has 12,978,189 digits! But $log_{2}(43112609)\cong 25.36$ and so

$2^{25}< 43112609\leq2^{26}$

It follows that we can calculate

$2^{43112609}-1$

using at most 51 multiplications! Incredible!