structural induction

Structural induction is how you prove that every object built by a set of rules has some property, by checking the smallest objects and then showing each rule preserves the property. Imagine a Lego set where you may only start from a few base bricks and combine them with a few fixed moves: if every base brick is red, and every move keeps things red, then everything you can ever build is red. You never inspect every possible model — you trust the base and the steps.

It generalizes ordinary mathematical induction (which counts up 0, 1, 2, ...) to things that are defined by building up from base cases: strings, regular expressions, parse trees, grammars. A proof has two parts. The base case checks the property holds for the starting pieces (the empty string, or a single-symbol regular expression). The inductive step assumes the property holds for the smaller pieces (the induction hypothesis) and shows it must then hold for anything assembled from them by one construction rule. Cover every rule and you have covered every object, because every object is reachable from the base by finitely many steps.

This is the standard tool for proving facts about all strings or all expressions at once. To show every regular expression denotes some language, you check the base regexes denote languages, then check that union, concatenation, and the Kleene star of language-denoting regexes again denote languages. To prove a property of every parse tree, you check single-leaf trees, then assume it for subtrees and verify it survives when a rule joins them under a new root. Without induction you would face infinitely many cases; with it, a finite proof settles them all.