Search

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, 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:

• (*)  For all n > 0, n3 < n2

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.

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:

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

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

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

Study Skills Survey

Tutoring from Purplemath
Find a local math tutor