Induction & Recursion · step 1 of 13

Weak (ordinary) mathematical induction

Ordinary induction proves ∀n ≥ n₀ P(n) from two ingredients: P(n₀) holds, and P(k) implies P(k+1) for every k ≥ n₀. The dominoes metaphor is accurate — the base case topples the first one and the step guarantees each knocks over the next. Exam schemes award marks separately for the base case, the explicit statement of the hypothesis, and the correct use of that hypothesis in the step.

Practise weak (ordinary) mathematical 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 P(n) preciselyWrite "let P(n) be the statement …". Vagueness here costs marks throughout.
Prove the base caseVerify P(n₀) by direct computation, showing both sides. One line, but never skippable.
Assume P(k) explicitlyWrite "assume P(k) holds for some k ≥ n₀, i.e. …" with the statement spelled out.
Derive P(k+1) using the hypothesisThe step must actually invoke P(k) — point to where. Then conclude by the principle of induction.

Worked example

Prove that 1 + 2 + … + n = n(n+1)/2 for all n ≥ 1.

Base case n = 1: LHS = 1, RHS = 1·2/2 = 1 ✓.
Assume P(k): 1 + … + k = k(k+1)/2.
Then 1 + … + k + (k+1) = k(k+1)/2 + (k+1), using the hypothesis for the first k terms.
= (k+1)(k/2 + 1) = (k+1)(k+2)/2, which is P(k+1).

Answer. The formula holds for all n ≥ 1 by induction.

Where marks get dropped

These are the specific errors that cost credit on weak (ordinary) mathematical induction questions — QED's rubric penalises each of them separately.

Omitting the base case. Without it, "P(k) ⟹ P(k+1)" proves nothing — the statement n = n + 1 satisfies the step and no base case.
Assuming P(n) for all n rather than for one k. That assumes what is to be proved and invalidates the proof.
Never actually using the hypothesis. If the step works without P(k), you have a direct proof, and the induction framing is misleading.

Practise this until it is automatic

Unlimited fresh questions

QED generates new weak (ordinary) mathematical 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.

Weak (ordinary) mathematical induction — frequently asked questions

Where exactly should I use the induction hypothesis?

At the point where you split the n = k+1 case into "the first k" plus "the new bit". Substituting the hypothesis for the first part is the whole method.

Can the base case be n = 0 or n = 5?

Yes — the base is whatever the smallest claimed value is. Proving from n = 5 up establishes the statement only for n ≥ 5.

Why is induction valid?

It is equivalent to the well-ordering of ℕ: if the set of counterexamples were non-empty it would have a least element, contradicting the base case or the step.

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 weak (ordinary) mathematical 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 →