Induction & Recursion · step 2 of 13

Strong induction

Strong induction assumes P(m) for ALL m from the base up to k, rather than only P(k). It is logically equivalent to ordinary induction but far more convenient whenever the n = k+1 case decomposes into smaller cases you cannot predict — prime factorisation, Fibonacci recurrences and divide-and-conquer analyses all need it.

Practise strong induction 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.

State the strong hypothesisAssume P(m) holds for every m with n₀ ≤ m ≤ k. Say this explicitly — it is what distinguishes the method.
Decompose the k+1 caseWrite the object as a combination of strictly smaller ones and apply the hypothesis to each piece.
Check enough base casesIf the step reaches back two steps you need two bases; if it can reach any smaller value, verify every case the step cannot produce.
Conclude by strong inductionName the principle used — some schemes distinguish the two forms.

Worked example

Prove every integer n ≥ 2 is a product of primes.

Base case n = 2: 2 is prime, so it is a product of one prime ✓.
Assume every m with 2 ≤ m ≤ k is a product of primes.
Consider k+1. If it is prime we are done.
Otherwise k+1 = ab with 2 ≤ a, b ≤ k. By the hypothesis both a and b are products of primes, so their product is too.

Answer. Every integer n ≥ 2 factors into primes, by strong induction — ordinary induction fails here because a and b are not k.

Where marks get dropped

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

Using ordinary induction where the decomposition produces unpredictable smaller values. Knowing P(k) alone does not cover P(a) for an arbitrary a < k.
Providing too few base cases. A step using P(k) and P(k−1) needs both P(n₀) and P(n₀+1) verified.
Forgetting to justify that the pieces really are smaller. Strong induction only applies to strictly smaller values.

Practise this until it is automatic

Unlimited fresh questions

QED generates new strong induction 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.

Strong induction — frequently asked questions

Is strong induction more powerful than ordinary induction?

No — each can be derived from the other. Strong induction is more convenient, not logically stronger, and either can be used wherever the other works.

How many base cases do I need?

Enough to cover every value the step cannot reach. For a recurrence referring to n−1 and n−2, that means two.

When is strong induction essential in practice?

Whenever the decomposition is not "n+1 = n plus one more": prime factorisation, well-founded recursion, and correctness proofs for divide-and-conquer algorithms.

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 strong induction 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 →