Induction & Recursion · step 8 of 13

Well-founded induction & termination

Well-founded induction generalises induction to any relation with no infinite descending chains. Its main application is proving termination: exhibit a measure mapping the program state into a well-founded order — usually ℕ, or ℕ × ℕ lexicographically — and show every step strictly decreases it. Since it cannot decrease forever, the program must stop.

Practise well-founded induction & termination 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.

Choose a measureA quantity computed from the current state, mapping into ℕ or another well-founded order.
Show it decreases strictlyEvery iteration or recursive call must reduce the measure. Non-strict decrease is not enough.
Show it is bounded belowThe measure must land in a well-founded set — ℕ works because it has no infinite descending chains.
Use a lexicographic pair when one number will not doAllow the second component to increase provided the first strictly decreases.

Worked example

Prove the Euclidean algorithm gcd(a, b) = gcd(b, a mod b) terminates for positive integers.

Take the measure to be the second argument b, a non-negative integer.
Each call replaces (a, b) with (b, a mod b).
By the division algorithm, 0 ≤ a mod b < b, so the measure strictly decreases.
A strictly decreasing sequence in ℕ cannot be infinite, so the recursion reaches b = 0.

Answer. The algorithm terminates, because the second argument is a strictly decreasing measure into the well-founded set ℕ.

Where marks get dropped

These are the specific errors that cost credit on well-founded induction & termination questions — QED's rubric penalises each of them separately.

Choosing a measure that only decreases sometimes. Every step must strictly reduce it, including the worst case.
Using a measure over ℤ or ℚ. Neither is well-founded under < — the measure must be bounded below.
Proving termination and calling it correctness. Termination says it stops; partial correctness says the answer is right, and both are needed.

Practise this until it is automatic

Unlimited fresh questions

QED generates new well-founded induction & termination 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.

Well-founded induction & termination — frequently asked questions

What is a well-founded relation?

One with no infinite descending chains. ℕ with < qualifies; ℤ with < does not, and neither does the positive rationals.

When do I need a lexicographic measure?

When one quantity decreases but another may grow — nested loops are the classic case. The pair (outer, inner) decreases lexicographically even though the inner counter resets.

Is termination decidable?

Not in general — that is the halting problem. Measure-based proofs work for specific programs, which is why they must be constructed by hand or by heuristic tools.

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 well-founded induction & termination 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 →