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/