The Fibonacci Sequence from Its Companion Matrix

From a Recurrence to a Matrix

The Fibonacci sequence is generated by a rule that uses the two preceding terms. A matrix can encode that rule in a single multiplication, so repeated multiplication produces successive pairs of terms. Diagonalizing the matrix then turns those repeated multiplications into powers of its eigenvalues. This gives an explicit formula for the \(n\)th term rather than a step-by-step recurrence.

We use the indexing \(F_0=0\), \(F_1=1\), and \(F_{n+2}=F_{n+1}+F_n\) for every integer \(n\geq 0\). All scalars and matrices in this tutorial are real. The order of the two entries in the state vector matters: define \(\mathbf{x}_n\) to list the later term first.

Using the recurrence, the next state is \(\mathbf{x}_{n+1}=\begin{bmatrix}F_{n+2}\\F_{n+1}\end{bmatrix}=\begin{bmatrix}F_{n+1}+F_n\\F_{n+1}\end{bmatrix}\). The coefficients in these two entries give the companion matrix \(\mathbf{C}\):

In particular, \(\mathbf{x}_n=\mathbf{C}^n\mathbf{x}_0\). This follows by applying the one-step rule repeatedly; the exponent \(n\) counts the number of updates from \(\mathbf{x}_0\). The first entry of \(\mathbf{x}_n\) is \(F_{n+1}\), while the second is \(F_n\).

Proof. At \(n=0\), \(\mathbf{C}^0\mathbf{x}_0=\mathbf{I}_2\mathbf{x}_0=\mathbf{x}_0=\begin{bmatrix}F_1\\F_0\end{bmatrix}\), as required. Suppose for some \(n\geq0\) that \(\mathbf{x}_n=\begin{bmatrix}F_{n+1}\\F_n\end{bmatrix}\). Then \(\mathbf{C}\mathbf{x}_n=\begin{bmatrix}F_{n+1}+F_n\\F_{n+1}\end{bmatrix}=\begin{bmatrix}F_{n+2}\\F_{n+1}\end{bmatrix}=\mathbf{x}_{n+1}\). Thus, if \(\mathbf{x}_n=\mathbf{C}^n\mathbf{x}_0\), then \(\mathbf{x}_{n+1}=\mathbf{C}^{n+1}\mathbf{x}_0\). Induction proves the formula for all \(n\geq0\). \(\square\)

Eigenvalues and Eigenvectors of the Companion Matrix

To diagonalize \(\mathbf{C}\), first solve the eigenvector equation \(\mathbf{C}\mathbf{v}=\lambda\mathbf{v}\) for a nonzero vector \(\mathbf{v}\). For a vector of the form \(\begin{bmatrix}\lambda\\1\end{bmatrix}\), direct multiplication gives \(\mathbf{C}\begin{bmatrix}\lambda\\1\end{bmatrix}=\begin{bmatrix}\lambda+1\\\lambda\end{bmatrix}\). This equals \(\lambda\begin{bmatrix}\lambda\\1\end{bmatrix}\) precisely when \(\lambda+1=\lambda^2\). The resulting equation \(\lambda^2-\lambda-1=0\) has two distinct real roots.

Both roots satisfy \(\lambda^2=\lambda+1\), so each produces an eigenvector. Put these eigenvectors into the columns of \(\mathbf{P}\). The two columns are independent because the determinant of \(\mathbf{P}\) is \(\phi-\psi=\sqrt{5}\ne0\); hence \(\mathbf{P}\) is invertible. The computations below give a diagonalization without requiring a general diagonalizability criterion.

Since \(\mathbf{P}\) is invertible, multiplying the last identity on the right by \(\mathbf{P}^{-1}\) gives \(\mathbf{C}=\mathbf{P}\mathbf{D}\mathbf{P}^{-1}\). Repeating this factorization yields \(\mathbf{C}^n=\mathbf{P}\mathbf{D}^n\mathbf{P}^{-1}\) for every \(n\geq0\). For \(n=0\), both sides equal \(\mathbf{I}_2\); for positive \(n\), adjacent factors \(\mathbf{P}^{-1}\mathbf{P}\) cancel, leaving \(\mathbf{P}\mathbf{D}^n\mathbf{P}^{-1}\).

