The trouble: proving something about infinitely many things
Almost every interesting claim in this subject is secretly an infinite claim. 'Every string over the alphabet has a well-defined length.' 'Every regular expression describes some language.' 'Every accepting run of a machine visits a start state.' There are infinitely many strings, infinitely many expressions, infinitely many runs — so you cannot check them one at a time and ever be done. You need a way to settle infinitely many cases with a finite argument, and that is exactly what induction gives you.
Start with the version you have probably met: ordinary mathematical induction over the counting numbers 0, 1, 2, 3, and so on. To prove a statement P(n) holds for every n, you do two things. First the base case: show P(0) is true. Then the inductive step: show that whenever P(k) is true, P(k+1) must also be true. Together these are a chain of dominoes — the base case tips the first one, the step guarantees each falling domino knocks over the next, so every domino in the infinite line falls.
The assumption 'P(k) is true' inside the step has a name: the induction hypothesis. It feels like cheating — you are assuming the very kind of thing you are trying to prove — but it is not, because you only assume it for the smaller case k and use it to reach the larger case k+1. The dominoes never assume themselves; each one is genuinely knocked over by the one before it.
From counting up to building up
Ordinary induction climbs a ladder of numbers. But the objects we care about here are not numbers — they are strings, expressions, and trees, which are not 'the next one after' anything in an obvious numeric way. The fix is to notice that these objects are inductively defined: they are built from a few starting pieces using a few fixed combining rules, and nothing else. A string over Sigma (the alphabet) is either the empty string epsilon (the base case), or a shorter string with one more symbol stuck on the end (the building rule). Every string is reachable from epsilon by finitely many one-symbol steps.
Structural induction is induction that follows this build-order instead of the number line. The slogan is exactly the Lego picture from the structural induction glossary entry: if every base brick is red, and every combining move keeps things red, then everything you can ever build is red — you never inspect every model, you trust the base and the steps. The base case proves the property for the starting pieces; the inductive step assumes it for the smaller pieces and shows each construction rule preserves it.
A worked example, step by step
Let us prove a small but real fact: for all strings x and y over Sigma, length(xy) = length(x) + length(y), where xy is the concatenation of x and y. This is the kind of 'obvious' statement that you actually do have to prove, because length and concatenation are themselves defined by induction. We induct on the structure of y — that is, on how y was built up from epsilon.
- Base case (y is epsilon): x·epsilon is just x, so length(x·epsilon) = length(x). And length(x) + length(epsilon) = length(x) + 0 = length(x). The two sides match, so the claim holds for the smallest y.
- Induction hypothesis: assume the claim holds for some string w, i.e. length(xw) = length(x) + length(w) for every x. (We assume it only for the shorter piece w.)
- Inductive step (build a bigger y by appending one symbol a, so y = wa): then xy = x(wa) = (xw)a, and appending one symbol adds exactly 1 to a length. So length(xy) = length(xw) + 1.
- Apply the hypothesis: length(xw) + 1 = (length(x) + length(w)) + 1 = length(x) + (length(w) + 1) = length(x) + length(wa) = length(x) + length(y). The two sides match for y = wa, completing the step.
Because y was built from epsilon by appending one symbol at a time, and we covered the base (epsilon) and the only building rule (append a symbol), the property holds for every y — and hence for all x and y at once. Notice the shape: we proved the base, assumed the smaller piece, and showed the one construction rule preserves the equation. That is the entire template, and you will reuse it constantly.
Inducting over trees and expressions
The real power shows up when the objects branch. A regular expression is built from base regexes (a single symbol, epsilon, or the empty set) by three combining rules: union, concatenation, and the Kleene star (written L*). A parse tree of a context-free grammar is built from single-leaf trees by joining subtrees under a new root according to a tree-shaped rule. To prove a property of every such object, the inductive step now has one case per combining rule, and you assume the hypothesis for each smaller part — both children of a union, every subtree under a root.
Here is the spine of one such proof, the claim that every regular expression denotes some language. The base regexes plainly denote languages (a single symbol denotes {that symbol}, and so on). The inductive step has three cases: if r and s already denote languages, then so do their union, their concatenation, and r*. Covering all three rules covers every regular expression, because each one is assembled from the base by finitely many of these three moves.
Grammar: S -> a S b | epsilon (this generates a^n b^n, n >= 0)
Parse tree for the string a a b b :
S
/ | \
a S b <- one use of rule S -> a S b
/ | \
a S b <- another use of S -> a S b
|
epsilon <- base rule S -> epsilon (a leaf)
Structural induction on this tree:
base case : the leaf S -> epsilon yields the empty string
build rule : if subtree under inner S yields a^k b^k,
then wrapping it as a S b yields a^(k+1) b^(k+1)
conclusion : every tree of this grammar yields some a^n b^nRead the tree from the leaves upward and the induction almost writes itself. The single base rule sits at the leaf; each application of the building rule a S b wraps a smaller a^k b^k into a^(k+1) b^(k+1). Assume the property for the subtree (the smaller derivation), show the wrapping rule preserves it, and you have proven that every parse tree of this grammar yields a balanced string. This bottom-up reading is exactly why trees and structural induction are made for each other.
Where it goes wrong, and where it goes next
Two mistakes sink most failed induction proofs, and both come from skipping part of the template. First, forgetting a construction rule in the inductive step: if a regular expression has three combining rules and you only check union and concatenation, every expression that uses the Kleene star is left unproven, and your 'theorem' is simply false for those. You must cover every rule. Second, skipping or fumbling the base case: a flawless inductive step with no valid base proves nothing at all — the dominoes are perfectly arranged but no one ever tips the first one.
Be honest about what induction does and does not give you. It proves a statement true for all the objects in an inductively defined collection — it does not, by itself, construct any particular object or hand you an algorithm. It also only works on objects that genuinely have a base and finitely many building steps; you cannot induct your way through an object that requires infinitely many steps to build. And induction is a different tool from proof by contradiction: induction builds a property up across all cases, whereas contradiction assumes the opposite of one claim and derives an impossibility. They are often used together but should not be confused.
Induction is also a gateway to the very next ideas in this rung. The pigeonhole principle — coming up next — is the cousin that proves a repeat must exist, and together with induction it underwrites the pumping lemma you will meet later. And a close relative of this build-and-check reasoning, run in reverse and pushed to infinity, becomes Cantor's diagonal argument, the tool that shows some languages cannot be recognized by any machine. Master the humble domino now, and these later, flashier proofs will feel familiar rather than magical.