## Strong Induction Wasn’t Needed After All

Lately when I’ve taught the second principle of mathematical induction – also called “strong induction” – I’ve used the following example to illustrate why we need it.

Prove that you can make any amount of postage of 12 cents or greater using only 4-cent and 5-cent stamps.

At this point in a class we would have just done several examples using regular induction, and so we would be naturally inclined to try to prove this postage stamp problem using that technique.  The base case is easy: Just use three 4-cent stamps to make 12 cents of postage.  The induction hypothesis is as usual, too: Suppose, for some $k \geq 12$, that we can make k cents’ worth of postage using only 4-cent and 5-cent stamps.  But regular induction fails at the induction step: To prove that you can make $k+1$ cents using only 4-cent and 5-cent stamps, knowing that you can make k cents isn’t helpful, since you can’t add either a 4-cent or a 5-cent stamp to k cents’ worth of postage to generate $k+1$ cents’ worth of postage.  Instead, you need to know that you can make, say, $k-3$ cents’ worth of postage.  Then you can add a 4-cent stamp to that amount to produce your $k+1$ cents.  In other words, you need to assume in the induction hypothesis not that you can make k cents but that you can make $12, 13, \ldots, k$ cents.  And that’s the essence of strong induction.

However, before we get to this realization my students will often suggest that we can produce $k+1$ cents from k cents by simply removing one of the 4-cent stamps used to produce k cents and replacing it with a 5-cent stamp.  This is a good idea.  However, it assumes that we actually used at least one 4-cent stamp to produce k cents, and that’s a faulty assumption.  Sometimes we don’t need a 4-cent stamp, such as if we use three 5-cent stamps to produce 15 cents.  (In fact, for 15 cents we must use only 5-cent stamps.)  If we don’t use any 4-cent stamps then we can’t generate $k+1$ cents from k cents by replacing a 4-cent stamp with a 5-cent one.

Normally the students are a little chagrined that this idea fails.  And that happened again this term.  After discussing the idea and why it doesn’t quite work I was about ready to move on and introduce strong induction when one of my students interjected, “I’ve got it!  I’ve got it!”  He pointed out that if we’re going to use only 5-cent stamps to generate k cents, when $k \geq 12$, then we’ll need at least three of them.  That’s true, I said.  Then, he added, if we have at least three 5-cent stamps to make k cents, we can replace them with four 4-cent stamps to yield $k+1$ cents’ worth of postage.  That covers the remaining case.  I was impressed enough that I applauded the class for their collective work in solving the problem.

To recap: You don’t actually need strong induction to solve the stamp problem described above.  Use regular induction, and break the induction step into two cases: (1) If you use at least one 4-cent stamp to make k cents, replace it with a 5-cent stamp to make $k+1$ cents.  (2) If you only use 5-cent stamps to make k cents, you’ll need at least three of them.  Replace those three with four 4-cent stamps to generate $k+1$ cents’ worth of postage.

Well done, Spring 2020 Math 210 students!

This entry was posted in number theory, proof techniques. Bookmark the permalink.