Deriving the Closed Formula

The inverse of \(\mathbf{P}\) is particularly simple because its determinant is \(\sqrt{5}\):

Applying this inverse to the initial state, and then multiplying by the diagonal powers and by \(\mathbf{P}\), gives the full state in terms of \(\phi\) and \(\psi\).

The second coordinate of \(\mathbf{x}_n\) is \(F_n\), so the expression for that coordinate is the closed formula. It is valid starting at \(n=0\), not just for positive indices.

Proof. The diagonalization above gives \(\mathbf{x}_n=\dfrac{1}{\sqrt{5}}\left(\phi^n\begin{bmatrix}\phi\\1\end{bmatrix}-\psi^n\begin{bmatrix}\psi\\1\end{bmatrix}\right)\) for each \(n\geq0\). By definition, the second coordinate of \(\mathbf{x}_n\) is \(F_n\). Taking the second coordinate of the displayed vector therefore gives \(F_n=(\phi^n-\psi^n)/\sqrt{5}\), as claimed. The argument includes \(n=0\): the formula gives \((1-1)/\sqrt{5}=0=F_0\). \(\square\)

Worked Checks: Recurrence, Matrix, and Formula

Common Pitfall: Keep the State Order Consistent

The companion matrix depends on how the state entries are ordered. With our convention, the state is \(\begin{bmatrix}F_{n+1}\\F_n\end{bmatrix}\), and the update matrix is \(\begin{bmatrix}1&1\\1&0\end{bmatrix}\). A wrong calculation is to use that same matrix with the reversed initial state \(\begin{bmatrix}F_0\\F_1\end{bmatrix}=\begin{bmatrix}0\\1\end{bmatrix}\):

This result is not the next reversed-order state, which should be \(\begin{bmatrix}F_1\\F_2\end{bmatrix}=\begin{bmatrix}1\\1\end{bmatrix}\). The correction is to use the matching matrix for that order: if \(\mathbf{y}_n=\begin{bmatrix}F_n\\F_{n+1}\end{bmatrix}\), then \(\mathbf{y}_{n+1}=\begin{bmatrix}0&1\\1&1\end{bmatrix}\mathbf{y}_n\). Indeed, multiplying \(\begin{bmatrix}0&1\\1&1\end{bmatrix}\begin{bmatrix}0\\1\end{bmatrix}\) gives \(\begin{bmatrix}1\\1\end{bmatrix}\), as required. Either convention works, but the state, update matrix, and initial vector must all agree.

A second potential error is to assume that \(\begin{bmatrix}1\\\lambda\end{bmatrix}\) is an eigenvector of \(\mathbf{C}\) for an eigenvalue \(\lambda\). In fact, \(\mathbf{C}\begin{bmatrix}1\\\lambda\end{bmatrix}=\begin{bmatrix}1+\lambda\\1\end{bmatrix}\), which is generally not \(\lambda\begin{bmatrix}1\\\lambda\end{bmatrix}\). For the chosen matrix, the correct eigenvector is \(\begin{bmatrix}\lambda\\1\end{bmatrix}\); its eigenvector equation works because the root satisfies \(\lambda^2=\lambda+1\).

Why the Diagonalization Helps

The recurrence is an efficient way to generate terms one at a time, but it requires retaining earlier values. The matrix form organizes those values as a state, and diagonalization explains how the state changes after many updates: each eigenvector component is multiplied by a power of its eigenvalue. In this example the initial state contributes to both eigenvectors, and the second coordinate of their combined powers yields the Fibonacci formula. The formula is useful for understanding the sequence and for checking exact values; the recurrence remains convenient for computing a short list of consecutive terms.