Lesson · Induction and Recursion · Recurrences

Solving Linear Recurrences

For a linear homogeneous recurrence, substitute aₙ = rⁿ and solve the resulting polynomial. Distinct roots give a combination of geometric sequences; repeated roots need an extra factor of n.

Open the interactive lesson Practice

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ ⟹ r² = c₁r + c₂ distinct roots r₁ ≠ r₂: aₙ = A r₁ⁿ + B r₂ⁿ repeated root r: aₙ = (A + Bn) rⁿ nonhomogeneous: general homogeneous + one particular solution

The recipe

Core ideas

What this lesson establishes

The whole method rests on one guess — that the solution is geometric — and on the fact that solutions can be added.

Guess rⁿ and see what r must be

Substituting turns the recurrence into a polynomial equation. Its roots are the geometric sequences that satisfy the recurrence.

Solutions combine linearly

If two sequences satisfy a linear homogeneous recurrence, so does any combination of them. The initial conditions pick the combination.

A repeated root needs n rⁿ too

One root gives one solution, and two initial conditions need two free constants. n rⁿ supplies the second and does satisfy the recurrence.

The material

The characteristic equation

Derivation, the two cases, and the nonhomogeneous extension.

Take aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ and try aₙ = rⁿ with r ≠ 0. Substituting gives rⁿ = c₁rⁿ⁻¹ + c₂rⁿ⁻², and dividing by rⁿ⁻² leaves

r² = c₁r + c₂ the CHARACTERISTIC EQUATION

Theorem · Distinct roots

If r² − c₁r − c₂ = 0 has distinct roots r₁ ≠ r₂, then every solution of the recurrence has the form aₙ = A r₁ⁿ + B r₂ⁿ, and A, B are determined by the initial conditions.

Theorem · Repeated root

If the characteristic equation has a single root r of multiplicity 2, then every solution has the form aₙ = (A + Bn) rⁿ.

Why the extra n? With one root there is only one geometric solution and only one free constant, which cannot generally satisfy two initial conditions. Substituting n rⁿ into the recurrence and using c₁ = 2r, c₂ = −r² (which is what a repeated root means) confirms it is also a solution.

Example · A repeated root, solved

aₙ = 4aₙ₋₁ − 4aₙ₋₂, a₀ = 1, a₁ = 4. Characteristic r² − 4r + 4 = (r − 2)² = 0, so aₙ = (A + Bn)2ⁿ. From a₀ = 1: A = 1. From a₁ = 4: (1 + B) · 2 = 4, so B = 1, and aₙ = (n + 1)2ⁿ. Check at a₂, which the fitting did not use: formula 3 · 4 = 12; recurrence 4 · 4 − 4 · 1 = 12. Had the n been forgotten, A·2ⁿ + B·2ⁿ is one constant C·2ⁿ, and a₀ demands C = 1 while a₁ demands C = 2 — the contradiction is how the missing factor announces itself.

Example · Fibonacci, solved

Fₙ = Fₙ₋₁ + Fₙ₋₂ gives r² = r + 1, so r = (1 ± √5)/2. Writing φ and ψ for the two roots, Fₙ = Aφⁿ + Bψⁿ. From F₀ = 0 we get A + B = 0, and from F₁ = 1 we get Aφ + Bψ = 1, giving A = 1/√5, B = −1/√5. So Fₙ = (φⁿ − ψⁿ)/√5 — Binet's formula, which produces integers from irrational numbers at every n.

Nonhomogeneous recurrences

Theorem · General solution

For aₙ = c₁aₙ₋₁ + ⋯ + c_k aₙ₋ₖ + f(n), the general solution is aₙ = (general solution of the homogeneous part) + (any one particular solution).

So the work is finding one particular solution. The standard approach is to guess a form matching f(n) and solve for its coefficients.

f(n) try unless it collides with a root constant A then try An linear an + b An + B then multiply by n polynomial deg d general poly of deg d then multiply by n sⁿ A sⁿ if s is a root, try A n sⁿ

