Induction & Recursion · step 10 of 13

Induction with several base cases

When the induction step derives P(n) from P(n−1) and P(n−2), one base case is not enough — the step cannot produce the second value from the first. The rule is simple: verify every value the step cannot reach. A step reaching back d places needs d base cases, and coin or postage problems often need several because the step jumps by a fixed amount.

Practise induction with several base cases 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.

Look at how far back the step reachesA step using P(k−1) and P(k−2) needs the two smallest values verified directly.
Verify each base explicitlyCompute both sides for every base value. Assuming one from the other defeats the purpose.
Check the step’s validity rangeState the smallest k for which the step is legitimate — often k ≥ 2 or k ≥ 3, and it must connect to the bases.
Confirm full coverageBases plus reachable values must be every n claimed. Gaps are the most common error.

Worked example

Show every postage of n ≥ 12 pence can be made from 4p and 5p stamps.

Bases: 12 = 4+4+4; 13 = 4+4+5; 14 = 4+5+5; 15 = 5+5+5. Four base cases.
Step: assume it holds for all values from 12 up to k, with k ≥ 15.
For k+1 ≥ 16, note k+1 − 4 ≥ 12, so by the hypothesis k+1 − 4 is makeable.
Add one 4p stamp to get k+1.

Answer. Every n ≥ 12 is makeable — four base cases are needed because the step subtracts 4 and must land at or above 12.

Where marks get dropped

These are the specific errors that cost credit on induction with several base cases questions — QED's rubric penalises each of them separately.

Using one base case for a two-step recurrence, leaving the second value unproved and the whole induction broken.
Verifying bases that the step could have produced anyway, which wastes effort but is harmless — the real error is the reverse.
Starting the step at a k for which the hypothesis does not yet cover k+1 − d.

Practise this until it is automatic

Unlimited fresh questions

QED generates new induction with several base cases 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.

Induction with several base cases — frequently asked questions

How do I know how many base cases I need?

Count how far back the step reaches: if it uses P(k+1−d), you need d consecutive base cases so that every application lands on established ground.

Can there be too many base cases?

Extra verified cases are never wrong, just redundant. Too few is fatal, so err on the side of more.

Why does the postage problem need four?

Because the step subtracts 4, so it can only reach values 4 or more above a base. Verifying 12, 13, 14 and 15 covers every residue class mod 4.

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 induction with several base cases 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 →