Associated Topics || Dr. Math Home || Search Dr. Math

### Calculating the Fibonacci Sequence

```
Date: 11/28/96 at 04:16:17
From: Louis Suhendra
Subject: Fibonacci sequence

Is there a formula that can be used to calculate the nth Fibonacci
number?

For example, if we want to know the 100th Fibonacci number, do we have
to count one by one?
```

```
Date: 12/11/96 at 21:39:10
From: Doctor Rob
Subject: Re: Fibonacci sequence

The answer to the first question is, "Yes, but ..."  The answer to the
second question is, "No."  Now for the explanations!  Sorry they are
so long.

The standard formula for the Fibonacci numbers is due to a French
mathematician named Binet.  If F(n) represents the nth Fibonacci
number, then:

F(n) = (a^n - b^n)/(a - b)

where a and b are the two roots of the quadratic equation x^2-x-1 = 0.
It is not obvious how to derive this formula, but it is easy to prove
that it satisfies F(0) = 0, F(1) = 1, and satisfies the same recursion
as the Fibonacci numbers do.  We can use the quadratic formula to see
that a = (1 + Sqrt[5])/2 and b = (1 - Sqrt[5])/2, so a - b = Sqrt[5].
According to this formula:

F(3) = (a^3 - b^3)/(a - b)
= a^2 + a*b + b^2
= [(1 + Sqrt[5])^2 + (1 + Sqrt[5])*(1 - Sqrt[5]) +
(1 - Sqrt[5])^2]/4
= [1 + 2*Sqrt[5] + 5 + 1 - 5 + 1 - 2*Sqrt[5] + 5]/4
= 8/4
= 2

You might not guess that the formula always produces an integer for
each value of n, but such is the case.

Unfortunately, computing with this formula is not very easy!  Luckily,
there is another way.  We use the recursion F(n+1) = F(n) + F(n-1) and
the starting values F(0) = 0, F(1) = 1.  We also use an auxiliary
sequence called the Lucas numbers, which we will denote by L(n).  They
are defined by L(0) = 2, L(1) = 1, and L(n+1) = L(n) + L(n-1).  Their
Binet formula is:

L(n) = a^n + b^n

with the same a and b as before.  We need the following formulas, too:

F(n+1) = [F(n) + L(n)]/2
L(n+1) = [5*F(n) + L(n)]/2

We also use the following "doubling formulas":

F(2*n) = F(n)*L(n),
L(2*n) = L(n)^2 - 2(-1)^n

We compute in sequence the pairs (F[k], L[k]) for k = 0, 1, 2, 3, 6,
12, 24, 25, 50, and 100:

k   F(k) L(k)
0   0    2
1   1    1
2   1    3
3   2    4
6   8    18
12  144  322
and so on

You can do the same kind of computations for any size value of n, no
matter how large.  Now what is the value of F(100)?  And why did we
choose the sequence of values of k given above?

If you want to learn more, take a look at the Math Forum's FAQ on the
Golden Ratio and the Fibonacci Sequence:

http://mathforum.org/dr.math/faq/faq.golden.ratio.html

-Doctor Rob,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
High School Fibonacci Sequence/Golden Ratio
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search