An Introduction to Induction Proofs

"Can't you prove anything is true, if you start by assuming that it's true in the first place? What's left to prove, if you've already assumed? Isn't this whole thing cheating somehow?"

Well...

First off, don't get mad at your instructor and your textbook's authors. Induction makes perfect sense to them, and they honestly think they've explained it clearly.

When I took this stuff, I know I had a good professor, so I know I got a good lesson. I knew that Prof Mazumdar had given us probably the best explanation that we were likely to get.

But... nah; I still didn't trust induction.

I'll try to pick up where your instructor left off, and fill in some of the holes.

What does "induction" mean?

Induction has many definitions, including that of using logic to come draw general conclusions from specific facts. This definition is suggestive of how induction proofs involve a specific formula that seems to work for some specific values, and applies logic to those specific items in order to prove a general formula.

What is proof by induction?

Proofs by induction take a proposed formula that works in certain specific locations (that you've checked), and applies logic and a specific set of steps to prove that the proposed formula is valid; that is, that the formula works "everywhere". (In the context of induction proofs, "everywhere" is almost always "the natural numbers", or some subset of them, such as n ≥ 5.

What are the three parts of a proof by induction?

To do a proof by induction, you start with a formula that you're wanting to prove. Then the main components of the proof are:

1. the base step, where you show that the formula works for n = 1 (or some other specific starting point).
2. the inductive hypothesis (or assumption step), where you assume that the formula works for some generic natural number n = k
3. the inductive step, where you use the induction hypothesis to prove that the formula works for n = k + 1

What are the steps of an inductive proof?

In order to do a proof by induction:

1. Write out the formula that you're wanting to prove.
2. Show that the formula works for some one actual number; this is called the "base" step.
3. Write out the formula, plugging k in place of n; you will be assuming that the formula works for a generic k, so this is the assumption step (also called the inductive hypothesis).
4. Write out the formula again, this time plugging k + 1 in place of n; this is the induction step.
5. Find a way to replace some of the information in the formula in (4) with the assumption-step info in (3).
6. Simplify, and find some way to restate the results so that they explicitly match the formula that you're trying to prove.

The lists above are all fine and good, but what do they mean in practice? What is the logic, what is the reasoning, that is going on with an inductive proof? What is the point of these steps? Here's the thinking:

Suppose you have been working with some numbers, and have noticed something that seems to be a pattern. To use the standard example, let's say that you have noticed that the sum of all the natural numbers from 1 to n, like this:

...you get a total that equals this:

That is, for every number that you've checked so far, you have found the following relationship to be true:

For convenience, we'll call this formula "(*)", or "star".

You'd like to know if (*) is true for all whole numbers, but you obviously can't check every single whole number, since the whole numbers never end. You only know that it's true for the relatively few numbers that you've actually checked. Of course, adding up all those numbers quickly becomes tedious, so you'd really like for (*) to work!

But to use (*) for whatever number you'd like, you somehow have to prove that (*) actually works everywhere. Induction proofs allow you to prove that the formula works everywhere without your having to actually show that it works everywhere (by somehow doing the infinitely-many additions).

So you have the first part of an induction proof; namely, the formula that you'd like to prove:

Now we move on to the next step: Is (*) ever true anywhere? If you can't find any place, any particular number, for which (*) is known to be true, then there's really no point in continuing.

So you do the second part (which you'd kind of already done; it's how you came up with the formula in the first place), which is to show that (*) is indeed true in some particular place. But, to be formal and correct, let's prove the formula at the first place where (*) is true; namely, at n = 1.

(In what follows, "LHS" refers to the left-hand side of an equation or formula, and "RHS" refers to the right-hand side.)

There; we've shown that (*) works in some particular, named place. But does it work anywhere else?

Well, that was our problem in the first place: we already knew that (*) worked in a few places. We need to prove that (*) works everywhere, and we'll never do that by proving one case at a time. So we need the third and fourth parts of the induction proof.

The third part is the assumption step:

This assumption step is not the same as the base step, where we named an actual place where (*) worked. To the contrary, this part just says "Let's assume that (*) works, somewhere, out there in space, I'm not saying where, I don't maybe even know where; just somewhere."

And you think "So what?" Here's what: the fourth step, the induction step.

If, assuming (*) works at n = k, we can then prove that (*) then works at n = k + 1 (that is, if it works some place, then it must also work at the next place), then, because we do in fact know of a certain place (namely, n = 1) where (*) works, we will then have proved that (*) works everywhere.

The above explicitly shows all my reasoning. The logical proof itself, absent the commentary, will look more like the following:

What is the logic of induction proofs?

The logic of induction proofs has you show that a formula is true at some specific named number (commonly, at n = 1). It then has you show that, if the formula works for one (unnamed) number, then it also works at whatever is the next (still unnamed) number. And since the formula does work for the specific named number, then the formula works at the next number, and the next, and the next, ad infinitum.

In other words, we assume that a formula (*) works as some generic unnamed faceless number k, and we then try to show that (*) works at the next generic number, being k + 1. Suppose we are successful in this, and that we can show that (*) does in fact work at a specific (non-generic) number (let's stick with n = 1). Then, by induction, we know that (*) works at 2 and, by induction, it works at 3 and, by induction, it works at 4, and so forth.

This is the power of proof by induction. The assumption and induction steps allow us to make the jump from "It works here and there" to "It works everywhere!" It's kinda like dominoes: instead of knocking each one down individually, you say "If I can knock down one of them, then that one will knock down the next one, and then the next one, and eventually all of them; and — look! — I can knock down this first one right here."