Induction & Recursion · step 6 of 13

Induction on inequalities & divisibility

Two families of induction problems have their own techniques. For divisibility, write the n = k+1 expression so the inductive multiple appears explicitly plus a visibly divisible remainder. For inequalities, the step usually needs an extra estimate — you prove something slightly stronger than the target and then weaken it, which is where most students get stuck.

Practise induction on inequalities & divisibility 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.

Divisibility — expose the hypothesisAssume d ∣ f(k), so f(k) = dm. Then rewrite f(k+1) as a multiple of f(k) plus a term you can show is divisible by d.
Inequalities — start from the hypothesisBegin the k+1 case with the quantity you can bound, substitute the hypothesis, and then estimate the leftover.
Check where the base really startsInequalities often fail for small n: 2ⁿ > n² holds from n = 5, not n = 1.
Justify every estimateEach ≤ or < step needs a reason — usually k ≥ some value from the base case.

Worked example

Prove 3 ∣ (n³ − n) for all n ≥ 1.

Base n = 1: 1 − 1 = 0, and 3 ∣ 0 ✓.
Assume 3 ∣ (k³ − k), so k³ − k = 3m.
Expand: (k+1)³ − (k+1) = k³ + 3k² + 3k + 1 − k − 1 = (k³ − k) + 3k² + 3k.
= 3m + 3(k² + k) = 3(m + k² + k), a multiple of 3.

Answer. 3 divides n³ − n for all n ≥ 1 by induction.

Where marks get dropped

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

Expanding (k+1)³ without regrouping to expose k³ − k. The hypothesis must be visible, or it cannot be used.
Starting an inequality induction at n = 1 when the claim is false there. Test small values first and set the base correctly.
Working backwards from the target inequality. The chain must run from what you know to what you want, not the reverse.

Practise this until it is automatic

Unlimited fresh questions

QED generates new induction on inequalities & divisibility 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 on inequalities & divisibility — frequently asked questions

Why do inequality steps need an extra estimate?

Because the hypothesis usually gives a bound on the previous term, and you must relate the new term to it — that relation is an extra inequality needing its own justification.

Is there a non-inductive proof of 3 ∣ n³ − n?

Yes: n³ − n = (n−1)n(n+1) is a product of three consecutive integers, one of which is divisible by 3. Induction is the required method only when the question says so.

From which n does 2ⁿ > n² hold?

From n = 5 onwards: 32 > 25. It fails at n = 2, 3 and 4, so the base case must be n = 5.

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 on inequalities & divisibility 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 →