Recursive Sequences and Fibonacci Sequences


In this discussion we will see how matrices can be used to describe recursive sequences, in particular Fibonacci numbers.  Recall that a recursively defined sequence is a sequence where the first one or more values are given along with a formula that relates the nth term to the previous terms.  The Fibonacci sequence is defined as follows:

        un  =  un - 1 + un - 2       u0  =  1        u1  =  1

We can find the Fibonacci numbers by using the formula

        u2  =  u1 + u0  =  1 + 1  =  2

        u3  =  u2 + u1  =  2 + 1  =  3

        u4  =  u3 + u2  =  3 + 2  =  5

        u5  =  u4 + u3  =  5 + 3  =  8

These numbers occur in several disciplines and wherever you don't expect them in mathematics.  For example suppose one mating pair of rabbits is introduced into an ecosystem.  This breed of rabbits produce a pair of rabbits after their second month of life and all months after that.  Assume no rabbits die.  Then the zeroth  and first month, there is one pair of rabbits.  On the second month there will be two pairs:  the original pair plus their children.  The third month there will three pairs:  the two pairs from second month plus the children from the original pair.  If we want to find out how many rabbits on the nth month, we add the number of rabbits from the prior month and the number of children.  Since only two month old rabbits can have children, we only add the rabbits that were there two months ago.  This is the Fibonacci sequence.

We can see how each number is produced, however if we want to find the 1000th Fibonacci number this way, it would be exhausting.  We now show how matrices can be used to produce Fibonacci numbers more efficiently.  We can write the following two equations:

        un      =  un - 1 + un - 2 
        un - 1  =  un - 1 

This has matrix equation


We can write this as

        wk  =  Awk - 1 



Notice that 

        w1  =  Aw0 
        w2  =  Aw1  =  AAw0  =  A2 w0

In general, we have 

        wk  =  Ak w0

We now seek a fancy way to find a power of a matrix.  The answer comes with diagonalization.  We have that if A is diaogonalizable with

        A  =  PDP-1 


        Ak  =  PDkP-1

We can diagonalize this matrix with 


The nth Fibonacci number can be found by 


If you carefully multiply this out and take the first component of the result, we get


Hence the 1000th Fibonacci number is 


This number is extremely large.

Other Sequences

We can play this same game with modified rules.  For example, if the mature rabbits had six pairs of children instead of one, then the recursion relationship would be

        un  =  un - 1 + 6un - 2       u0  =  1        u1  =  1

and the matrix equation would be


and we would use a similar technique to find a general formula for un.  In this case, we have


So that




Back to the Vectors Home Page

Back to the Linear Algebra Home Page

Back to the Math Department Home Page

e-mail Questions and Suggestions