# Induction

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