Example · Tower of Hanoi, properly

Hₙ = 2Hₙ₋₁ + 1. Homogeneous part: r = 2, so C·2ⁿ. Particular: try a constant A, giving A = 2A + 1, so A = −1. General solution Hₙ = C·2ⁿ − 1, and H₁ = 1 gives C = 1. So Hₙ = 2ⁿ − 1 — derived rather than guessed.

The collision case is worth a sentence. If f(n) = 2ⁿ and 2 is a root of the characteristic equation, then A·2ⁿ already solves the homogeneous equation and cannot produce the forcing term. Multiplying by n and trying A n 2ⁿ is the fix, exactly as with a repeated root.

Interactive

Recurrence and closed form

Iterated and solved, then compared

Roots, and the solution they build

Each preset shows its characteristic equation and the constants fitted to the initial conditions. The iterated column and the closed-form column are computed independently. The default is the worked example below, A = −2, B = 3. Then select the repeated root 4aₙ₋₁ − 4aₙ₋₂: the closed form reads (A + Bn)·2ⁿ with A = 1, B = 1, the example above. The triangular preset aₙ = aₙ₋₁ + n is the collision row of the table: the only root is 1 and f(n) = n is a polynomial, so the particular solution is quadratic, n(n+1)/2.

Recurrence

Terms shown12

Closed form

Method

Solving a linear recurrence

Homogeneous part first, then a particular solution, then fit.

Write the characteristic equation

Replace aₙ₋ⱼ by r^{k−j} and set the polynomial to zero. Its degree is the order of the recurrence.

Find the roots and their multiplicities

Distinct roots give A r₁ⁿ + B r₂ⁿ; a root of multiplicity m contributes (A₀ + A₁n + ⋯ + A_{m−1}n^{m−1}) rⁿ.

For a nonhomogeneous recurrence, find one particular solution

Guess a form matching f(n), substitute, and solve for the coefficients. Multiply by n if the guess collides with a root.

Fit the constants to the initial conditions

One linear equation per initial condition. Then check the closed form reproduces a term you did not use in the fitting.

Solving recurrences

Score 0 / 0

Choose the answer you can justify.

Solve aₙ = 5aₙ₋₁ − 6aₙ₋₂, a₀ = 1, a₁ = 5

Second order, homogeneous, distinct roots.

Characteristic: r² = 5r − 6 r² − 5r + 6 = 0 (r − 2)(r − 3) = 0 ⟹ r = 2, 3 General: aₙ = A·2ⁿ + B·3ⁿ Fit: a₀ = A + B = 1 a₁ = 2A + 3B = 5 subtract twice the first: B = 3, so A = −2 Solution: aₙ = −2·2ⁿ + 3·3ⁿ Check a₂: formula −8 + 27 = 19; recurrence 5(5) − 6(1) = 19. ✓

The check at a₂ used a term not involved in fitting the constants, which is what makes it a real check. Verifying a₀ and a₁ would only confirm the arithmetic of the fitting.

Common mistakes

Forgetting the n on a repeated rootA·2ⁿ + B·2ⁿ collapses to a single constant and cannot satisfy two initial conditions. The general solution is (A + Bn)2ⁿ.

Fitting the constants before finding a particular solutionFor a nonhomogeneous recurrence the constants must be fitted to the FULL general solution, homogeneous plus particular. Fitting early gives wrong constants.

Not checking the collision caseIf the forcing term matches a characteristic root, the obvious guess solves the homogeneous equation and produces 0 = f(n). Multiply by n.

Check your understanding

✓

Finish when you can solve a second-order recurrence and verify it independently.

Solve aₙ = 6aₙ₋₁ − 9aₙ₋₂ with a₀ = 1, a₁ = 6, and check your closed form at a₃ against the recurrence. The repeated root makes this the case people get wrong.

Note: The same method solves linear differential equations with constant coefficients: substitute e^{rt}, get a characteristic polynomial, and handle repeated roots with an extra factor of t. The parallel is exact and not a coincidence.