500th Fibonacci Number

Date: 04/16/97 at 12:16:29
From: Dung Che Che
Subject: Fibonacci numbers

Dear Dr. Math,

I was hoping you could help me figure out an extra credit math 
problem. My calculus teacher has challenged us to find the 500th term 
of the Fibonacci sequence. In high school, I figured out the 100th 
term by adding on my calculator, but this seems to be more of a 
challenge. So if you could maybe give me a formula and some 
instructions, I would greatly appreciate it.

Thank you for your time.

Date: 04/18/97 at 10:39:43
From: Doctor Rob
Subject: Re: Fibonacci numbers

This is quite challenging, since the answer has 105 decimal digits!  
There are two ways to proceed.

(1) Use Binet's formula for the Fibonacci numbers, drop the small 
    term, and round.

    Fibonacci numbers are defined by F(0) = 0, F(1) = 1, and

    (F)  F(n+1) = F(n) + F(n-1) for n > 1.

    Binet's formula says that:

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

    where 

    a = (1 + Sqrt[5])/2
    b = (1 - Sqrt[5])/2

    Observe that a - b = Sqrt[5], a + b = 1, and a*b = -1.

    You can actually prove that this formula is correct by showing 
    that F(0) = (a^0 - b^0)/(a - b), F(1) = (a^1 - b^1)/(a - b), and 
    that (a^n - b^n)/(a - b) satisfies the same recursion that F(n) 
    does. Then apply the principle of mathematical induction to 
    conclude that the Binet formula holds for all nonnegative n.

    This may seem impossible, but all of the Sqrt[5] terms evaporate 
    when the formula is expanded, and the result is, in fact, an 
    integer.

    Furthermore, since -1 < b < 0, it turns out that
       |b^n/Sqrt[5]| < 1/2 
    for all nonnegative n, so it is true that:

    F(n) ~=~ a^n/Sqrt[5]

    If you can compute the quantity on the right to 110 significant 
    figures, then rounding it off to the nearest integer will give 
    your answer.

(2) Use the doubling formulas for Fibonacci and Lucas numbers.

    Lucas numbers are defined as follows:  L(0) = 2, L(1) = 1, and

    (L)  L(n+1) = L(n) + L(n-1) for n > 1

    There is also a Binet formula for them:

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

    a and b are the same as defined above.

    Since a + b = 1, we could write L(n) = a^n + b^n.

    You can also prove this formula using mathematical induction.

    Fibonacci and Lucas numbers satisfy the following identities, 
    which you can prove using the principle of mathematical induction, 
    or directly using the Binet Formulas:

    (A)  F(2*n) = F(n)*L(n)
    (B)  L(2*n) = L(n)^2 - 2*(-1)^n
    (C)  F(n+1) = (F(n) + L(n))/2
    (D)  L(n+1) = (5*F(n) + L(n))/2
    (L')  L(n) = L(n+1) - L(n-1)

    To compute F(500), use (A) and the values of F(250) and L(250).
    To compute F(250), use (A) and the values of F(125) and L(125).
    To compute L(250), use (B) and the value of L(125).
    To compute F(125), use (C) and the values of F(124) and L(124).
    To compute L(125), use (D) and the values of F(124) and L(124).
    To compute F(124), use (A) and the values of F(62) and L(62).
    To compute L(124), use (B) and the value of L(62).
    To compute F(62), use (A) and the values of F(31) and L(31).
    To compute L(62), use (B) and the value of L(31).
    To compute F(31), use (C) and the values of F(30) and L(30).
    To compute L(31), use (D) and the values of F(30) and L(30).
    To compute F(30), use (A) and the values of F(15) and L(15).
    To compute L(30), use (B) and the value of L(15).
    To compute F(15), use (C) and the values of F(14) and L(14).
    To compute L(15), use (D) and the values of F(14) and L(14).
    To compute F(14), use (A) and the values of F(7) and L(7).
    To compute L(14), use (B) and the value of L(7).
    To compute F(7), use (C) and the values of F(6) and L(6).
    To compute L(7), use (D) and the values of F(6) and L(6).
    To compute F(6), use (A) and the values of F(3) and L(3).
    To compute L(6), use (B) and the value of L(3).

    You can compute directly that F(3) = 2, L(3) = 4. Now work your 
    way back up the chain above, computing F(n) and L(n) for 
    n = 6, 7, 14, 15, 30, 31, 62, 124, 125, and 250, then F(500).

    As a check, F(500) starts off 13942...  and ends  ...94125.

    Alternatively, since you already know F(100), you could compute
    L(n) using (B) for the even n's and (L') for the odd n's in the 
    sequence n = 2, 3, 4, 6, 8, 7, 12, 14, 13, 24, 26, 25, 50, and 
    100. Then use the additional identity

        (E)  F(5*n) = F(n)*[L(n)^4 - 3*(-1)^n*L(n)^2 + 1]

    with n = 100.  You can prove this directly from the Binet
    formulae.

Good question!

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/