If you're reading this lesson, then you've probably just covered induction proofs in your algebra class, and you're feeling somewhat uneasy about the whole thing. Believe me: I felt the exact same way.
You may even be having some of the same thoughts that I had:
Content Continues Below
"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?"
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.
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.
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.
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:
In order to do a proof by induction:
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:
1 + 2 + 3 + 4 + ... + n
...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:
(*) For all natural numbers n, 1 + 2 + 3 + 4 + ... + n =
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.
Content Continues Below
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.)
Let n = 1. Then the LHS of the formula is 1 + 2 + 3 + 4 + ... + n, which is actually just 1. Plugging into (*)'s RHS, we get:
Then we get 1 = 1, so (*) is true at n = 1.
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:
Let n = k.
Assume that, for n = k, (*) works; that is, assume that:
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 induction step starts out with:
Let n = k + 1
The complete expansion of the LHS of (*) for this step is:
Then 1 + 2 + 3 + 4 + ... + k + (k + 1)
Only the last term in the above expression is from the k+1-th case. I'll mark off (with square brackets) the part that matches the assumption step:
[1 + 2 + 3 + 4 + ... + k] + k + 1
Now (and this is a fairly common tactic) I can replace the bracketed part in the above with the expression from the RHS of the assumption step:
To add these expressions together (which seems a sensible next step), I'll need common denominators:
Now I can combine the two fractions:
I'll pull the k + 1 factor out front:
For this result to be helpful, I'll need to find a way to restate it in terms not of just k, but of k + 1. Fortunately, this (usually) just involves regrouping in some manner, so I'll do that:
And this is the RHS of (*) for the k + 1 case.
The above explicitly shows all my reasoning. The logical proof itself, absent the commentary, will look more like the following:
Prove: For n ≥ 1, 1 + 2 + 3 + 4 + ... + n =
Let n = 1. Then:
LHS: 1 + 2 + ... n = 1
So (*) holds for n = 1
Assume that, for n = k, the following is true:
1 + 2 + 3 + ... + k =
Let n = k + 1. Then:
Clearly, the LHS equals the RHS, so the statement is proven for n = k + 1, and thus the statement is true for all natural numbers.
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."