* Induction* is used to prove a sequence of
statements , , , .... There may be finitely many
statements, but often there are infinitely many.

* Example.* Consider the statement

This is actually an infinite set of statements, one for each integer :

You might think of proving this result by induction --- and in fact, I'll do so below.

On the other hand, the statement

is an infinite set of statements, but there is one for each *real
number*. You are unlikely to prove this by induction.

The fact that a statement involves integers does not mean induction is appropriate. For example, consider the statement

"The sum of two even numbers is even."

It's true that this is a statement about an infinite set of pairs of integers.

However, the problem with using induction here is that there isn't an
obvious way to arrange the statements in a *sequence*.

Likewise, consider the statement

"If n is an integer, then is odd."

While it's conceivable that you could give an induction proof, it would be overkill: expresses as 2 times something plus 1, so it must be odd.

How does induction work? Suppose you have a sequence of statements , , ..., , ..., one for each positive integer. (There's no harm in starting your numbering with 0 if it's convenient.) In the simplest case, to give a proof by induction:

1. Prove .

2. Let , and *assume* *is true*.

3. Using the assumption that is *true*, prove that
must be true.

If you can complete these steps, you can conclude that is true for all , by induction.

The assumption that is true is often called the * induction hypothesis*, or the *
inductive assumption*.

Why does it work? Induction follows from a fundamental fact about the
positive integers called the * Well-Ordering
Principle*.

* Well-Ordering Principle.* Every nonempty
subset of the positive integers has a smallest element.

The Well-Ordering Principle is an *axiom* for the positive
integers, so there's no question of *proving* it.

* Example.* Consider the subset of the positive
integers consisting of the positive even integers: . The smallest element of this set is 2.

Consider the subset of the positive integers which consists of positive integers whose decimal representations begin and end with "1". For example, 101, 128391, and 1651 are elements of this set. The smallest element of this set is 1.

* Principle of Mathematical Induction.* Let
, , ... be a set of statements indexed by the
positive integers. Suppose that:

(a) is true.

(b) For every , if is true, then is true.

Then is true for all .

* Proof.* I'll prove the result by
contradiction.

Assume that is true, and for every , if is true, then
is true. Suppose that it *isn't* true that
is true for all .

Consider the set of integers such that
is *false*. Since is not true for all , there must be *some* n for which
is false. Hence, the set of integers such that
is *false* is nonempty.

Since this is a nonempty subset of the positive integers, it contains a smallest element MIN. Thus, is false, and is not false (i.e. is true) for all .

Now MIN can't be 1, because is true by assumption. Thus, . So is a positive integer, and must be true.

But now my second assumption --- if a statement in the sequence is true, the following statement is true --- shows that must be true. This contradicts the fact that is false.

This contradiction proves that is true for all .

* Example.* Prove that

The formula is true for , since

Assume , and suppose the formula holds for . This means that

I want to prove that the formula holds for n.

This proves the formula for n. Hence, the result is true for all , by induction.

* Example.* Let , . Prove that

You're allowed to "begin" an induction with --- or any other integer --- if it's convenient to do so.

For ,

The result is true for .

Assume that , and that the result holds for :

I want to show that the result holds for n.

This proves the result for n, so the result is true for all , by induction.

* Example.* Let , . Prove that

You may have seen this idea when you learned about infinite series;
it's called * telescoping*:

The "argument" is that the terms cancel in pairs, leaving .

Arguments where you say "and so on" are often justified rigorously by induction. That's what I'll do here.

For ,

The result is true for .

Assume that , and suppose the result is true for :

I want to show that the result holds for n.

This proves the result for n, so the result is true for all , by induction.

In some situations, it's convenient to give an induction proof in the following form:

1. Prove .

2. Let , and *assume* *is true for
all* .

3. Using the assumption that is *true for all* , prove that must be true.

In other words, you can take as your induction hypothesis the truth
of *all* the statements prior to the statement, which you are trying to prove.

* Example.* Define a sequence of integers by

Prove that

Here is a table which shows through :

Each x after the first two is defined in terms of the preceding two
x's via the equation , which is called a
* recursion formula*. For example,

To get the induction started, I have to verify the formula for both and . The reason is that the recursion formula doesn't kick in till .

For , the formula gives

For , the formula gives

Both of these check with the given values.

Now assume , and assume the formula holds for all . (Notice that I replaced n with k in the formula to avoid confusion.) I want to prove the formula for n, i.e. .

I begin with the recursion formula

Now holds for all , so in particular it holds for and :

Now plug these into and do some algebra:

This proves the result for n, so the result is true for all by induction.

While the algebra looks like a mess, there is some sense to it, and
you should keep the general principle in mind: *Make what you have
look like what you want*. I knew that I wanted to get . This suggested, first of all, that I group the
powers of 6 together and the powers of -2 together.

I factored out and because I saw powers of 6 and -2 in . When I got to , I was pretty sure that was supposed to give me the , and was supposed to give me the . So it was just a matter of finding the and that I needed to make it work.

* Example.* Prove that if , then .

For , and . The statement is true.

Assume that , and that the result is true for n. I'll prove it for . I have

Now , so multiplying both sides by gives

Also, implies , and multiplying both sides by gives

Also, implies , and multiplying both sides by gives

Also, implies , and multiplying both sides by n gives

To inequalities (1)--(4), add the inequality to obtain

Combining this with the inequality that I derived above, I get

Obviously, I didn't pluck those intermediate inequalities out of thin air! I worked backwards by expanding the target , then trying to see how to make the terms in the expansion less than each of the 5 copies of I had in " ".

Send comments about this page to: Bruce.Ikenaga@millersville.edu.

Copyright 2013 by Bruce Ikenaga