Skip to content

Linear Recurrences & Matrices

A linear recurrence has the form \(a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}\). Matrix exponentiation finds \(a_n\) in \(O(k^3 \log n)\) after building a companion matrix.

Fibonacci example

\[ \begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix} \]

Implement matrix multiply and binary exponentiation on the transition matrix modulo \(m\); multiply the result by the initial state vector to read off \(a_n\).

General \(k\)-term recurrence: build a \(k \times k\) matrix that shifts the state vector \((a_{n},\ldots,a_{n-k+1})\).