Induction & Recursion · step 12 of 13

Linear recurrences via characteristic roots

For aₙ = p·aₙ₋₁ + q·aₙ₋₂, substituting aₙ = rⁿ gives the characteristic equation r² = pr + q. Distinct roots r₁, r₂ produce the general solution A r₁ⁿ + B r₂ⁿ; a repeated root r gives (A + Bn)rⁿ, with the extra factor of n supplying the second independent solution. Initial conditions then fix A and B.

Practise linear recurrences via characteristic roots free → All Induction & Recursion subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Form the characteristic equationRewrite as aₙ − p·aₙ₋₁ − q·aₙ₋₂ = 0 and substitute rⁿ, giving r² − pr − q = 0.
Solve for the rootsFactor or use the quadratic formula. Note whether the roots are distinct, repeated, or complex.
Write the general solutionDistinct: A r₁ⁿ + B r₂ⁿ. Repeated root r: (A + Bn)rⁿ. Complex roots give an equivalent trigonometric form.
Apply the initial conditionsSubstitute two known terms to get two linear equations in A and B, and solve.

Worked example

Solve aₙ = 5aₙ₋₁ − 6aₙ₋₂ with a₀ = 1 and a₁ = 4.

Characteristic equation: r² − 5r + 6 = 0, factoring as (r−2)(r−3) = 0.
Roots 2 and 3, so aₙ = A·2ⁿ + B·3ⁿ.
n = 0: A + B = 1. n = 1: 2A + 3B = 4.
From the first, A = 1 − B; substituting gives 2 − 2B + 3B = 4, so B = 2 and A = −1.

Answer. aₙ = −2ⁿ + 2·3ⁿ. Check n = 2: −4 + 18 = 14, and 5·4 − 6·1 = 14 ✓.

Where marks get dropped

These are the specific errors that cost credit on linear recurrences via characteristic roots questions — QED's rubric penalises each of them separately.

Using A rⁿ + B rⁿ for a repeated root, which is just one solution with the constants merged. The second must be n·rⁿ.
Getting the sign of q wrong when forming the characteristic equation. Move everything to one side first.
Solving for A and B with only one initial condition. A second-order recurrence needs two.

Practise this until it is automatic

Unlimited fresh questions

QED generates new linear recurrences via characteristic roots problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Induction & Recursion mastery is tracked so you know when this is exam-ready.

Linear recurrences via characteristic roots — frequently asked questions

What if the roots are complex?

Write them as re^(±iθ). The solution becomes rⁿ(A cos nθ + B sin nθ), which is real and oscillating — the discrete analogue of damped oscillation.

How does this give Binet’s formula?

For Fibonacci, r² = r + 1 has roots φ = (1+√5)/2 and ψ = (1−√5)/2, and the initial conditions give Fₙ = (φⁿ − ψⁿ)/√5.

What about non-homogeneous recurrences?

Solve the homogeneous part, find any particular solution matching the forcing term, and add them — exactly as for linear differential equations.

The rest of Induction & Recursion

Mathematical, strong & structural induction; recursion. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make linear recurrences via characteristic roots exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →