next up previous
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:

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

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
\end{displaymath} (1)

which we have to use to show it's true for $n+1$:
2^{n+1} \stackrel{?}{\geq} (n+1)^2
\end{displaymath} (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
\end{displaymath} (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

\begin{displaymath}2^{n+1} > 2n^2 > (n+1)^2 \end{displaymath}

But this inequality is just (2) which is what we were trying to show. Thus the induction holds. \( \ \vrule width.2cm height.2cm depth0cm\smallskip\)

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: 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. \( \ \vrule width.2cm height.2cm depth0cm\smallskip\)

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