Next: Taxonomy of proof: contrapositive Up: Taxonomy: techniques useful in Previous: Taxonomy of Proof: if

## 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
• Prove that if it holds for , it must hold for 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 , .

Proof: The base case here is , and so that's ok. How about the inductive step? Assuming it's true for means that

 (1)

which we have to use to show it's true for :
 (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 , or

 (3)

Is ? Well, which is less than if . 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 : for , and for , so for . The point of this whole thing is that we can expand (3) to say

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.1 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 be the number of left parentheses in a wff and be the number of right parentheses in . We now consider each case and its parentheses count:

 case number of (`s number of )'s 1 2 3 4 + 1
In the last three cases, and are simpler than the complex forms they are part of [, , or ], and hence for these cases we can assume the inductive hypothesis for and : namely, that and for these simpler forms. Using this assumption, we see that , , and . Finally, we see by inspection that in the base case (1) the parenthesis count matches, so they match in all cases.

Next: Taxonomy of proof: contrapositive Up: Taxonomy: techniques useful in Previous: Taxonomy of Proof: if
Craig Silverstein 2005-08-27