Induction & Recursion · step 7 of 13

Recurrence relations & closed forms

A recurrence defines each term from earlier ones; a closed form gives aₙ directly from n. For first-order linear recurrences aₙ = r·aₙ₋₁ + c there are two reliable routes: iterate the recurrence and recognise the resulting geometric sum, or telescope after a clever substitution. Both end with an induction check, which is where the marks are.

Practise recurrence relations & closed forms 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.

Iterate a few timesSubstitute the recurrence into itself two or three times and look for the emerging pattern in the coefficients.
Recognise the geometric sumFor aₙ = r·aₙ₋₁ + c you get aₙ = rⁿa₀ + c(rⁿ − 1)/(r − 1) when r ≠ 1, and aₙ = a₀ + cn when r = 1.
Telescope when the recurrence is additiveIf aₙ − aₙ₋₁ = f(n), sum both sides from 1 to n; the left collapses to aₙ − a₀.
Verify by inductionConfirm the base and that the closed form satisfies the recurrence. Never present an unverified guess.

Worked example

Solve aₙ = 3aₙ₋₁ + 4 with a₀ = 1.

Iterate: a₁ = 3·1 + 4 = 7; a₂ = 3·7 + 4 = 25; a₃ = 3·25 + 4 = 79.
General pattern: aₙ = 3ⁿ·1 + 4(3^(n−1) + … + 3 + 1) = 3ⁿ + 4·(3ⁿ − 1)/2.
Simplify: aₙ = 3ⁿ + 2·3ⁿ − 2 = 3·3ⁿ − 2 = 3^(n+1) − 2.
Check: n = 0 gives 3 − 2 = 1 ✓; n = 2 gives 27 − 2 = 25 ✓.

Answer. aₙ = 3^(n+1) − 2.

Where marks get dropped

These are the specific errors that cost credit on recurrence relations & closed forms questions — QED's rubric penalises each of them separately.

Using the geometric sum formula with r = 1, which divides by zero. That case is arithmetic, not geometric.
Losing track of how many times the recurrence was applied, giving an off-by-one in the exponent.
Presenting a pattern spotted from three terms as the answer. The induction verification is a marked step.

Practise this until it is automatic

Unlimited fresh questions

QED generates new recurrence relations & closed forms 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.

Recurrence relations & closed forms — frequently asked questions

What is telescoping?

Writing a sum so consecutive terms cancel: Σ(aₖ − aₖ₋₁) collapses to aₙ − a₀. It turns an additive recurrence into a single sum.

How do I handle aₙ = r·aₙ₋₁ + f(n) with non-constant f?

Divide through by rⁿ to make it telescoping, or use the summation factor method. The homogeneous part is always rⁿ times a constant.

What about second-order recurrences?

Use the characteristic equation — it handles aₙ = pAₙ₋₁ + qaₙ₋₂ directly and is the standard method for Fibonacci-style relations.

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 recurrence relations & closed forms 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 →