## Linear Algebra and the Fibonacci Sequence

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

1. view the $n^{th}$ and $(n+1)^{\mathrm{th}}$ Fibonacci numbers as components of a vector $\mathbf{x}_n$
2. write down a matrix that takes us from $\mathbf{x}_n$ to $\mathbf{x}_{n+1}$
3. find its eigenvalues and eigenvectors
4. write down $\mathbf{x}_0$ in this basis
5. exponentiate the matrix and multiply to $\mathbf{x}_0$
6. read off the Fibonacci numbers

We start by defining the Fibonacci recurrence relation by

$F_{n+1} = F_n + F_{n-1}$.

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

$\left[ \begin{array}{cc} 0 & 1 \\ 1 & 1\end{array}\right] \left[\begin{array}{c}F_{n-1}\\F_n\end{array}\right] = \left[\begin{array}{c}F_n\\F_{n+1}\end{array}\right].$

More abstractly, in notation I hope explains itself,

$\mathbf{M}\mathbf{x}_{n-1} = \mathbf{x}_n$,

which implies

$\mathbf{M}^p\mathbf{x}_0 = \mathbf{x}_p$.

The characteristic polynomial of $\mathbf{M}$ is $\lambda^2 - \lambda - 1$ whose roots are $\frac{1}{2}(1 \pm \sqrt{5})$. I’ll denote those values by $\lambda_+$ and $\lambda_-$.

The eigenvectors are

$\left[\begin{array}{c}1\\ \lambda_+ \end{array}\right], \qquad \left[\begin{array}{c}1\\ \lambda_- \end{array}\right].$

Which I’ll denote by $\mathbf{e}_+$ and $\mathbf{e}_-$. Writing $\mathbf{x}_0$ in terms of these we have

$\mathbf{x}_0 = \frac{1}{\sqrt{5}}(\mathbf{e}_+ - \mathbf{e}_-)$

Multiplying by $\mathbf{M}^p$ gives

$\begin{array}{rcl} \mathbf{M}^p \mathbf{x}_0 & = & \mathbf{x}_p \\ & = & \mathbf{M}^p \frac{1}{\sqrt{5}} \left(\mathbf{e}_+ - \mathbf{e}_-\right) \\ & = & \frac{1}{\sqrt{5}}(\lambda_+^p \mathbf{e}_+ - \lambda_-^p \mathbf{e}_-) \end{array}$

The top component of that vector equation gives

$F_p = \frac{1}{\sqrt{5}}\left({\lambda_+^p - \lambda_-^p}\right)$

More generally, the symmetry of $\mathbf{M}$ tells us that its eigenvectors are orthogonal, and so normalizing them we have the unitary change of basis

$\left[\begin{array}{cc} \frac{1}{\sqrt{1+\lambda_+^2}} & \frac{\lambda_+}{\sqrt{1+\lambda_+^2}} \\ \frac{1}{\sqrt{1+\lambda_-^2}} & \frac{\lambda_-}{\sqrt{1+\lambda_-^2}} \end{array}\right] \left[\begin{array}{cc} \rule{0pt}{3ex} 0 & 1 \\ \rule{0pt}{4ex}1 & 1 \end{array}\right]^p \left[\begin{array}{cc} \frac{1}{\sqrt{1+\lambda_+^2}} & \frac{1}{\sqrt{1+\lambda_-^2}} \\ \frac{\lambda_+}{\sqrt{1+\lambda_+^2}} & \frac{\lambda_-}{\sqrt{1+\lambda_-^2}} \end{array}\right] = \left[\begin{array}{cc} \lambda_+^p & 0 \\ 0 & \lambda_-^p \end{array}\right]$

or

$\mathbf{M}^p = \left[\begin{array}{cc} \frac{1}{\sqrt{1+\lambda_+^2}} & \frac{1}{\sqrt{1+\lambda_-^2}} \\ \frac{\lambda_+}{\sqrt{1+\lambda_+^2}} & \frac{\lambda_-}{\sqrt{1+\lambda_-^2}} \end{array}\right] \left[\begin{array}{cc} \rule{0pt}{3ex} \lambda_+^p & 0 \\ \rule{0pt}{4ex} 0 & \lambda_-^p \end{array}\right] \left[\begin{array}{cc} \frac{1}{\sqrt{1+\lambda_+^2}} & \frac{\lambda_+}{\sqrt{1+\lambda_+^2}} \\ \frac{1}{\sqrt{1+\lambda_-^2}} & \frac{\lambda_-}{\sqrt{1+\lambda_-^2}} \end{array}\right]$.

That would allow us to start with any $\mathbf{x}_0$ and write $\mathbf{x}_p = \mathbf{M}^p\mathbf{x}_0$