Matrix Exponentiation for Recurrences

A linear recurrence like the Fibonacci rule $F_n = F_{n-1} + F_{n-2}$ can be rewritten as a matrix multiplication: stacking consecutive terms into a vector, $\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = M \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix}$ for a fixed matrix $M$. Applying $M$ once advances the sequence by one step, so applying it $n$ times from the starting vector produces $F_n$ — but computing $M^n$ doesn't require $n$ separate multiplications. Repeated squaring computes $M^n$ in about $\log_2 n$ matrix multiplications by writing $n$ in binary and combining powers of $M$ that double at each stage ($M, M^2, M^4, M^8, \dots$), the same trick used for fast integer exponentiation.

For Fibonacci, $M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$. To find $F_{10}$, instead of 10 sequential additions, compute $M^2$, $M^4$, $M^8$ by three squarings, then combine $M^8 \cdot M^2$ to get $M^{10}$ — about 4 matrix multiplications total rather than 10 scalar steps. The gap widens enormously for large $n$: computing $F_{10^9}$ takes about 30 matrix multiplications by this method versus a billion additions by direct iteration.

The technique generalizes to any order-$k$ linear recurrence with constant coefficients, using a $k \times k$ companion matrix, and is a standard tool whenever a coding interview or a simulation needs a huge recurrence term without simulating every intermediate step. It also composes naturally with modular arithmetic — since matrix multiplication only needs addition and multiplication, taking every entry modulo some large prime at each step keeps the numbers bounded, which is exactly what's needed when a problem asks for a huge Fibonacci-style term modulo $10^9+7$.