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

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

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:

- 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.

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 |