The
Purplemath Forums 
Induction
Proofs: 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:
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^{3} = 1^{3} = 1 and n^{2} = 1^{2} = 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^{3} < k^{2}. 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, 3k^{2} > k^{2}, because k^{2} > 0. Also, we know that three of the value is bigger than two; that is, 3k > 2k, because k > 0. Also, we know that k^{3} > 0, because k > 0. Also, 1 > 1. Copyright © Elizabeth Stapel 20002011 All Rights Reserved Adding together all the lefthand sides and all the righthand sides above, we get: k^{3} + 3k^{2} + 3k + 1 > k^{2} + 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) ...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 © 20002012 Elizabeth Stapel  About  Terms of Use 




