Linear Recurrences via Matrices

Key idea

Compute Fibonacci numbers using matrix powers.

In depth

A recurrence like aₙ₊₂ = aₙ₊₁ + aₙ can be written as a vector update vₙ₊₁ = Avₙ, so vₙ = Aⁿv₀. Eigenvalues give closed forms and fast computing through matrix powers.

Worked example

Fibonacci: [1 1; 1 0]ⁿ contains Fₙ₊₁, Fₙ, Fₙ₋₁.

Real-world uses

• Computing large terms of a recurrence quickly, such as in financial growth models

Common mistake

Building the state vector with inconsistent ordering.

How to learn this

1. Read the key idea and say it in your own words.
2. Work through the worked example, then try a similar problem.
3. Use the interactive lesson’s visual and mini-quiz to check the pattern.

Frequently asked questions

Expand all Collapse all

Related expert topics in Linear Algebra

• Triple Product – Scalar triple product gives parallelepiped volume.
• Homogeneous Systems – Ax = 0 always has the trivial solution.
• Cofactor Expansion – Compute determinants recursively.
• Properties of Determinants – Multiplicative; row swaps change sign.
• Geometric Meaning of Determinants – Area or volume scaling factor.
• Cramer’s Rule for Systems – Solve systems using determinants.