Induction and recursive structure

Prerequisites: Propositions, quantifiers, basic algebra, and simple recursive definitions.

Learning objectives

• Write an induction proof with a precise hypothesis.
• Choose ordinary, strong, or structural induction.
• Separate a termination argument from a correctness argument.

A proof is more than a pattern

Checking a formula for several inputs can suggest a theorem, but it does not establish all inputs. Mathematical induction proves a statement P(n) for every integer n at least a chosen base. Prove P(0), then prove that P(k) implies P(k+1) for an arbitrary nonnegative k. The step is conditional: you may use P(k), but you may not assume the conclusion P(k+1).

Consider the claim that the sum of the first n odd positive integers is n squared. At n=0 the empty sum is 0. Suppose the first k odd integers sum to k squared. The next odd integer is 2k+1, so the extended sum is k squared + 2k + 1 = (k+1) squared. The base and step together cover every nonnegative integer. The algebra identifies exactly why adding one term preserves the claimed relationship.

Strong induction allows the step to assume P(0) through P(k). It has the same proof power as ordinary induction, but it fits recurrences that depend on several smaller arguments. For example, proving that every integer at least two factors into primes considers a composite n=a*b, where both factors are smaller than n. Be explicit about which smaller cases the step needs.

Data has structure too

Define a full binary tree recursively: a leaf is a tree, and a branch containing two trees is a tree. Claim that each such tree has one more leaf than internal nodes. A leaf has one leaf and zero internal nodes. For a branch with subtrees L and R, assume leaves(L)=internal(L)+1 and the corresponding equation for R. Then total leaves are internal(L)+internal(R)+2, while total internal nodes are internal(L)+internal(R)+1. The claim follows.

This is structural induction: the proof cases follow the constructors of the data. It directly supports recursive programs over lists, expressions, syntax trees, and directories. If a datatype gains a constructor, both the program and its proof need a new case.

Termination is another obligation

A recursive function also needs a well-founded decrease. Traversing strict subtrees terminates for a finite tree because each call receives fewer nodes. Correctness of a returned value does not prove that a return will occur. A complete argument states the input domain, the decreasing measure, the base behavior, and how recursive results establish the parent result. Cyclic object graphs are not finite trees merely because their references look tree-shaped.

Practice problem

Define a list recursively as empty or a head followed by a smaller list. Prove that reversing a list preserves its length using structural induction. Then inspect a recursive length function whose nonempty case calls itself on the original list rather than its tail. Explain why the intended induction hypothesis cannot justify this program and give a smallest failing input. Finish by stating a decreasing measure for the correct implementation and what additional assumption is required if lists are represented by linked objects.

Worked solution

The empty list reverses to empty, so both lengths are zero. For a nonempty list with head h and tail t, assume reverse(t) has length len(t). Reversing the original list appends h to reverse(t), producing length len(t)+1, exactly the original length. This uses the elementary fact that appending one element increases length by one. Calling length on the unchanged list makes no progress: even a single-element list repeats forever until the runtime stops it. The correct call uses the tail, reducing the nonnegative integer number of remaining nodes by one. A linked representation additionally requires an acyclic chain ending at an empty marker. A cycle defeats that decreasing measure.

Check your understanding

A proof handles n=1 and proves P(k) implies P(k+2). What is missing for all positive integers?

• A base case for n=2.
• A check at n=100.
• An assumption that P(k+2) holds.

Explanation

The step preserves parity. The n=1 base reaches odd integers only, so n=2 is needed for the even chain.

Why does structural induction fit an expression evaluator?

• It proves every loop terminates.
• Its cases match expression constructors and assume results for strict subexpressions.
• It removes the need to specify valid inputs.

Explanation

Recursive syntax supplies the proof structure. Termination and validity still need explicit arguments.

Primary reading

• Mathematics for Computer Science: MIT OpenCourseWare

Open the study and save your work →