Induction & Recursion · step 4 of 13

Recursive definitions of sequences & functions

A recursive definition gives base values and a rule expressing later values in terms of earlier ones. To be well-founded, every recursive call must reduce towards a base case — otherwise the "definition" defines nothing. Once you have a recurrence, computing terms is mechanical, and proving a proposed closed form correct is a routine induction.

Practise recursive definitions of sequences & functions 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.

Write the base cases firstEnough of them to make every recursive call bottom out. A rule referring to n−2 needs two bases.
Check the recursion decreasesEvery call must be on a strictly smaller argument, converging on a base case.
Unfold to compute termsSubstitute repeatedly, keeping earlier results so you do not recompute them.
Verify a closed form by inductionCheck the base, then show the closed form satisfies the recurrence at n+1.

Worked example

For a₁ = 2 and aₙ = 2aₙ₋₁ + 1, compute a₄ and verify the closed form aₙ = 3·2^(n−1) − 1.

a₂ = 2·2 + 1 = 5; a₃ = 2·5 + 1 = 11; a₄ = 2·11 + 1 = 23.
Closed form at n = 1: 3·2⁰ − 1 = 2 ✓.
Assume aₖ = 3·2^(k−1) − 1. Then aₖ₊₁ = 2(3·2^(k−1) − 1) + 1.
= 3·2^k − 2 + 1 = 3·2^k − 1, which is the formula at k+1 ✓.

Answer. a₄ = 23, and aₙ = 3·2^(n−1) − 1 for all n ≥ 1 by induction.

Where marks get dropped

These are the specific errors that cost credit on recursive definitions of sequences & functions questions — QED's rubric penalises each of them separately.

Giving too few base cases, leaving the recursion undefined at the bottom.
Defining a function in terms of itself at the same or a larger argument, which never terminates.
Checking a closed form on a few terms and calling it proved. Agreement on five terms is evidence, not a proof.

Practise this until it is automatic

Unlimited fresh questions

QED generates new recursive definitions of sequences & functions 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.

Recursive definitions of sequences & functions — frequently asked questions

What makes a recursive definition valid?

Well-foundedness: the arguments must decrease along a relation with no infinite descending chains, so every computation reaches a base case.

How do I find the closed form?

Compute several terms and look for a pattern, or use the standard techniques — iteration/telescoping for first-order recurrences, characteristic roots for linear ones.

Are recursive definitions the same as recursive algorithms?

They correspond exactly: the base cases become the algorithm’s termination conditions and the rule becomes the recursive call. Proving termination is proving well-foundedness.

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 recursive definitions of sequences & functions 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 →