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!