Examples Where Induction Fails

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, n³ ≤ n²

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

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.