Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/