Strong Induction

Induction, in one form or another, is the main tool that computer scientists use to prove properties of the systems that they build. Induction has many forms, some of which are much more suitable to certain situations than others, so it's a good idea to know the many different forms.

Curiously enough, most of the different forms of induction boil down to good old mathematical induction. So in some sense, all one really needs to learn is mathematical induction. Nevertheless, the "boiling down" of the different forms to mathematical induction is not completely trivial, so it still makes sense to learn the others.

Recall that mathematical induction goes as follows:

If you want to prove something about all the natural numbers, forall n, P(n), it suffices to prove that

1. P(0)
2. forall k, P(k) implies P(k+1)

Mathematical induction is directly applicable in many situations, but it also falls down in some cases. For example, suppose you want to prove some property about binary trees and try to do induction on the height of the tree. You'd like to use the induction hypothesis to prove the property in question for the sub-trees. However, the height of each sub-tree is not necessarily one less than the height of the current tree (the height could be even less). Thus, you wouldn't be able to apply the induction hypothesis to each sub-tree.

In this situation, strong induction (a.k.a. complete induction or course of values induction) is a a much better fit (and structural induction is an even better fit, but I'll wait to talk about that). Recall that strong induction goes as follows:

To prove a property about all integers, forall n, P(n), it suffices to prove that for any k, if for any m where m < k, you have P(m), then P(k).

So the nice thing about strong induction is that you get to assume that the property is true of all the natural numbers less than k, instead of just k - 1 as is the case in mathematical induction.

Even though strong induction is much easier to apply in many situations than mathematical induction, strong induction boils down to mathematical induction. Here's the proof of strong induction by use of mathematical induction.

As with many proofs, the strong induction principle cannot be proved directly by induction, but instead a slightly stronger version can be proved instead. This seems unintuitive! Why would something stronger be easier to prove? The reason is that when proving something by induction, in the induction step you get to assume what you're trying to prove (for n-1) so the stronger the property, the more horsepower you have to get through the induction step. In this case, instead of proving forall k, P(k) we'll prove that forall j, forall k < j, P(k). It's easy to see that the later implies the former. Just pick j=k+1 and you have P(k).

Lemma. If (forall n, (forall k < n. P k) implies P n), then (forall j, forall k < j, P(k)).

The proof is by mathematical induction on j.

Base case (j=0):

There are no k < 0, so this case is vacuously true.

Induction step:

The induction hypothesis is: if (forall n, (forall k < n. P(k)) implies P(n)), then (forall k < j. P(k)). We need to show the corresponding property for j + 1. We proceed by assuming that

forall n, (forall k < n. P(k)) implies P(n) (call this fact H)

and need to prove that forall k < j+1, P(k). We then pick an arbitrary k less than j+1 and need to show that P(k). Note that by the induction hypothesis combined with H, we know that

forall m < j. P(m) (call this fact A).

Now, because k < j+1 we have two cases to consider:

Case k < j: We can apply fact A to conclude that P(k). Note that without the modification to strengthen this lemma, we would have been stuck here.

Case k = j: From fact A and H, we have P(j). But since j=k we can conclude that P(k).

QED.

Here is a version of the above proof written in a machine-checkable language (Isabelle).