The Technique of Proof by Induction

This page is almost a mirror of http://www.math.sc.edu/~sumner/numbertheory/induction/Induction.html . Very special thanks to David Sumner at the University of South Carolina for providing this nice site! In finding this page I also found out about "Dr. Math" http://mathforum.org/library/drmath/view/52863.html Very Cool! Also http://www.math.csusb.edu/notes/proofs/pfnot/node10.html has a short piece.

Suppose that having just learned the product rule for derivatives [i.e. (fg)' = f'g + fg'] you wanted to prove to someone that for every integer n >= 1, the derivative of is . How might you go about doing this? Maybe you would argue like this:

"Well, see that when n=1, f(x) = x and you know that the formula works in this case.

Now for n=2,

Now for n=3,

And you see we can keep on going this way - do you see the pattern? We just keep using the product rule in conjunction with the result from the previous line and we get the theorem for the next integer."

Consider another example. Suppose that you wanted to show that for every integer n >= 1,

. You might argue this way:

It's true for n=1, that's pretty clear. I can also check it directly for n =2, 3 ,4 and 5.

Now that I know it's true for n=5, I can show you that it is true for n=6 like this:

and so the formula works for n=6, too. Now I can continue this way and use this last result to show that the formula is true for n=7. Then, using the fact that it is true for 7, show that is also true for 8 etc. I could say something like, "so, see, I can continue just like this and prove the result for one integer after another." But that's not very satisfying.

In fact, not only is it not satisfying, it is not a proof since sometimes patterns change and one might not have gotten to the point where this change occurs.

Here are a couple more Summation equalitities and a proof by induction for one.

Now suppose I wanted to prove the following theorem.

Theorem. Suppose that m is a fixed integer and .
Then for every integer n >= 1, .

We might recall that we have already shown this is true for n=2 and n=3.

To show that it is true for n=4, we could say that since we know that and , then . Now that we know that the result is true for n = 4, we can show that it is true for n = 5 in exactly the same way.

Since and , we have

Now that we know the result is true for n = 5, we can show that it is true fro n =6 in exactly the same way. Since and , then . And now we might say that it is fairly evident that we can continue this process and so it is true that for every integer n >= 1.

Mathematical Induction is way of formalizing this kind of proof so that you don't have to say "and so on" or "we keep on going this way" or some such statement. The idea is to show that the result is true for n=1 and then show how once you've shown it to be true for some integer, you can see that it must be true for the next one as well.

The Principle of Mathematical Induction

Suppose we have an assertion P(n) about the positive integers.

Then if we show both of (i) and (ii) below, then P(n) is true for all n >= 1.

(i). P(1) is true

(ii). For each k >= 1: If P(k) is true, then P(k+1) is true.

So to prove that we could argue like this:

For n = 1, the result is clearly true since .

Now suppose that for integer k >= 1, . We will be finished if we can show that . But we have,

and so the result follows by induction.

Theorem. Suppose that m is a fixed integer and .
Then for every integer n >= 1, .

Proof. We will argue by induction. This result is trivial for n=1 it just says that if , then . Hard to argue with that!

Now assume that for some integer k >= 1, . Since and since multiplying corresponding sides of congruences is still a congruence, . But his last expression reduces to . Hence the result follows by induction.

Note: Induction arguments don't always start with the case n = 1. Sometimes we want to prove that an assertion is true for all integers n >= m for some other integer m. In that case we can use the slightly more general version of induction below.