Ben wrote a nice post deriving an explicit formula for the 
- view the
Fibonacci numbers as components of a vector
- write down a matrix that takes us from
to
- find its eigenvalues and eigenvectors
- write down
in this basis
- exponentiate the matrix and multiply to
- read off the Fibonacci numbers
We start by defining the Fibonacci recurrence relation by
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].](http://l.wordpress.com/latex.php?latex=%5Cleft%5B+%5Cbegin%7Barray%7D%7Bcc%7D+0+%26+1+%5C%5C+1++%26+1%5Cend%7Barray%7D%5Cright%5D+%5Cleft%5B%5Cbegin%7Barray%7D%7Bc%7DF_%7Bn-1%7D%5C%5CF_n%5Cend%7Barray%7D%5Cright%5D+%3D+%5Cleft%5B%5Cbegin%7Barray%7D%7Bc%7DF_n%5C%5CF_%7Bn%2B1%7D%5Cend%7Barray%7D%5Cright%5D.&bg=ffffff&fg=000000&s=0 "\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,
which implies
The characteristic polynomial of 
The eigenvectors are
![\left[\begin{array}{c}1\\ \lambda_+ \end{array}\right], \qquad \left[\begin{array}{c}1\\ \lambda_- \end{array}\right].](http://l.wordpress.com/latex.php?latex=%5Cleft%5B%5Cbegin%7Barray%7D%7Bc%7D1%5C%5C+%5Clambda_%2B+%5Cend%7Barray%7D%5Cright%5D%2C+%5Cqquad+%5Cleft%5B%5Cbegin%7Barray%7D%7Bc%7D1%5C%5C+%5Clambda_-+%5Cend%7Barray%7D%5Cright%5D.&bg=ffffff&fg=000000&s=0 "\left[\begin{array}{c}1\\ \lambda_+ \end{array}\right], \qquad \left[\begin{array}{c}1\\ \lambda_- \end{array}\right].")
Which I’ll denote by 
Multiplying by 
The top component of that vector equation gives
More generally, the symmetry of
![\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]](http://l.wordpress.com/latex.php?latex=%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D+%5Cfrac%7B1%7D%7B%5Csqrt%7B1%2B%5Clambda_%2B%5E2%7D%7D+%26+%5Cfrac%7B%5Clambda_%2B%7D%7B%5Csqrt%7B1%2B%5Clambda_%2B%5E2%7D%7D+%5C%5C+%5Cfrac%7B1%7D%7B%5Csqrt%7B1%2B%5Clambda_-%5E2%7D%7D+%26+%5Cfrac%7B%5Clambda_-%7D%7B%5Csqrt%7B1%2B%5Clambda_-%5E2%7D%7D+%5Cend%7Barray%7D%5Cright%5D+%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D+%5Crule%7B0pt%7D%7B3ex%7D+0+%26+1+%5C%5C+%5Crule%7B0pt%7D%7B4ex%7D1+%26+1+%5Cend%7Barray%7D%5Cright%5D%5Ep+%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D+%5Cfrac%7B1%7D%7B%5Csqrt%7B1%2B%5Clambda_%2B%5E2%7D%7D+%26+%5Cfrac%7B1%7D%7B%5Csqrt%7B1%2B%5Clambda_-%5E2%7D%7D+%5C%5C+%5Cfrac%7B%5Clambda_%2B%7D%7B%5Csqrt%7B1%2B%5Clambda_%2B%5E2%7D%7D+%26+%5Cfrac%7B%5Clambda_-%7D%7B%5Csqrt%7B1%2B%5Clambda_-%5E2%7D%7D+%5Cend%7Barray%7D%5Cright%5D+%3D+%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D+%5Clambda_%2B%5Ep+%26+0+%5C%5C+0+%26+%5Clambda_-%5Ep+%5Cend%7Barray%7D%5Cright%5D&bg=ffffff&fg=000000&s=0 "\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]](http://l.wordpress.com/latex.php?latex=%5Cmathbf%7BM%7D%5Ep+%3D++%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D+%5Cfrac%7B1%7D%7B%5Csqrt%7B1%2B%5Clambda_%2B%5E2%7D%7D+%26+%5Cfrac%7B1%7D%7B%5Csqrt%7B1%2B%5Clambda_-%5E2%7D%7D+%5C%5C+%5Cfrac%7B%5Clambda_%2B%7D%7B%5Csqrt%7B1%2B%5Clambda_%2B%5E2%7D%7D+%26+%5Cfrac%7B%5Clambda_-%7D%7B%5Csqrt%7B1%2B%5Clambda_-%5E2%7D%7D+%5Cend%7Barray%7D%5Cright%5D++++%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D+%5Crule%7B0pt%7D%7B3ex%7D+%5Clambda_%2B%5Ep+%26+0+%5C%5C+%5Crule%7B0pt%7D%7B4ex%7D+0+%26+%5Clambda_-%5Ep+%5Cend%7Barray%7D%5Cright%5D+++%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7D+%5Cfrac%7B1%7D%7B%5Csqrt%7B1%2B%5Clambda_%2B%5E2%7D%7D+%26+%5Cfrac%7B%5Clambda_%2B%7D%7B%5Csqrt%7B1%2B%5Clambda_%2B%5E2%7D%7D+%5C%5C+%5Cfrac%7B1%7D%7B%5Csqrt%7B1%2B%5Clambda_-%5E2%7D%7D+%26+%5Cfrac%7B%5Clambda_-%7D%7B%5Csqrt%7B1%2B%5Clambda_-%5E2%7D%7D+%5Cend%7Barray%7D%5Cright%5D&bg=ffffff&fg=000000&s=0 "\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
Tags: Fibonacci, linear algebra
July 17, 2009 at 5:14 am
[...] I wrote up a derivation of the formula for this number here. [...]