Lesson · Induction and Recursion · Recursion

Structural Induction

When a set is defined recursively, proving something about all its members means proving it for the base objects and showing each construction rule preserves it. No numeric parameter is needed.

Open the interactive lesson Practice

BASE prove P for every object given outright STEP assume P for the parts, prove P for the object built from them Valid because every object is built in finitely many steps. Applies to strings, trees, formulas — anything with a recursive definition.

Induction over structure

Core ideas

What this lesson establishes

Structural induction is ordinary induction over the number of construction steps, with the counting left implicit.

The cases mirror the definition

One base case per base clause, one step per recursive clause. If the definition has three rules the proof has three parts.

The hypothesis is about the parts

For a tree built from L and R, you assume the claim for L and for R and prove it for the whole. That is strong induction on structure.

No size parameter is needed

Trees and formulas have no obvious n. Structural induction sidesteps the question by inducting on how the object was assembled.

The material

Induction over a recursive structure

The principle, why it is valid, and three applications.

Theorem · Structural induction

Let S be defined recursively. To prove P(x) for every x ∈ S, prove P for each object given by a base clause, and prove that each recursive clause preserves P — that is, if P holds for the parts, it holds for the object built from them.

Validity comes straight from the definition. Every member of S is produced in finitely many steps, so induct on that number: at zero steps the object is a base object, and each further step is a recursive clause applied to objects built in fewer steps.

Example · Parenthesis strings are balanced

Recall the definition: the empty string is well formed; if s is, so is (s); if s and t are, so is st. Claim: every well-formed string has equally many left and right parentheses.

Base. The empty string has 0 of each.

Clause (s). Assume s has m of each. Then (s) has m + 1 of each.

Clause st. Assume s has m of each and t has p of each. Then st has m + p of each.

Every well-formed string is built by these clauses, so the property holds throughout.

□

Three parts, matching the three clauses. Missing one — forgetting the concatenation clause, say — would leave a whole family of strings unproved, and the omission is invisible unless the definition is beside the proof.

Trees

Definition · Height and node count

For a binary tree: h(empty) = −1 and h(node(v, L, R)) = 1 + max(h(L), h(R)). n(empty) = 0 and n(node(v, L, R)) = 1 + n(L) + n(R).

Theorem · A binary tree of height h has at most 2^{h+1} − 1 nodes

For every binary tree T, n(T) ≤ 2^{h(T)+1} − 1.

Base. The empty tree has h = −1 and n = 0, and 2⁰ − 1 = 0.

Step. Let T = node(v, L, R) and assume the bound for L and R. Write h = h(T), so h(L) ≤ h − 1 and h(R) ≤ h − 1.

Then n(T) = 1 + n(L) + n(R) ≤ 1 + (2^h − 1) + (2^h − 1) = 2·2^h − 1 = 2^{h+1} − 1.

□

Both subtrees needed the hypothesis, which makes this structural induction with two recursive parts — the structural analogue of the two-term recurrence that forced strong induction in “Strong Induction”.

Formulas

The well-formed formulas of Logic and Proof are a recursively defined set: a variable is a formula; if A is a formula so is ¬A; if A and B are, so is (A ∧ B), and similarly for the other binary connectives. Structural induction over that definition proves the syntactic facts Logic and Proof used without proof.

Example · Parentheses balance in every formula

Base: a variable has none of either. Negation adds none. Each binary clause adds one of each. So every well-formed formula has matching parentheses — which is what makes the parser in the truth-table lab able to reject the strings that are not formulas.

Interactive

Recurrence and closed form

Iterated and solved, then compared

Method

Writing a structural induction proof

Put the definition beside the proof and match them clause for clause.

List the clauses of the definition

Base clauses and recursive clauses. The proof will have exactly this many parts, and matching them is how you know none was skipped.

Prove the claim for each base object

Usually immediate. Do it anyway, in writing.

For each recursive clause, assume the claim for the parts

Then establish it for the object constructed. This is the inductive hypothesis, and there may be more than one part.

Check nothing else is in the set

The closure sentence of the definition is what makes these cases exhaustive. Without it the proof covers a subset.

Structural induction

Score 0 / 0

Choose the answer you can justify.

Every full binary tree has an odd number of nodes

A tree is full when every node has either 0 or 2 children.

Definition: BASE a single node is a full binary tree RECURSIVE if L and R are full binary trees, then the tree with a new root and subtrees L, R is one BASE a single node has 1 node. Odd. ✓ STEP Assume L has n(L) nodes and R has n(R), both odd. The new tree has 1 + n(L) + n(R) nodes. odd + odd = even, and 1 + even = odd. ✓ Every full binary tree is built by these two clauses, so every one has an odd number of nodes. ∎

The parity argument reuses the result of “Direct Proof”, in Logic and Proof: the sum of two odd integers is even. Structural induction supplied the two odd numbers; elementary arithmetic finished the job.

Common mistakes

Omitting a clauseThe concatenation clause for strings and the second subtree for trees are the ones usually forgotten. Write the definition out first.

Using the hypothesis for only one partA binary construction gives you two hypotheses. Using one and asserting the other is a gap.

Assuming the set has no other membersThat is the closure sentence of the definition, and if the definition omits it the proof cannot supply it.

Check your understanding

✓

Finish when you can match a proof to a definition clause by clause.

Prove that every well-formed parenthesis string has no proper prefix with more right than left parentheses. Three clauses, three parts, and the concatenation case is the one that needs thought.

Note: Structural induction is how properties of programs and of syntax are proved: type soundness, evaluation termination and compiler correctness are all structural inductions over a recursively defined language.