# Application to a probleme of Fibonacci Introduction In 1202, an Italian mathematician known as Fibonacci posed the following problem: A male and a female rabbit are born at the beginning of the year. We assume the following conditions:

1.      After reaching the age of two months, each pair produces a mixed pair, (one male, one female), and then another mixed pair each month thereafter.

2.      No deaths occur during the year.

How many rabbits will there be at the end of the year?

Let fn denote the number of rabbit pairs at the beginning of month n, then we have

f0=1, f1=1, f2=2, f3=3, f4=5,... (Look at the diagram above) and, in general,

fn=fn-1+fn-2.

In other words, every term in this sequence (starting with n=2) is equal to the sum of the previous two terms. The sequence {1,1,2,3,5,8,13,21,34…} generated according to this scheme was named in honour of Fibonacci. This sequence occurs in many places in mathematics, general science, in nature and even in art.

The following table gives the first 55 Fibonacci numbers:

 n, fn n, fn n, fn n, fn n, fn 1, 1 12, 144 23, 28657 34, 5702887 45, 1134903170 2, 1 13, 233 24, 46368 35, 9227465 46, 1836311903 3, 2 14, 377 25, 75025 36, 14930352 47, 2971215073 4, 3 15, 610 26, 121393 37, 24157817 48, 4807526976 5, 5 16, 987 27, 196418 38, 39088169 49, 7778742049 6, 8 17, 1597 28, 317811 39, 63245986 50, 12586260925 7, 13 18, 2584 29, 514229 40, 102334155 51, 20365011074 8, 21 19, 4181 30, 832040 41, 165580141 52, 32951280099 9, 34 20, 6765 31, 1346269 42, 267914296 53, 53316291173 10, 55 21, 10946 32, 2178309 43, 433494437 54, 86267571272 11, 89 22, 17711 33, 3524578 44, 701408733 55, 139583862445

In particular, at the end of the first year (n=12), there will 144 rabbits.

As you can see, the Fibonacci numbers get bigger and bigger. To have an idea about these numbers beyond n=55, click here.

A natural question would be: can we find an expression that gives fn for any n? The answer is yes if one knows a little bit about matrix diagonalization. So let us recall some basic facts about this topic..

Definition For a square nxn matrix A, a scalar λ is called an eigenvalue for A if there exists a nonzero vector X of Rn satisfying AX= λX. In this case, we say that X is an eigenvector of A corresponding to the eigenvalue λ.

Example Let then .

Therefore, the vector is an eigenvector for the matrix A corresponding to the eigenvalue (1+√5)/2.

Given a square nxn matrix A, the eigenvalues of A are the solutions to the equation where |A- λ I| means the determinant of the matrix A- λ I and I is the identity matrix of the same size as A.

Example For the matrix A in the previous example, Solving the above equation gives the two eigenvalues What about the eigenvectors of A?

If  X is an eigenvector of A corresponding to the eigenvalue λ, then AX= λX. In other words, (A- λI)X=0. This means that every eigenvector of A is a solution of the homogeneous system  (A- λI)X=0.

We define the eigenspace E λ corresponding to the eigenvalue λ to be the set of all eigenvector of λ together with the zero vector. In other words, E λ is the solution set to the homogeneous system (A- λI)X=0.

To see how this works, let us take again the matrix A of our previous examples. To find the eigenvectors of A corresponding to the eigenvalue λ1=(1+√5)/2, we solve the system which is equivalent to and the general solution is This shows in particular that the vector is a basis for Eλ1. Similarly, one can show that the vector is a  basis for the eigenspace Eλ2. In particular dim (Eλ1) + dim (Eλ2)=2.

Definition a square matrix is called diagonal if all its entries are zero except, perhaps, the entries on the main diagonal. A square matrix A is called diagonalizable if there exists an invertible matrix P of the same size satisfying for some diagonal matrix D. (we say that A is similar to a diagonal matrix).

Why are we interested in diagonalizable matrices? For one, powers of diagonalizable matrices are easy to compute. Here’s how it works :

If A is diagonalizable, then A=PDP-1 for some invertible matrix P and diagonal matrix D. Let’s try to compute some powers of A: In general, one can see that Ak=PDkP-1 for any power k. What about Dk ? Remember that D has the form so it is not difficult to see that   Dk   will have the form Therefore, computing the powers of a diagonalizable matrix is an easy task once we know the matrices P and D in the formula .

The following Theorem gives an algorithm for diagonalization.

Theorem  Let A be an nxn matrix, and let λ1,…, λk be the distinct (real) eingenvalues of A. We have the following:

1.      A is diagonalizable if and only if dim (Eλ1) +…+ dim (Eλk)=n.

2.      If A is diagonalizable with P-1AP=D, then the columns of P are basis vectors for the eigenspaces of A and the diagonal entries of D are the corresponding eigenvalues.

Let us consider again the matrix above and apply this diagonalization algorithm to it. Since we showed above that dim (Eλ1) + dim (Eλ2)=2, we know now that A is diagonalizable. Let be the matrix whose columns are the basis vectors of the eigenspaces found above. Then The above Theorem gives the following decomposition of A: Let us now see how all this can be applied to answer our problem about the rabbits of Fibonacci. The general pattern for the Fibonacci sequence was:

fn=fn-1+fn-2.

A general expression for fn is not apparent, but a clever twist transforms the problem into a simpler one using matrices. The idea is to compute the vector for each n ≥ 0 rather than fn  itself. The relation fn=fn-1+fn-2 gives where is the same matrix studied above. Using the relation we have  But  An=PDnP-1  where are as above. Therefore, for all n ≥ 0. In this formula the last vector is If you carefully multiply this out and take the first component of the result, you get the nth Fibonacci term: Is it now easy to compute the 100th term of the Fibonacci sequence: A powerful calculator shows the value 573147844013817084101 for f100.

Note that the number is one of the most mysterious numbers,  and is widely known as the golden ratio. It has this name since a rectangle with sides s and Φs has a pleasing shape, possibly because of the fact that if you fold the smaller side (of length s) into the rectangle, dividing into a square of side s and a rectangle with sides s and s(1- Φ), this smaller rectangle is similar to the one you began with!