Strong induction

What is the best way to explain induction to a student?  That is, given a true-or-false statement P(n) involving a natural number n \geq 0, we would like to prove that the statement is true for all such n \geq 0.  How does one prove such a claim, when it seems to require checking an infinite number of cases?  My motivation for this thinking-out-loud post involves a particular form of induction whose presentation in some textbooks may cause students some confusion (or at least, it did cause confusion in at least one student).

Often the first exposure to induction is the so-called “weak” form: to show that P(n) is true for all n \geq 0, it suffices to prove the following two claims:

  • Base step: P(0) is true.
  • Induction step: For all n \geq 0, if P(n) is true, then P(n+1) is true.

That is,

(P(0) \land \forall n \geq 0 P(n) \Rightarrow P(n+1)) \Rightarrow \forall n \geq 0 P(n)

So far, so good.  Although this is technically all that we need, that this is referred to as “weak” induction suggests that there is a stronger form.  There is… sort of.  In his Applied Combinatorics (see Reference 1 below), Tucker skips weak induction altogether, presenting induction in the following “strong” form:

  • Base step: P(0) is true.
  • Induction step: If P(0), P(1), P(2), \ldots, P(n-1) are true, then P(n) is true.

The idea is that the induction hypothesis is stronger, which can make the resulting proof simpler; in the process of proving P(n) in the induction step, we have at our disposal not only the assumed truth of P(n-1), but also all of the other previous statements.  (I say “sort of,” and wrap “weak” and “strong” in quotes, because the two forms are actually equivalent.  Strong induction isn’t really any stronger in the sense of more “proving power”; statements provable using strong induction are also provable by weak induction, and vice versa.)

Notice that the induction step above, quoted directly from Tucker, lacks some rigor in that there is no explicit universal quantifier for n.  That is, for what values of n do we need to demonstrate the induction step?  This is important, because it turns out that if we are more careful, we can economize a bit and demonstrate that P(n) is true for all n \geq 0 by proving the single more compact claim:

  • Strong induction “single-step”: For all n \geq 0, if P(k) is true for all k<n, then P(n) is also true.

That is,

(\forall n \geq 0 (\forall k<n P(k)) \Rightarrow P(n)) \Rightarrow \forall n \geq 0 P(n)

Velleman (Reference 2) takes this presentation approach, which certainly has elegance going for it.  But he then goes on to “note that no base case is necessary in a proof by strong induction [my emphasis].”  This is where I think things can get confusing.  It’s certainly true that, once we have demonstrated the implication in the single-step version above, then we know that P(0) is true.  As Velleman explains, “plugging in 0 for n, we can conclude that (\forall k<0 P(k)) \Rightarrow P(0).  But because there are no natural numbers smaller than 0, the statement \forall k<0 P(k) is vacuously true.  Therefore, by modus ponens, P(0) is true.  (This explains why the base case doesn’t have to be checked separately in a proof by strong induction [my emphasis]; the base case P(0) actually follows from the modified form of the induction step used in strong induction.)”

There is nothing strictly incorrect here.  What may be misleading, though, is the repeated assurance that no special attention is required for treatment of the base case.  When writing the actual proof of the implication in the single-step version of strong induction, the argument may “look different” for n=0 than it does for n>0.  I think Wikipedia actually does the most admirable job of explaining this wrinkle: “Sometimes the same argument applies for n=0 and n>0, making the proof simpler and more elegant.  In this method it is, however, vital to ensure that the proof of P(n) does not implicitly assume that n>0, e.g. by saying “choose an arbitrary k<n” or assuming that a set of n elements has an element [my emphasis added].”

From a teaching perspective, what are good examples of induction proofs that highlight these issues?  This is a good question.  When discussing strong induction, the most common example seems to be the existence part of the fundamental theorem of arithmetic: every integer greater than 1 is the product of one or more primes.  Here we really can make just one argument, so to speak, without treating the first prime number 2 as a special base case (interestingly, Wikipedia does address it separately).

In a course on graph theory, I think another nice example is the proof that any round-robin tournament contains a Hamiltonian path.  Again, the single-step version of a strong induction argument works here as well (although we have to be a little more careful about what happens when some constructed subsets of vertices end up being empty).

Finally, another common example where strong induction is useful, but special treatment of base case(s) is required, involves postage stamps: show that it is possible to use 4- and 5-cent stamps to form every amount of postage of 12 cents or more.

References:

  1. Tucker, Alan, Applied Combinatorics, 6th ed. New York: Wiley and Sons, 2012
  2. Velleman, Daniel J., How to Prove It: A Structured Approach. New York: Cambridge University Press, 2006
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s