Print-friendly page

Induction Proofs:
     Examples of where induction fails (page 2 of 3)

Sections: Introduction, Examples of where induction fails, Worked examples

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, we'll try to prove a couple of statements that we know are wrong, to show you that you can't use induction to prove something that ain't so. Here's the first one:

• (*)  For all n > 0, n³ < n²

Now, 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 n³ = 1³ = 1 and n² = 1² = 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 k³ < k².

For this next bit, just trust me: everything will become clear at the end:

Let n = k + 1.

Whatever k is, we know that 3k² > k², because k² > 0.

Also, we know that 3k > 2k, because k > 0.

Also, we know that k³ > 0, because k > 0.

Also, 1 > 1.   Copyright © Elizabeth Stapel 2006-2008 All Rights Reserved

Adding these together, we get:

k³ + 3k² + 3k + 1 > k² + 2k + 1

...and this can be restated as:

(k + 1)³ > (k + 1)²

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 (*) is true for n = 1, it is 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:

• (*)  For all n, n + 1 < n

Now, 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)

...so:

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

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

  Copyright © 2006-2008  Elizabeth Stapel   |   About   |   Terms of Use

 Feedback   |   Error?