Matrix Exponentiation for Linear Recurrences — Squaring the Transition Matrix
A linear recurrence is staten = M·staten-1, so staten = Mn·state0. Watch binary exponentiation build Mn from M→M²→M⁴→… and recover the recurrence term.
step 0
F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1
Transition matrix — base = M1, and the result accumulator
base = M¹
result (accumulated)
The result matrix accumulates Mn. The recurrence term is read from it.
entry holding f(n) top row = coefficients
Binary exponentiation ladder — bits of n drive square vs multiply
f(n) = ?
Press Step to begin. We compute Mn by repeatedly squaring M (the ladder) and multiplying in the powers whose bit is set in n.
Self-contained visualization. Counting semiring (+,×); for display, entries are reduced mod 1e9+7 only when they grow large, so small values stay readable.
The transition (companion) matrix has the recurrence coefficients on its top row and an identity shift on its sub-diagonal.
See junior.md and professional.md for the proof that M·staten-1 = staten, hence staten = Mn·state0.