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  where         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  then          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         Hence         Back to the Linear Algebra Home Page