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$.