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

Well...

Affiliate

Advertisement

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:

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

In order to do a proof by induction:

- Write out the formula that you're wanting to prove.
- Show that the formula works for some one actual number; this is called the "base" step.
- 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). - Write out the formula again, this time plugging
*k*+ 1 in place of*n*; this is the induction step. - Find a way to replace some of the information in the formula in (4) with the assumption-step info in (3).
- 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:

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

RHS:

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.

Affiliate

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

URL: https://www.purplemath.com/modules/inductn.htm

© 2024 Purplemath, Inc. All right reserved. Web Design by