``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:
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
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
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:
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|