Induction

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

For 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, this statement is also an infinite set of statements:

However, 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 Axiom.

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

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

Example. Verify the Well-Ordering Axiom for the following subsets of positive integers:

(a) The positive even integers: .

(b) 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.

(a) The smallest element of this set is 2.

(b) The smallest element of this set is 1.

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

Remark. You can also do the induction step by assuming the result for n, and proving it for . Usually, there is no difference in the difficulty, so you should use whichever approach you find comfortable.

Also, some inductions begin with a statement numbered "0" --- or "42". The numbering doesn't matter.

Example. Prove that

The formula is true for , since the left side is 1 and the right side is

Suppose the formula holds for n. This means that

I want to prove that the formula holds for .

Suggestion: You might want to write the formula for out on scratch paper so you know what you're trying to prove. You get it by replacing "n" with " " in the formula for n:

Don't start with this equation! --- that would be assuming what you want to prove. Instead, start with the left side and work until you get the right side.

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

Notice that when I wrote out the left side of the formula for I put in both the final term " " and the term before it, which is "n". In that way, I could see the expression " " which is the left side of my induction assumption --- so I knew to begin by substituting. This trick is often useful in the induction step.

Example. Prove that for

The formula is true for , since the left side is 14 and the right side is

Suppose the formula holds for n. This means that

I need to prove the formula for .

(On scratch paper, I write out the formula for ; it is

Remember not to start with this equation --- start with the left side! Notice that on the left side I wrote out the final term ( ), then wrote out the previous term ( ). This helps me recognize the left side of the induction assumption.)

Continuing with our proof, here's the proof of the formula for . I won't write out justifications for steps this time, as most of it is basic algebra.

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

Are you wondering how I made the final step?

The idea is that I knew from my scratch work that the final answer had to be . So I wrote it down, then checked that it worked by multiplying out to see if I got . Nobody "knows" how you got the final step --- the question is whether it's true!

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 .

(For variety, I'll do this induction step by assuming the result for and proving it for n. The amount of work is about the same as assuming it for n and proving it 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 the result is true for n:

I want to show that the result holds for n.

This proves the result for , 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. This is sometimes called generalized induction or strong induction.

Example. Define a sequence of integers by

Prove that

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

The formula holds for and .

Now assume that and the formula holds for all , i.e. for all numbers less than n. In particular, since and are less than n, I have

The fact that I need both of these formulas to do the induction step is why I'm using a generalized or strong induction. If I did a standard induction where I just assumed the result for , I would not have it for .

I have to show that the formula holds for n. I start with the recursion formula that defines , substitute the results for and , and do some algebra:

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

Here are some remarks about the algebra I did. My target expression has a power of 7 and a power of -2. So I began by grouping terms into powers of 7 and powers of -2.

Next, to try to make what I had look like what I wanted, I factor out and . Then simplifying what was left produced the powers ( and ) that I needed to finish. Perhaps it looks like magic, but as we've seen in other proofs, if your steps are correct, it has to work --- you know what the final expression should be.

In the examples that follow, I use induction to prove inequalities and a divisibility result. The general setup for the inductions remains the same --- it's just the specific work that differs.

Example. Prove that

For ,

The result holds for .

Assume that the result holds for n:

I'll prove it for . To get the proof started, I make a " " term appear using algebra, so I can use the induction assumption.

(In the inequality which gave the second-to-the-last line, I used the facts that and to replace the existing terms so I could match the target.)

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

Example. Prove that for ,

In this case, the basis step is , because the result is to be proved for . (Try some numbers and you'll find the can be bigger than for some numbers smaller than 6 .)

For ,

The result is true for .

Assume that the result holds for n:

I have to prove the result for .

Thus, I have

On scratch paper, I see that my target inequality is

So my strategy will be to break up the that I have so far into 4 pieces, each of which will be greater than or equal to one of the 4 pieces of . I will do this in steps.

Since and , I have

Again, since , multiplying both sides by , I get

Since , it follows that . So taking the last inequality and adding another term, I have

Finally, gives

Adding the inequalities (1), (2), (3), and (4), I have

Combine this with the inequality I proved earlier:

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

There are other ways to prove the key inequality . For example, you could use calculus: After some algebra, you get the inequality . Take . Note that , and show that for , so the function increases.

This proof is a little involved, so for starters try to understand why each step is correct before trying to grasp the whole. Don't feel bad if you think that you wouldn't have figured this out by yourself! There are math problems that stump even the best mathematicians. The more experience you get, the more you will be able to do by yourself.

For the next example, remember that if m and n are integers, m divides n (in smbols, ) if for some integer n.

Example. Prove that for ,

You can do this proof directly, without induction. But I'll give an induction proof by way of example.

For , I have

Since , the result holds for .

Assume that the result holds for n:

I can write this as for some integer k, or

I must prove the result for . As usual, the first thing I'll do is to work on the given expression to get (part of) the induction assumption to appear.

I have the " " which is part of the induction assumption. Now means for some integer k, or

Substituting this into the expression above, I get

All together,

Therefore, . This proves the result for , so the result holds for by induction.

Here's a sketch of a direct proof: Write . Then use the formula

Contact information