The Fibonacci Sequence and Generalizations

Source:

        Under the conditions of the problem, the total number of pairs of rabbits one year later will be 233. The entries in the last column of Table 1 are the first thirteen members of the Fibonacci sequence.

II. The Fibonacci Sequence in Matrix Form   

        Although the recursion definition in the introduction gives a complete description of the Fibonacci sequence, it is not particularly useful if we are interested in finding an arbitrary Fibonacci number yk. For example, if we want to compute y1000 using the definition, we shall need to compute all 999 members that precede it. Therefore, we derive an explicit formula for the kth Fibonacci number as a function of k by solving the recurrence relation in matrix form.

        Let us modify the original definition by adding the following trivial equation:

                                        yk+1 = yk+1                                                                        (2)

                                                            yk+2 = yk+1 + yk 

        

        This system of equations can be written in matrix form by letting,

     and    

and noticing the relation,

,

we can rewrite the matrix equation in the general form:

                                                             uk+1 = Auk                                             (3)

The vector uk can be written in terms of u0 by noting the relation,

u1 = Au0

u2 = Au1 = A2u0 

u3 = Au2 = A3u0

                                         .

                                .

                                uk = Aku0                

Since yk is the top entry in uk and the matrices A and u0 are known, we can readily use this equation to find an arbitrary Fibonacci number. For example, y5 can be computed from the equation u5 = A5u0:  

However, this formula is useful in practice only if we can find a convenient way to compute Ak for higher values of k. Diagonalization of A provides a possible solution to this practical problem.

 First, in order to determine whether A is diagonalizable, we derive and solve the characteristic equation of A:

                                                          (4)

 ,

Next we solve for the eigenvectors,

                                                                                                   (5)

For λ1,

For λ2,

        Since the 2x2 matrix A has two distinct eigenvalues, it follows that A is diagonalizable and there exist a diagonal matrix D and an invertible matrix P, such that:

                                                                    ,                                  (6)

where ,  and  are constructed as follows:

,          

Since A is diagonalizable,  can be easily computed by applying the formula:

                                                       ,                              (7)

In this way computations are significantly facilitated since  is a diagonal matrix and computing   does not pose any serious technical difficulties.

From equation (5), we can derive a general formula for in terms of  and .  

,

Multiplying the three matrices out and simplifying yields,

                                (8)

From equation (6), the k-th Fibonacci number can be found from the relation,

 =

Hence, = (). Using the fact that the two eigenvalues have the property,, the expression forsimplifies to:

= ()=               (9)

The formula above was discovered in 1843 by the French mathematician J.P.M.Binet (1786-1856) and is known today in the literature as the Formula of Binet.

The second term of Binet’s formula is less than one in absolute value, so as k gets progressively larger, it will approach zero. Therefore,

                                                                                   (10)

Hence, the sequence of ratios of consecutive Fibonacci numbers () is convergent and its limit is given by:

                                               (11)

 

The limit  is called the Golden Mean, and has been regarded since ancient times as the aesthetically ideal ratio of width to height for a rectangle. It is commonly reflected in natural objects which grow by a linear increment (e.g. snail shells, sunflowers, and in great many other places).

III. Generalizations of the Fibonacci sequence. Lucas sequence.

The Fibonacci sequence is a special type of a broader class of recurrence relations that occur frequently in applied mathematics. A k-th order linear homogenous recurrence relation is a relation of the form:

                                                    ,                     (12)

where .

In particular, the Fibonacci sequence is a second order sequence with =1 and =1.

The analysis applied for the Fibonacci sequence in section II can be readily generalized for any second order linear recurrence relation with constant coefficients of the form:

                                                          ,                         (13)

where c1 and c2 are non zero constants. A sequence derived from this equation is often called a Lucas sequence. It is an interesting question to explore whether the method we used for deriving the formula for yk of the Fibonacci sequence can be applied to find a similar formula for yk  of the Lucas sequence.

Let us start with several examples:

1. Consider the following Lucas sequence:

                                                             yk+2=3yk+1-2yk,                                             (14)

where y0=0 and y1=1.

The first few terms generated by the equation above are 0, 1, 3, 7, 15, 31, 63…..

In order to find an explicit formula for yk , we can repeat the same method we used for deriving the formula of Binet for the Fibonacci sequence.

First, we add the trivial equation:

                                                         yk+1 = yk+1                                                             (15)

                                                         yk+2 = 3yk+1 -2yk

By letting,

       and    

and noting,

                         A =  = = uk+1                      (16)

the system of equations (15) can be written in matrix form as

       

                                       uk+1 = Auk                                               (17)

The vector uk could be written in terms of u0 by noting that

                                              uk = Auk-1 = AAuk-2=…..=Aku0                             (18)

As in the case for the Fibonacci sequence, the main goal is to find a general formula for  Ak by possibly diagonalizing A.

In order to diagonalize A, we derive and solve the characteristic equation of A:

 = 0                    (19)

                                                     

Since A has two distinct eigenvalues, it is diagonalizable and can be expressed in the form   for some invertible matrix P and a diagonal matrix D. In fact, the columns of P are the eigenvectors of A corresponding to  and , and the non-zero entries in D are the two eigenvalues.

The eigenvectors corresponding to the two eigenvalues are computed as follows.

For

For

Let us construct:

       and ,

Since A is diagonalizable,

 =  = ,    (20)

From equation (16),

                      (21)

Hence,

                                                               =                                                (22)

In order to verify the obtained formula, we plug in k = 0, 1, 2, 3, 4.. in () and get 0, 1, 3, 7, 15.., which are exactly the first few terms of the Lucas sequence defined in example 1. In this case, the method used to obtain the formula for the Fibonacci sequence works well and yields an explicit formula for the k-th term of the Lucas sequence.

However, let us consider the following example:

2. Consider the following Lucas sequence generated by the equation:

                                                               yk+2 = 2yk+1-yk,                                                            (23)

     where y0 = 0 and y1 = 1.

The first few terms this sequence are 0, 1, 3, 7, 15, 31, 63…..

Following the same steps as in example 1, the equation above can be also written in matrix form. Let

       and     A =

Then,

                           A =  = = uk+1 ,                  (24)

Hence equation (23) can be stated compactly as

                                                                 uk+1 = Auk ,                                              (25)

or alternatively as

                                                                 uk =Aku0                                                                            (26)

 In order to diagonalize A, we solve its characteristic equation,

                                    (27)

Since the 2x2 matrix A has only one distinct eigenvalue with multiplicity 2, it follows that A is not diagonalizable. Therefore, there is no general formula for Ak and hence for yk.

From the two examples above we can derive the following two conclusions about our matrix method for solving second order recurrence relations:

1. If the characteristic equation of A has two distinct solutions, then A is diagonalizable and we can derive an explicit formula for yk.
2. If the characteristic equation of A has less than two distinct solutions, then A is not diagonalizable and our method for deriving yk cannot be applied.

More formally, our conclusions are consistent with the following more general theorem:

Theorem: Let γ and δ be the distinct solutions of the equation, where and b ≠ 0. Then every solution of the linear homogenous recurrence relation with constant coefficients, where a0 = C0 and a1 = C1, is of the form

for some constants A and B. 

IV. Conclusion

This paper discussed how linear algebra can be applied to the analysis of linear recurrence relations, a number of which arise frequently in applied and pure math. In particular, it emphasized the concepts of eigenvalues and eigenvectors and how helpful they are in describing and understanding infinite sequences of integers.    

Bibliography:

---