Tiny Volt18. Fibonacci numbers
Power iteration showed that repeatedly applying a matrix to a vector drives it toward the eigenvector of 's largest eigenvalue, because and the dominant eigenvalue swamps the rest. This chapter cashes that idea out on a sequence every programmer knows.
If you write code, you have almost certainly met the Fibonacci numbers, and probably written a function to compute the -th one by iteration or recursion. Here we look at them through a linear-algebra lens, which reveals a closed-form formula and connects them to the broader family of linear recurrence relations.
18.1 Fibonacci numbers
The Fibonacci numbers are a sequence defined by , , and
The textbook recursive implementation follows the definition directly:
def fibonacci(n):
if n == 0: return 0
if n == 1: return 1
return fibonacci(n - 1) + fibonacci(n - 2)
18.2 Two consecutive Fibonacci numbers as a vector
Now pack two consecutive Fibonacci numbers into a 2D vector:
This gives , , , and so on.
18.2.1 What is the direction of this vector?
The direction of is the angle . As grows, does this ratio of consecutive Fibonacci numbers converge? If it does, then the direction of settles down too, and (just like power iteration) that limiting direction is the eigenvector of the largest eigenvalue of some matrix. Let's watch it happen before we find the matrix.
Reveal , the line of slope . Now plot the Fibonacci vectors one at a time: , , , , and . Each vector is longer than the last, but their directions zig-zag in and lock onto the violet line: the ratio converges to .
18.3 The recurrence relation
The trick is to express as a matrix-vector product . Finding is easy:
So . Since , , and in general , the vector points toward 's dominant eigenvector for large , exactly the convergence we just saw. Let's find its eigenvalues and eigenvectors.
If is an eigenvalue of , then is singular, so its columns are parallel and its determinant vanishes:
This is precisely the equation that defines the golden ratio.
- The eigenvalues are and .
- The corresponding eigenvectors are and .
Since is the larger absolute eigenvalue, for large the vector points in the direction . In other words, for large the ratio .
18.3.1 Deriving Binet's formula
The eigendecomposition of is
Because , and using , we can compute in closed form:
Reading off the first entry gives Binet's formula for the -th Fibonacci number:
18.4 Generalizing to any linear sum of the last two values
This chain of reasoning is not special to Fibonacci: it works for any sequence where each term is a linear combination of the previous two. A slightly more general version is
Here the same packing gives
with . The remaining steps are identical: find the eigenvalues and eigenvectors of this matrix, then use its eigendecomposition to write the -th value in closed form.
18.5 Linear recurrence relations
The most general version of this idea is a linear recurrence relation:
where the and are constants. The approach is unchanged in spirit: stack the last terms into a vector
and find a matrix (plus a constant vector to absorb the term) so that . Once again the powers of , through its eigendecomposition, carry all the information about how the sequence grows.
Another place higher powers of a matrix show up is Markov chains, where repeatedly applying a transition matrix drives a probability distribution toward a steady state. We look at them next.