Computing Fibonacci Numbers

Matrix Exponentiation

Let's call our matrix $\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}$ that represents a single iteration of the Fibonacci recurrence $M$. What can we do now that we have $M$ as a matrix?

Well, let's start with our initial values $V = \begin{pmatrix}1 \\ 0\end{pmatrix}$. We have that $$MV = \begin{pmatrix}2 \\ 1\end{pmatrix}$$

All is as expected: we've moved along to the next value of the Fibonacci sequence.¹ Doing it more, we get

$$\begin{aligned} M(MV) &= \begin{pmatrix}3 \\ 2\end{pmatrix} \\ M(M(MV)) &= \begin{pmatrix}5 \\ 3\end{pmatrix} \\ M(M(M(MV))) &= \begin{pmatrix}8 \\ 5\end{pmatrix} \\ \end{aligned}$$

In general, we seem to have that

$$M^n V = \begin{pmatrix} F(n + 1) \\ F(n) \end{pmatrix}$$

(Remember, order matters but we can remove the parentheses: matrix multiplication is associative but not commutative.)

So now we have a new question: how can we compute $M^n$ efficiently?