This page contains two proofs of the formula for the Fibonacci numbers. The first is probably the simplest known proof of the formula. The second shows how to prove it using matrices and gives an insight (or application of) eigenvalues and eigenlines.

A simple proof that Fib(n) = (Phin – (–Phi)–n)/√5

[Adapted from Mathematical Gems 1 by R Honsberger, Mathematical Assoc of America, 1973, pages 171-172.]

Reminder:

First look at the Summary at the end of the Fascinating Facts and Figures about Phi page.
If we use -phi instead of phi, we get a single formula that covers all powers of both Phi and -phi:

Phi1 = 0 + 1 Phi = 1·6180339.. and (-phi)1 = 0 + 1 (-phi) = -0·6180339..
Phi2 = 1 + 1 Phi = 2·6180339.. and (-phi)2 = 1 + 1 (-phi) = 0·3819660..
Phi3 = 1 + 2 Phi = 4·2360679.. and (-phi)3 = 1 + 2 (-phi) = -0·2360679..
Phi4 = 2 + 3 Phi = 6·8541019.. and (-phi)4 = 2 + 3 (-phi) = 0·1458980..
Phi5 = 3 + 5 Phi = 11·0901699.. and (-phi)5 = 3 + 5 (-phi) = -0·0901699..
...
Since Phi and -phi are the two roots of x2=x+1, we can summarise the table above as follows:
If x2=x+1 then xn = fib(n) x + fib(n-1) for n>0.
You can either assume this is always true based on the initial examples in the table or, you can prove it.
An easy way to prove this result is by induction, if you have covered that method in your maths classes. I'll leave this as an exercise for you!

We can easily show that the two roots of x2=x+1 are Phi = (1+sqrt(5))/2 = 1·6180339... and -phi = (1-sqrt(5))/2 = -0·6180339.... and thus that these are the only two values for which their powers can be expressed as Fibonacci multiples of themselves, as given in the formula.

So, from the formula above, we have:

Phin = fib(n) Phi + fib(n-1) (A)
and also
(-phi)n = fib(n) (-phi) + fib(n-1) (B)
Subtracting (B) from (A) gives:
Phin - (-phi)n = fib(n)(Phi - (-phi))(C)
and from this we derive an initial formula for fib(n):
fib(n) = 
n
Phi
n
 – (phi)

Phi – (–phi)
But Phi-(-phi)=sqrt(5), so we can write this as:
fib(n) = 
n
Phi
n
 – (phi)

sqrt5
To get the form of the formula which involves only Phi, we replace phi by 1/Phi so that
n
(–phi)
 = 
n
(–1* phi )
 = 
–n
(
1

(–1 * phi )
)
 =  
–n
(
–1

phi 
)
 = 
–n
(–Phi)
The formula for fib(n) is now:
fib(n) = 
n
Phi
–n
 – (Phi)

sqrt5

A proof using Matrices

This proof uses matrices and gives a practical application of - or introduction to - eigenvalues and eigenlines. It is optional and only recommended for those who have used matrices before.
All you need to know is what a matrix is and how they multiply.

Back in the Rabbits field...

Returning to Fibonacci's original rabbits problem, let's enumerate how many mature rabbit pairs there are each month and how many immature pairs (1 month old):
  month:    1  2  3  4  5     
  mature:      1  1  2  3  ...   
  young:    1     1  1  2  ...   
  TOTAL:    1  1  2  3  5  ...
  

Explanation:

The young pair are introduced into the field and are immature in month 1.
They become mature in month 2.
They give birth to a new pair in month 3.
In month 4, all those that were "young" the previous month become "mature", together with those who were "mature" from the previous month, so the top entry is the sum of the two entries in the column of the previous month.
The number of young in any month is just the number of pairs that were mature the previous month, so we just copy the top entry to the bottom of the next column. These two processes are summarized in this diagram:
  month:    ...  n    n+1 ...
  mature:   ...  M    M+Y ...  the top entry is the TOTAL of the previous month
  young:    ...  Y     M  ...  the bottom entry is the TOP entry of the previous month
  TOTAL:    ... M+Y  2M+Y ...
  
If f(n) is the total number of pairs in month n, then it is the sum of the mature in month n plus the young in month n. The number of mature pairs is the total of the previous month, ie f(n-1). The number of young is the same as the top entry of the previous month which is also the total of the month-before-that, ie f(n-2). Hence f(n)=f(n-1)+f(n-2). Since f(1)=1, f(2)=1 then we have the Fibonacci numbers (but starting from n=1 not n=0):
  month:    ...   n      n+1    ...
  mature:   ... f(n-1)   f(n)   ...
  young:    ... f(n-2)  f(n-1)  ...
  TOTAL:    ...  f(n)   f(n+1)
  
