Computing Fibonacci Numbers

Deriving Binet's Formula

From before, we have that $M^n \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} F(n + 1) \\ F(n) \end{pmatrix}$. From this we can derive that $F(n)$ is equal to the bottom left element of $M^n$. In fact, in general we have $$M^n = \begin{pmatrix} F(n + 1) & F(n) \\ F(n) & F(n - 1) \end{pmatrix}$$

(Proof left as an exercise to the reader!)

We can use our diagonalization to find a closed form for this value: let the number crunching commence! (I'm writing it out here for pedagogical purposes, but in the real world I am 100% using a computer to do all of this math for me.)

$$\begin{aligned} M^n &= PD^nP^{-1} \\ &= \begin{pmatrix} \phi & \psi \\ 1 & 1 \end{pmatrix} \begin{pmatrix}\phi^n & 0 \\ 0 & \psi^n \end{pmatrix} \left[\frac{1}{\sqrt{5}} \begin{pmatrix} 1 & -\psi \\ -1 & \phi \end{pmatrix}\right] \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi & \psi \\ 1 & 1 \end{pmatrix} \begin{pmatrix}\phi^n & 0 \\ 0 & \psi^n \end{pmatrix} \begin{pmatrix} 1 & -\psi \\ -1 & \phi \end{pmatrix} \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi & \psi \\ 1 & 1 \end{pmatrix} \begin{pmatrix}\phi^n & -\psi \phi^n \\ -\psi^n & \phi \psi^n \end{pmatrix} \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi^{n+1} - \psi^{n+1} & -\psi \phi^{n+1} + \phi \psi^{n+1} \\ \phi^n - \psi^n & \phi \psi^n - \psi \phi^n \end{pmatrix} \\ \end{aligned}$$

To simplify further, we can use a special property of the golden ratio to rewrite $\psi$ in terms of $\phi$: $$\begin{aligned} -\frac{1}{\phi} &= \frac{-2}{1 + \sqrt{5}} \\ &= \frac{-2(1 - \sqrt{5})}{(1 + \sqrt{5})(1 - \sqrt{5})} \\ &= \frac{-2(1 - \sqrt{5})}{-4} \\ &= \frac{1 - \sqrt{5}}{2} \\ &= \psi \end{aligned}$$

This lets us simplify further:

$$\begin{aligned} M^n &= PD^nP^{-1} \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi^{n+1} - \psi^{n+1} & -\psi \phi^{n+1} + \phi \psi^{n+1} \\ \phi^n - \psi^n & \phi \psi^n - \psi \phi^n \end{pmatrix} \\ &= \frac{1}{\sqrt{5}} \begin{pmatrix} \phi^{n+1} - \psi^{n+1} & \phi^{n} - \psi^{n} \\ \phi^n - \psi^n & \phi^{n-1} - \psi^{n-1} \end{pmatrix} \\ \end{aligned}$$

Remember, $F(n)$ is the bottom-left element.¹ So, at long last, we have a closed form for $F(n)$:

$$\boxed{F(n) = \frac{\phi^n - \psi^n}{\sqrt{5}}}$$

🥳

That was quite the derivation!² Our result is known as Binet's formula.