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.

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:

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