## Binets Formula for the nth Fibonacci number

We have only defined the nth Fibonacci number in terms of the two before it:

the n-th Fibonacci number is the sum of the (n-1)th and the (n-2)th. So to calculate the 100th Fibonacci number, for instance, we need to compute all the 99 values before it first -quite a task, even with a calculator! A natural question to ask therefore is:

Can we find a formula for F(n) which involves only n and does not need any other (earlier) Fibonacci values?

Yes! It involves our golden section number Phi and its reciprocal phi: Here it is:

V5 V5

where Phi = 161803 39887 49894 84820 45868 34365 63811 77203 09179 80576 ... .

The next version uses just one of the golden section values: Phi, and all the powers are positive:

Since phi is the name we use for 1/Phi on these pages, then we can remove the fraction in the numerator here and make it simpler, giving the second form of the formula at the start of this section.

We can also write this in terms of -V5 since Phi =-and -phi =-:

If you prefer values in your formulae, then here is another form:-

2.236067977..

This is a surprising formula since it involves square roots and powers of Phi (an irrational number) but it always gives an integer for all (integer) values of n!

Here's how it works:

Let X= Phin =(1-618..)n and Y=(-Phi)"n=(-1-618..)"n=(-0-618..)n then we have:

 n: X= Phin : Y= (-Phi)-n : X- Y: (X- 0 1 1 0 0 1 1- 618033989 -0 •61803399 2- 23606798 1 2 2- 618033989 0 •38196601 2- 23606798 1 3 4- 236067977 -0 •23606798 4- 47213595 2 4 6- 854101966 0 •14589803 6- 70820393 3 5 11 •09016994 -0 •09016994 11- 18033989 5 6 17 •94427191 0 •05572809 17- 88854382 8

7 29-03444185 -0-03444185 29-06888371 13

8 46-97871376 0-02128624 46-95742753 21

9 76-01315562 -0-01315562 76-02631123 34 10 122-9918694 0-00813062 122-9837388 55

You might want to look at two ways to prove this formula: the first way is very simple and the second is more advanced and is for those who are already familiar with matrices.

Since phi is less than one in size, its powers decrease rapidly. We can use this to derive the following simpler formula for the n-th Fibonacci number F(n):

where the round function gives the nearest integer to its argument.

 n: Phin/sqrt(5) ..rounded 0 0-447213595 0 1 0-723606798 1 2 1-170820393 1 3 1-894427191 2 4 3-065247584 3 5 4-959674775 5 6 8-024922359 8 7 12-98459713 13 8 21-00951949 21 9 33-99411663 34 10 55-00363612 55

Notice how, as n gets larger, the value of Phin/V5 is almost an integer.

1. What then is F(100) according to this formula? You may choose to write a computer program for this, or use a package (such as Mathematica or Maple) which lets you work out very long integers exactly, or you can just get an approximate value on your calculator.

2. How many digits does F(100) have? (the approximate value on your calculator should tell you). Check your answer with the list of Fibonacci numbers.

3. Look at the following line from the last Table above:

1 1-618033989 -0-61803399 2-23606798 1

You might nave noticed that we didn't ADD the X and Y values to get 1-618..-0-618..=1 directly but instead we subtracted and divided by sqrt(5).

Let's see what happens if we do just ADD the X and Y columns:

(a) Add a new column to the table above which is X+Y. Fill it in and you'll notice something very surprising - another integer series that is not the Fibonacci numbers!! These numbers are called the Lucas Numbers and they also have some similar properties to the Fibonacci numbers and are covered in another page at this site (see Fibonacci Home page).

(b) Can you spot the rule whereby the latest two Lucas numbers are used to generate the next Lucas number?