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 f_{n} denote the number of rabbit pairs at the beginning of month n, then we have
f_{0}=1, f_{1}=1, f_{2}=2, f_{3}=3, f_{4}=5,... (Look at the diagram above) and, in general,
fn=f_{n-1}+f_{n-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, f_{n} |
n, f_{n} |
n, f_{n} |
n, f_{n} |
n, f_{n} |
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 R^{n} 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 A^{k}=PD^{k}P^{-1} for any power k. What about D^{k} ? Remember that D has the form
_{}
so it is not difficult to see that D^{k} 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^{-1}AP=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=f_{n-1}+f_{n-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 f_{n} itself. The relation fn=f_{n-1}+f_{n-2} gives
_{}
where
_{}
is the same matrix studied above. Using the relation
_{}
we have
_{}
_{}
But A^{n}=PD^{n}P^{-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 n^{th} Fibonacci term:
_{}
Is it now easy to compute the 100^{th} term of the Fibonacci sequence:
_{}
A powerful calculator shows the value 573147844013817084101 for f_{100}.
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!