Ben wrote a nice post deriving an explicit formula for the Fibonnaci number using a generating function. Here’s a complementary approach using some ideas from linear algebra. The approach is

- view the and Fibonacci numbers as components of a vector
- write down a matrix that takes us from to
- find its eigenvalues and eigenvectors
- write down in this basis
- exponentiate the matrix and multiply to
- read off the Fibonacci numbers

We start by defining the Fibonacci recurrence relation by

.

The trick is to notice that we can re-cast this equation in matrix form.

More abstractly, in notation I hope explains itself,

,

which implies

.

The characteristic polynomial of is whose roots are . I’ll denote those values by and .

The eigenvectors are

Which I’ll denote by and . Writing in terms of these we have

Multiplying by gives

The top component of that vector equation gives

More generally, the symmetry of tells us that its eigenvectors are orthogonal, and so normalizing them we have the unitary change of basis

or

.

That would allow us to start with any and write

### Like this:

Like Loading...

*Related*

Tags: Fibonacci, linear algebra

This entry was posted on June 2, 2009 at 5:17 pm and is filed under math. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

July 17, 2009 at 5:14 am

[…] I wrote up a derivation of the formula for this number here. […]