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]


\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


Tags: ,

One Response to “Linear Algebra and the Fibonacci Sequence”

  1. Answer: Flight Of Stairs « Arcsecond Says:

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: