If you're anything like I was, you're probably feeling a bit queasy about that assumption step. I mean, if we assume something is true, can't we prove anything?
Well, actually, no. But I'll bet your text gives you a list of formulas, and asks you to "try to prove..." or "determine whether true...", and, whaddya know, they all turn out to be true! So, in spite of their good intentions, your teacher and your book have been quite misleading. To help you feel more confident about induction, let's try to prove a couple of statements that we know are wrong, so you can see that you can't use induction to prove something that ain't so. Here's the first one:
We know perfectly well that this statement just isn't so: cubes of whole numbers are bigger than squares (except for the cube and square of 1, where they're equal). But let's try to prove this false statement, and see what happens.
Let n = 1. Then n3 = 13 = 1 and n2 = 12 = 1, and 1 < 1.
Then (*) holds for n = 1.
Hmm...that's weird; the first part worked. Well, let's continue, and see what happens:
Let n = k.
Assume that, for n = k, we have k3 < k2.
For this next bit, just trust me: everything will become clear at the end:
Let n = k + 1.
Whatever k is, we know that three of their square is bigger than just one of their square; that is, 3k2 > k2, because k2 > 0.
Also, we know that three of the value is bigger than two; that is, 3k > 2k, because k > 0.
Also, we know that k3 > 0, because k > 0.
Also, 1 > 1. Copyright © Elizabeth Stapel 2000-2011 All Rights Reserved
Adding together all the left-hand sides and all the right-hand sides above, we get:
k3 + 3k2 + 3k + 1 > k2 + 2k + 1
...and this can be restated as:
(k + 1)3 > (k + 1)2
But we needed to prove just the opposite!!
That is, (*) failed the induction step. Even if (*) is true in some one place, it will not be true at the next place. So, even though (*) was true for n = 1, it was not true for n = 2, and (*) fails, as we knew it ought to!
Let's try another one. In this one, we'll do the steps out of order:
Any child capable of counting on his fingers knows that this isn't true! But let's see what happens if we assume that it is true somewhere:
Let n = k. Assume, for n = k, that (*) holds; that is, assume that k + 1 < k
Let n = k + 1. Then:
(k + 1) + 1 < (k) + 1 = (k + 1)
(k + 1) + 1 < (k + 1)
...and (*) holds for n = k + 1.
Well, that's a bit disturbing: if (*) is true anywhere, then it's true everywhere. Ah, but we haven't shown (*) to be true anywhere! And that's where the induction proof fails in this case. You can't find any number for which this (*) is true. Since there is no starting point (no first domino, as it were), then induction fails, just as we knew it ought to.
I hope these examples, in showing that induction cannot prove things that are not true, have increased your confidence in the technique. Induction is actually quite powerful and clever, and it would be a shame for you not to have caught a glimpse of that.