Induction & Recursion · step 3 of 13

Structural induction

When a set is defined by base elements plus construction rules, structural induction proves a property of every member: verify it for the base elements, and show each rule preserves it. This is the natural proof method for lists, trees, and the formulas of propositional logic — and it is what justifies recursion on those structures.

Practise structural 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.

Write out the inductive definitionList the base cases and each construction rule with its arguments. The proof mirrors this list exactly.
Prove the property for each base elementOne short argument per base case.
Assume it for the immediate substructuresFor a rule building x from y and z, assume the property for y and z — that is the structural induction hypothesis.
Prove it for the constructed objectOne case per rule. Missing a rule leaves the proof incomplete, so tick them off explicitly.

Worked example

Prove every propositional formula has equally many left and right brackets, where formulas are variables, or (¬A), or (A ∘ B) for a binary connective ∘.

Base: a variable p contains no brackets, so 0 = 0 ✓.
Rule (¬A): by hypothesis A has equal counts, say b each. The new formula has b+1 of each.
Rule (A ∘ B): by hypothesis A has a of each and B has b of each.
The result has a + b + 1 left and a + b + 1 right brackets.

Answer. Every rule preserves the balance and the base satisfies it, so every formula has equally many left and right brackets.

Where marks get dropped

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

Skipping a construction rule. Every rule in the definition needs its own case, or some elements are unproved.
Applying the hypothesis to something that is not an immediate substructure — the hypothesis covers the pieces the rule was given, not arbitrary subformulas.
Inducting on length instead of structure without justifying that the substructures are shorter. Usually true, but it must be said.

Practise this until it is automatic

Unlimited fresh questions

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

Structural induction — frequently asked questions

How does structural induction relate to strong induction?

It is strong induction on the size or depth of the structure. Working structurally avoids having to define and manipulate a size measure.

Does every inductively defined set support it?

Yes, provided the set is the SMALLEST one closed under the rules. That minimality is exactly what makes structural induction valid.

What is the connection to recursion?

Structural recursion defines a function by the same case analysis, and structural induction proves things about it. The two always come in a pair.

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 structural 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 →