 Search

Induction Proofs: Introduction (page 1 of 3)

Sections: Introduction, Examples of where induction fails, Worked examples If you're reading this module, then you've probably just covered induction in your algebra class, and you're feeling somewhat uneasy about the whole thing. If you're anything like me, you're having the same thoughts that I had: "Can't you prove anything is true, if you assume it to be true in the first place? What's left to prove, if you've already assumed? Isn't that cheating somehow?"

Well...

First off, don't get mad at your instructor. Induction makes perfect sense to him, and he honestly thinks he's explained it clearly. When I took this stuff, I know I had a good professor, so I know I got a "good" lesson. But 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 proofs have four components: (1) the thing you want to prove, (2) the beginning step (usually "let n = 1"), (3) the assumption step ("let n = k"), and (4) the induction step ("let n = k + 1"). Here's the thinking:   Copyright © Elizabeth Stapel 2000-2011 All Rights Reserved

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, when you add up all the numbers from 1 to n (that is, 1 + 2 + 3 + 4 + ... + n), you get a total that equals (n)(n+1)/2. That is, for every number that you've checked so far, you get

1 + 2 + 3 + 4 + ... + n = (n)(n+1)/2

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 (*) works everywhere. Induction proofs allow you to prove that the formula works "everywhere" without your having to actually show that it works everywhere (by doing the infinitely-many additions).

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

(*)  For all natural numbers n, 1 + 2 + 3 + 4 + ... + n = (n)(n+1)/2

But 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 is to show that (*) is indeed true in some particular place:

Let n = 1. Then 1 + 2 + 3 + 4 + ... + n is actually just 1; that is:

(n)(n+1)/2 = (1)(1+1)/2 = (1)(2)/2 = 1.

Then we get 1 = 1, so (*) is true at n = 1.

There; we've shown that (*) works in some particular place. But does it work anywhere else? Well, that was our problem in the first place: we know that it works in a few places, but 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 part:

Let n = k.

Assume that, for n = k, (*) works; that is, assume that:

1 + 2 + 3 + 4 + ... + k = (k)(k+1)/2

This is not the same as the second part, where we named the actual place where (*) worked. 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. If we can prove, assuming (*) works at n = k, that (*) then works at n = k + 1 (that is, if it works some place, then it must also work at the next place), then, since we know of a certain place (n = 1) where (*) works, we will have proved that (*) works everywhere:

 Let n = k + 1. Then 1 + 2 + 3 + 4 + ... + k + (k + 1) [the left-hand side of (*)] = [1 + 2 + 3 + 4 + ... + k] + k + 1 [from part three] = [(k)(k+1)/2] + k + 1 [our assumption] = [(k)(k+1)/2] + 2(k+1)/2 [common denominator] = (k)(k+1)+2(k+1)/2 [adding fractions] = (k+2)(k+1)/2 [simplifying] = ((k+1)+1)(k+1)/2 [restating in "k + 1" form]

This last line is the right-hand side of (*). In other words, if we assume that (*) works as some unnamed faceless number k, then we can show (by using that assumption) that (*) works at the next number, k + 1. And we already know of a number where (*) works! Since we showed that (*) works at n = 1, the assumption and induction steps tell us that (*) then works at n = 2, and then by induction (*) works at n = 3, and then by induction, (*) works at n = 4, and so on. 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."

Top  |  1 | 2 | 3  |  Return to Index  Next >>

 Cite this article as: Stapel, Elizabeth. "Induction Proofs: Introduction." Purplemath. Available from     https://www.purplemath.com/modules/inductn.htm. Accessed [Date] [Month] 2016

Study Skills Survey

Tutoring from Purplemath
Find a local math tutor