The Linear Algebra View of the Fibonacci Sequence

The Fibonacci sequence is a beautiful mathematical concept, making surprise appearances in everything from seashell patterns to the Parthenon.

It’s easy to write down the first few terms — it starts with 0, 1, 1, 2, 3, 5, 8, 13, with each term equal to the sum of the previous two.

But what about the 100th or 100,000th term? Can we find them without doing thousands of calculations?

In this post I’ll explain how a simple linear model can help us see the “long run” values of the Fibonacci sequence. The result is an elegant expression that illustrates the connection between the Fibonacci sequence and the so-called “golden ratio”, an aesthetic principle appearing throughout art, architecture, music, book design and more.

Setting Up the Model

Each term in the Fibonacci sequence equals the sum of the previous two. That is, if we let Fn denote the nth term in the sequence we can write

To make this into a linear system, we need at least one more equation. Let’s use an easy one:

Putting these together, here’s our system of linear equations for the Fibonacci sequence:

We can write this in matrix notation as the following:

Here’s what this is saying. If we start with the vector on the right and multiply it by this 2 x 2 matrix, the result is the vector on the left. That is, multiplying our starting vector by the matrix above gives us the next element in the sequence.

The n-1 element from the right becomes the n element on the left, and the n-2 element becomes the n-1 element. Each time we multiply by this matrix we’re moving the system from one term of the Fibonacci sequence to the next.

The general form for dynamic linear models like this is:

where u0 is the initial state, u1 is the final state, and A is the transformation matrix that moves us from one state to the next. We can use eigenvalues and eigenvectors to solve for the long run values of systems like this.

Here’s how we do that. Let S be a 2 x 2 matrix where the columns are the two eigenvectors of our transformation matrix A. And let

be a 2 x 2 matrix with the two eigenvalues of A along the diagonal and zeros elsewhere. By the definition of eigenvalues and eigenvectors, we have the following identity:

Solving for A, we have:

Plugging this into our above equation relating u0 and u1, we have the following system:

This equation relates the initial state vector u0 to the next state u1. But each time we multiply by A it moves us to the next state, and the next state, and so on. Imagine we multiply k times. We get the following general form:

This equation is what we’re looking for. It allows us to quickly find the kth term in the Fibonacci sequence with a simple calculation. It relies only on the initial state vector u0 and the eigenvalues and eigenvectors of the transformation matrix A. That’s our linear model.

Putting the Pieces Together

Now that we have a model, let’s find the S,

and other parts that make it up. The first step is to find the eigenvalues of the A matrix. This is given by:

We find the eigenvalues by solving Ax = lambda x for the vector lambda that makes that equation true (that’s the definition of an eigenvalue). That’s the same as solving Ax — lambda x = 0, or (A — lambda)x = 0. This implies the matrix (A — lambda) is singular or not invertible. So the determinant of (A — lambda) must be zero. That means we can find the eigenvalues by setting the determinant of (A — lambda) equal to zero and solving for lambda (this is called the “characteristic polynomial”).

Here’s how we do that:

Plugging this into the quadratic formula with a = 1, b = -1 and c = -1, you’ll get the following two solutions, which are our two eigenvalues:

For a quick check that these are right, note that the trace of A is 1. The sum of the two eigenvalues is also 1. Since the eigenvalues must always sum to the trace, we’ve got the right values here.

The next step is to find the two eigenvectors that correspond to the eigenvalues. Let’s start with

To do this, we write the following:

This implies that

Our “free” variable here is x2, so we’ll let that equal 1. Then we can solve for x1. We get the following:

Using the old algebra trick for the difference of squares — that is,

— we can simplify this by multiplying both numerator and denominator by

as follows:

So our first eigenvector v1 is equal to:

Following the same process for

give us the other eigenvector:

Note that the vectors v1 and v2 are orthogonal to each other. That is, the dot product between them is zero. This comes from a basic theorem of linear algebra: every symmetric matrix will have orthogonal eigenvectors. Since A is symmetric, our two eigenvectors are perpendicular to each other.

Now that we have the eigenvalues and eigenvectors, we can write the S and

matrices as follows:

To complete our model, we also need to know the inverse of the S matrix. Thankfully, there’s a simple formula for the inverse of a 2 x 2 matrix. If A is given by:

then the inverse of A is found by transposing the diagonal terms, putting a negative sign on the off-diagonal terms, and multiplying by 1/(determinant of A), or

Using that formula, we get:

As explained in our earlier post, our final step is to write our initial state vector u0 as a combination of the columns of S. That is, we can write:

where c is a 2 x 1 vector of scalars. Solving for c, we get:

For this example, let’s let our initial state vector u0 be (1,1). These are the second and third terms of the Fibonacci sequence. Note that you can use any two subsequent terms for this step — I’m just using (1,1) because I like the way the math works for it. So we have:

Since

that means

The Result

Putting everything together, we can write our final model for the Fibonacci sequence:

Multiplying this out, we get the following extensive form of the model:

This equation gives the k+3 and k+2 terms of the Fibonacci sequence as a function of just one variable: k.

This allows us to easily find any term we’d like — just plug in k. For example, imagine we want the 100th term. Simply let k = 98, and solve the above for F101 and F100.

This is a huge number, by the way — 218,922,995,834,555,000,000 — something you can easily verify in this Excel spreadsheet. (Note that whether this is the 99th or 100th term depends on whether you label 0 or 1 to be the first term of the sequence; here I’ve made zero the first term, but many others use 1.)

Some Analysis

So what happens to the above system as k grows very large? Do the terms in the Fibonacci sequence display some regular pattern as we move outward? All changes from one term to the next are determined by k in the above model. Imagine k grows very large. In the second term in the equation, we can see that

That means that as k gets bigger, the second term in the equation goes to zero. That leaves only the first term. That means as

So as k grows large, the ratio of the k+1 to the k term in the Fibonacci sequence approaches a constant, or

This is a pretty amazing result. As we move far out in the Fibonacci sequence, the ratio of two subsequent terms approaches a constant. And that constant is equal to the first eigenvalue of our linear system above.

More importantly, this value is also equal to the famous “golden ratio”, which appears in myriad forms throughout Western art, architecture, music and more. In the limit, the ratio of subsequent terms in the Fibonacci sequence equals to the golden ratio — something that’s not obvious at all, but which we can verify analytically using our model above.