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

### 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

(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/
```
Associated Topics:
High School Fibonacci Sequence/Golden Ratio

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