Math for CS: Induction

Induction is a powerful method for showing a property is true for all non-negative integers. Induction plays a central role in discrete mathematics and computer science. In fact, its use is a defining characteristic of discrete—as opposed to continuous—mathematics. This chapter introduces two versions of induction, Ordinary and Strong, and explains why they work and how to use them in proofs.

We are given the induction principle, which states the following. Let P be a predicate on non-negative integers. If P(0) is true, and P(n) implies P(n+1) for all non-negative integers, n, then P(m) is true for all non-negative integers, m.

Induction Template

We are then given a familiar example along with a template for applying an induction proof.

Five components of the template:

1. State that the proof uses induction. This immediately conveys the overall structure of the proof, which helps your reader follow your argument.
2. Define an appropriate predicate P(n). The predicate P(n) is called the induction hypothesis. The eventual conclusion of the induction argument will be that P(n) is true for all nonnegative n. A clearly stated induction hypothesis is often the most important part of an induction proof, and its omission is the largest source of confused proofs by students. In the simplest cases, the induction hypothesis can be lifted straight from the proposition you are trying to prove, as we did with equation (5.1). Sometimes the induction hypothesis will involve several variables, in which case you should indicate which variable serves as n.
3. Prove that P(0) is true. This is usually easy, as in the example above. This part of the proof is called the base case or basis step.
4. Prove that P(n) implies P(n+1) for every nonnegative integer n. This is called the inductive step. The basic plan is always the same: assume that P(n) is true and then use this assumption to prove that P(n+1) is true. These two statements should be fairly similar, but bridging the gap may require some ingenuity. Whatever argument you give must be valid for every nonnegative integer n, since the goal is to prove that all the following implications are true: P(0) implies P(1), P(1) implies P(2), P(2) implies P(3), …
5. Invoke induction. Given these facts, the induction principle allows you to conclude that P(n) is true for all nonnegative n. This is the logical capstone to the whole argument, but it is so standard that it’s usual not to mention it explicitly.

Always be sure to explicitly label the base case and the inductive step. Doing so will make your proofs clearer and will decrease the chance that you forget a key step—like checking the base case.

We are walked through an example where we need a stronger induction hypothesis in order to prove by induction. The author notes that it is not always immediately obvious what a more clever induction hypothesis could be. They mentioned that it took mathematicians over 20 years to prove something by induction. It ended up taking a clever induction hypothesis.

We are also walked through a bogus proof.

Strong induction.

A useful variant of induction is called strong induction. Strong induction and ordinary induction are used for exactly the same thing: proving that a predicate is true for all nonnegative integers. Strong induction is useful when a simple proof that the predicate holds for n + 1 does not follow just from the fact that it holds at n, but from the fact that it holds for other values <= n.

Strong induction vs. induction vs. well-ordering

Strong induction looks genuinely “stronger” than ordinary induction —after all, you can assume a lot more when proving the induction step. Since ordinary induction is a special case of strong induction, you might wonder why anyone would bother with the ordinary induction. But strong induction really isn’t any stronger, because a simple text manipulation program can automatically reformat any proof using strong induction into a proof using ordinary induction—just by decorating the induction hypothesis with a universal quantifier in a standard way. Still, it’s worth distinguishing these two kinds of induction, since which you use will signal whether the inductive step for n + 1 follows directly from the case for n or requires cases smaller than n, and that is generally good for your reader to know. The template for the two kinds of induction rules looks nothing like the one for the Well Ordering Principle, but this chapter included a couple of examples where induction was used to prove something already proved using well ordering. In fact, this can always be done. As the examples may suggest, any well ordering proof can automatically be reformatted into an induction proof.

So theoretically, no one need bother with the Well Ordering Principle either. But it’s equally easy to go the other way, and automatically reformat any strong induction proof into a Well Ordering proof. The three proof methods—well ordering, induction, and strong induction—are simply different formats for presenting the same mathematical reasoning! So why three methods? Well, sometimes induction proofs are clearer because they don’t require proof by contradiction. Also, induction proofs often provide recursive procedures that reduce large inputs to smaller ones. On the other hand, well ordering can come out slightly shorter and sometimes seem more natural and less worrisome to beginners. So which method should you use? There is no simple recipe. Sometimes the only way to decide is to write up a proof using more than one method and compare how they come out. But whichever method you choose, be sure to state the method up front to help a reader follow your proof.