Computing Fibonacci Numbers

We'll start with $\lambda_1, a,$ and $c$: note that $\lambda_2, b, d$ follow exactly the same equation, just renamed, so we're going to get a pair of solutions that are interchangeable.

We have that $\lambda_1 a = a + c$ and $\lambda_1 c = a$. Substituting equation 2 into equation 1, we get

$$\begin{aligned} \lambda_1 (\lambda_1 c) &= \lambda_1 c + c \\ \lambda_1^2 c &= \lambda_1 c + c \\ \end{aligned}$$

Because we have three unknowns and two equations, we get some flexibility. Here, as long as $a$ and $c$ are in the right proportion, it doesn't matter what they are. We just want a solution, so we can pick whatever suits our purposes. Let's set $c = 1$ and solve from there:

$$\begin{aligned} \lambda_1^2 &= \lambda_1 + 1 \\ \lambda_1^2 - \lambda_1 - 1 &= 0 \\ \lambda_1 = \frac{1 \pm \sqrt{5}}{2} \\ \end{aligned}$$

As expected, we got two different solutions: one will be our first column and the other will be our second. It's generally nice to work from large to small values of $\lambda$, so we'll pick $\lambda_1 = \frac{1 + \sqrt{5}}{2}$. This has another name: the golden ratio, or $\phi$. Then we have that $\lambda_1, a, c = \phi, \phi, 1$.

Now we fill in the other column with the other solution: $\lambda_2 = \frac{1 - \sqrt{5}}{2}$. We'll call this $\psi$, so we have $\lambda_2, b, d = \psi, \psi, 1$.

So now we have $P = \begin{pmatrix} \phi & \psi \\ 1 & 1 \end{pmatrix}$ and $D = \begin{pmatrix}\phi & 0 \\ 0 & \psi \end{pmatrix}$. Almost done! Now all that's left is to compute $P^{-1}$. There are many ways to do this: if you write out $PP^{-1} = I$ with $a, b, c, d$ as the elements of $P$, you'll get a system of four equations you can solve. I'll just skip that and give $P^{-1} = \frac{1}{\sqrt{5}} \begin{pmatrix} 1 & -\psi \\ -1 & \phi \end{pmatrix}$. That completes the diagonalization.

Take a coffee break or something—if you're still here, you've earned it!