structural induction

Numbers are not the only things that come in 'a smallest one and bigger ones built from smaller ones'. A tree is a node with smaller subtrees; a linked list is a head plus a smaller tail; a well-formed arithmetic expression is either a number or two smaller expressions joined by an operator. Anything defined by 'base shapes plus rules for building bigger shapes from smaller ones' can be reasoned about by structural induction: prove the property for the base shapes, then prove that the building rules preserve it.

Formally, a recursively defined set has constructors (ways to build elements). To prove every element has property P, you prove P for each base constructor, then for each combining constructor assume P holds for its components (parts) and show it holds for the whole. For binary trees, the base is the empty tree (or a leaf) and the rule is 'a node with a left and right subtree.' To prove, say, 'number of leaves = number of internal nodes + 1' for full binary trees: a single leaf has 1 leaf, 0 internals, 1 = 0+1; for a node joining subtrees with (L1, I1) and (L2, I2) leaves/internals, the whole has L1+L2 leaves and I1+I2+1 internals, and L1+L2 = (I1+1)+(I2+1)... = (I1+I2+1)+1, preserving the property.

Structural induction is really strong induction over the size (or depth) of the structure, so it is sound for the same reason: the components are always strictly smaller, so the recursion bottoms out. It is the standard way to prove things about trees, lists, grammars, and recursive data types, and it is the cleanest framing for the correctness of recursive procedures whose recursion mirrors the data's structure. The pitfall is forgetting a constructor (e.g., handling internal nodes but not the empty tree), which leaves a hole in the proof.