Taxonomy of Proof: structural induction

``STRAIGHT'' INDUCTION is an occasionally useful proof technique. It is used to prove there exists a relationship between some function of the integers and a given formula. Since there are an infinite number of integers, brute force won't work (``Well, the pattern holds for 1, and for 2, and for 3, and ...''), so we use induction:

• Prove the pattern holds for the smallest number we care about.
• Assume it holds for an arbitrary number $N$
• Prove that if it holds for $N$, it must hold for $N+1$ as well.

Again, we can't escape the IF...THEN construction. We can use induction to prove Theorem 1 from Section 1. Recall the theorem: if $x \geq 4$, $2^x \geq x^2$.

Proof: The base case here is $x = 4$, and $2^4 \geq 4^2$ so that's ok. How about the inductive step? Assuming it's true for $n$ means that

$$2^n \geq n^2$$ (1)

which we have to use to show it's true for $n+1$:

$$2^{n+1} \stackrel{?}{\geq} (n+1)^2$$ (2)

To get the left-hand size of (1) to look like the left hand side of (2), we multiply both sides by 2 to get $2 \times 2^n \geq 2n^2$, or

$$2^{n+1} \geq 2n^2$$ (3)

Is $2n^2 \geq (n+1)^2$? Well, $(n+1)^2 = n^2 + 2n + 1$ which is less than $2n^2$ if $2n + 1 < n^2$. This is not hard to prove, but I'll prove it in a short but kinda tricky way which takes advantage of the fact we know $n \geq 4$: $2 \times n < (n-1) \times n$ for $n \geq 4$, and $1 < n$ for $n \geq 4$, so $2n + 1 < (n-1)n + n = n^2$ for $n \geq 4$. The point of this whole thing is that we can expand (3) to say

$$2^{n+1} > 2n^2 > (n+1)^2$$

But this inequality is just (2) which is what we were trying to show. Thus the induction holds.

There aren't many places where straight induction is useful, however, for we rarely try to prove things about integers. However, forms of induction can be appropriate when trying to prove things about structures defined recursively.¹ For instance, a string in computer science is defined as a collection of characters, and proofs about strings often start with proving the case for single-character strings (or the empty string) and then proving the rest by induction. This generalized induction is known as structural induction. It is useful when objects are built up from more primitive objects: if we can show the primitive objects have the desired property, and that the act of building preserves that property, then we have shown that all objects must have the property. The inductive hypothesis (i.e., the assumption) is to assume that something is true for ``simpler'' forms of an object and then prove that it holds for ``more complex'' forms. ``Complexity'' is defined as a relative term: one object is more complex than another iff it includes that other object as a subpart. A classic use of structural induction is to prove that any legal expression has the same number of left parentheses and right parentheses:

Theorem 5   E is a well-formed formula (wff) if it has one of the following forms:

• a number (constant) or letter (variable)
• E + F, where E and F are both wffs
• E * F, where E and F are both wffs, or
• (E), where E is a wff.

Prove all wffs have the same number of left and right parentheses.

In this example, wffs of type 1 are the primitive types, while the others make new wffs from simpler ones. We must take care not to forget a case.

Proof: We let $E_($ be the number of left parentheses in a wff $E$ and $E_)$ be the number of right parentheses in $E$. We now consider each case and its parentheses count:

case	number of (`s	number of )'s
1	$0$	$0$
2	$E_( + F_($	$E_) + F_)$
3	$E_( + F_($	$E_) + F_)$
4	$E_( + 1$	$E_)$ + 1

In the last three cases, $E$ and $F$ are simpler than the complex forms they are part of [$E+F$, $E*F$, or $(E)$], and hence for these cases we can assume the inductive hypothesis for $E$ and $F$: namely, that $E_( = E_)$ and $F_( = F_)$ for these simpler forms. Using this assumption, we see that $[E+F]_( = [E+F]_)$, $[E*F]_( = [E*F]_)$, and $[(E)]_( = [(E)]_)$. Finally, we see by inspection that in the base case (1) the parenthesis count matches, so they match in all cases.