Examples Where Induction Fails
Purplemath
Induction proofs consist of four things — well, one thing (a formula) and three steps; namely, the formula you want to prove, the base step (usually with n = 1), the assumption step (also called the induction hypothesis; either way, usually with n = k), and the induction step (with n = k + 1).
But...
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 and everything is true?
Well, actually, no. But I'll bet your textbook 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 textbook 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 (using (*), pronounced "star", as the formula's name):
- (*) 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.
Base step: 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:
Assumption step: 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:
Induction step: Let n = k + 1.
Whatever k is, we know that three of its square is bigger than just one of its square, because k2 > 0; that is:
3k2 > k2
Also, because k > 0, we know that three of the value is bigger than two; that is:
3k > 2k
Adding this to the previous inequality, we get:
3k2 + 3k > k2 + 2k
Also, we know that k3 > 0, because k > 0. Adding this positive value *only* to the larger side of the inequality, we get:
k3 + 3k2 + 3k > k2 + 2k
Also, 1 ≥ 1. Adding this to both sides, we get:
k3 + 3k2 + 3k + 1 > k2 + 2k + 1
And the above can be restated as:
(k + 1)3 > (k + 1)2
But we were trying to prove the exact opposite of this!
That is, (*) failed in the induction step. Even if (*) were true in some one place, it would not be true at the next place. So, even though (*) was true for n = 1, it was not true for n = 2, and thus (*) fails, as we knew it ought to.
As the above example shows, induction proofs can fail at the induction step. If we can't show that (*) will always work at the next place (whatever that next place or next number is), then (*) simply isn't true.
Let's try another one. In this one, we'll do the steps out of order, because it's going to be the base step that fails this time.
- (*) 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: we've somehow shown that, 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.
In this case, it was the base step that failed. This will not normally be the case, as people aren't likely to spend any great amount of time trying to prove a formula works everywhere when they haven't seen it work *anywhere*. But it's a failure, nonetheless. This confirms that induction will not prove something untrue to be true. Proof by induction is not a cheat.
I hope these examples, in showing that induction cannot prove things that are not true, have increased your understanding of, and confidence in, the technique. Induction is actually quite powerful and really clever, and it would be a shame for you not to have caught a glimpse of that.
© 2024 Purplemath, Inc. All right reserved. Web Design by 