We can summarise the columns as follows:
  
  adults in month n+2:      f(n+1)=f(n)+f(n-1)
   young in month n+2:      f(n)
  
or, written in matrix form:
( f(n+1))
f(n)
 = 
( 1  1 )
10
( f(n) )
f(n–1)
Replacing n by (n-1) in the equation above gives a matrix formula for the vector on its right hand side.
( f(n) )
f(n–1)
 = 
( 1  1 )
10
( f(n–1) )
f(n–2)
If we substitute this back in to the first formula, we have:
( f(n+1))
f(n)
 = 
( 1  1 )
10
( f(n) )
f(n–1)
 = 
( 1  1 )
10
( 1  1 )
10
( f(n–1) )
f(n–2)
 = 
2
( 1  1 )
10
( f(n–1) )
f(n–2)
We can keep on doing this, each time getting ahigher power of the 2-by-2 matrix until eventually we get right back to the original month 0 and month 1 (i.e. the unit vector):
( f(n+1) )
f(n)
 = 
n
( 1  1 )
10
(1)
0
 = 
n
M
(1)
0
You will see that we have called the matrix M. We need to find its n-th power if we are to determine f(n+1) and f(n). Raising a matrix to the n-th power is a lot of work! Fortunately, matrix algebra comes to the rescue and provides a quick way of evaluating it with very little work.

What is a formula for the n-th power of this matrix?

If we can find a formula for the n-th power of M, we have a formula for f(n).
There is a useful method that applies to matrices to find such a formula.
If we can write matrix M as the product of 3 matrices: Q D Q-1, where D is a matrix whose only entries are on its main diagonal, then Mn is
Mn = (Q D Q-1)(Q D Q-1)...(Q D Q-1)
All the Q.Q-1 terms nicely cancel out so we get
Mn = Q Dn Q-1
What is the advantage of the new form - we still need to find Dn?
The answer is that since D is in diagonal form then its powers are easy to work out:
D = 
n
( a 0)
0 b 
 = 
( an 0)
0 bn 

Eigenvalues

The entries we need for D are the eigenvalues of M, found by solving this equation:
0 = det 
( 1–k 1)
1 0–k 
 = (1–k)(0–k) – 1*1  =  k2 – k – 1
There are two values for k, k=Phi and k=–phi. So the D matrix can be
(Phi0)
0-phi

What about Q?

Now we've found D as a matrix in diagonal form, what about Q? This is defined by the eigenlines of our original matrix M, that is, for eigenvalues a and b ( ours were a=Phi and b=-1/Phi ) we want to solve:
(1 1
1 0
)(x
y
)=(ax
ay
)   (1 1
1 0
)(x
y
)=(bx
by
)
giving y=x/a and y=x/b. From this we can "invent" a matrix Q as follows:
(11)
1/a1/b
Its determinant is (a-b)/ab which is just -sqrt(5) for our values of a and b so we can form the inverse of Q:
Q–1 = (a/√51/√5)
–b/√5–1/√5
Now we can write our matrix M in the Q D Q-1 form:
(1 1
1 0
) = Q(a 0
0 b
) Q-1
So we have
(1 1
1 0
)n = Q(an 0
0 bn
) Q-1
Looking back, we had:
(f(n+1)
f(n)
) = (1 1
1 0
)n(1
0
)
Now we replace Mn by Q Dn Q-1 and multiply out the matrices:
(f(n+1))
f(n)
 = 
n
( 1  1 )
10
(1)
0
 = 
( 1  1 )
1

a
1

b
(an0)
0bn
)
  
 a 

sqrt5
   
 1 

sqrt5
  
)
–b

sqrt5
 –1

sqrt5
(1)
0
 = 
)
  
an+1 – bn+1

sqrt5
  
)
an – bn

sqrt5
So the vector on the left is equal to the vector on the right. Both top and bottom components give the same formula, but the top has (n+1) in place of the n in the bottom one. Finally, then, we have it - our formula for f(n):
f(n) = an – bn where a = Phi = Phi = 1+sqrt5  and b = –phi = –phi = 1–sqrt5

sqrt
5

2

2

See also:
Article: A Primer on the Fibonacci Sequence - Part II by S L Basin, V E Hoggatt Jr in Fibonacci Quarterly vol 1, pages 61 - 68 for more examples of how to derive Fibonacci formulae using matrices.


WHERE TO NOW???

FIB Home Fibonacci Home PageCalculator

Return Return to A Formula for the Fibonacci Numbers


Valid HTML 4.01! © 1996-2003 Dr Ron Knott email
updated 30 October 2003