Fibonacci Numbers and Linear Operators - psholtz/MIT-SICP GitHub Wiki

Exercise 1.19

The "clever algorithm" used in Exercise 1.19 for computing Fibonacci numbers should be familiar to students of linear algebra. Referring, for example, to Exercise 4.2.9 in the text Linear Algebra Done Wrong, available from the Math Department at Brown University, we encounter a very similar problem statement in relation to computing matrix eigenvalues.

Linear Algebra Done Wrong - Exercise 4.2.9

Let us recall that the famous Fibonacci sequence:

[ 0, 1, 1, 2, 3, 5, 8, 13, 21, ... ]

is defined as follows:

img

We want a formula for the n-th Fibonacci number:

(a) Find a 2 x 2 matrix A such that:

img

(b) Diagonalize A and find a formula for the n-th power of A.

(c) Noticing that

img

find a formula for the n-th Fibonacci number.

(d) Show that the vector

img

converges to an eigenvector of A.

Linear Algebra Done Wrong - Solution 4.2.9

It's worthwhile to work through this example, both for its own merits, and also to understand in more depth the procedure we designed in SICP Exercise 1.19.

The linear operator A can easily be derived as follows:

img

To diagonalize A, we must calculate its eigenvalues, and verify that the algebraic multiplicity of each eigenvalue is equal to its geometric multiplicity. The characteristic equation of A is given by:

img

and hence we determine that the two distinct eigenvalues of A are:

img

The algebraic and geometric multiplicity of each eigenvalue is 1, and so the matrix can be diagonalized.

Knowing this, we know that the operator A can be expressed as a diagonal matrix as follows:

img

where the column vectors of P are the eigenvectors of the linear operator A.

If we wish to obtain a representation for the inversion matrix P, we may proceed as follows:

A representative eigenvector, chosen from the eigenspace corresponding to the eigenvalue lambda(1), is:

img

Similarly, a representative eigenvector chosen from the eigenspace corresponding to the eigenvalue lambda(2) is:

img

So that the inversion matrix we are seeking can be expressed succinctly as:

img

so that:

img

From here, it may be easily verified that:

img

Since the eigenvalues lambda are solutions to the characteristic equation, the off-diagonal elements reduce to 0.

Similarly, bearing in mind that:

img

we have:

img

so that:

img

and likewise

img

so that:

img

Hence we have that:

img

To obtain an expression for A^n, we write:

img

Furthermore, since:

img

We can now obtain our expression for A^n as follows:

img

Since we showed above that:

img

we can now use this expression to find an expression for the n-th Fibonacci number as follows:

img

From which we obtain the following expression for the n-th Fibonacci number:

img

Let's try out this expression for a few Fibonacci numbers, to see if it holds up:

img

Clearly, the expression holds up.

If we "re-index" the n-th Fibonacci number to begin with 0 rather than 1, we obtain the following expression for the n-th Fibonacci number:

img

Compare this with the expression utilized in Exercise 1.13.

Finally, let us consider the following expression:

img

and consider further that:

img

for all positive n, so that:

img

and so that:

img

Hence the vector

img

converges to the vector

img

which we already proved was an eigenvector of the operator A.

Home