CHAPTER 5. RIGOROUS MATHEMATICAL INDUCTION (2) is the tough one. What does it say? Read it out loud, write it down in an English sentence, think about it. Compare it to the regular old PMI we stated and proved in the previous section. Why would we call this one strong? How are these theorems dierent? Are their hypotheses dierent? What about their conclusions? Take a few minutes break from reading to ponder these questions. Then, read on . . . Okay, lets explain this theorem. Notice that the only dierence between The Strong PMI (Theorem 5.4.1) and The Regular PMI (Theorem 5.2.2) lies in condition (2), which governs what we do in the induction hypothesis part of a proof. The setup (that we have a variable proposition) and condition (1) (the N) are identical. base case) and the conclusion (that P (n) holds for every n Lets compare condition (2), now.

The Regular PMI requires that P (k) is sucient to allow us to deduce P (k + N. If we can achieve that (the domino toppling aect), and 1), for every k N. This is what we do in we have a Base Case, then P (n) holds for every n the IH and IS of an induction proof: suppose P (k) holds and use it to deduce P (k + 1) necessarily holds, too. Lets rewrite condition (2) of The Strong PMI to see what it says: k N. (cid:0) P (1) P (2) P (3) P (k) (cid:1) = P (k + 1) That is, Strong PMI requires that all of the previous instances of the proposition (P (1) and P (2) and P (3) and . . . and all the way until P (k)) are together sucient to allow us to deduce P (k + 1). This theorem seems to say, Hey, dont worry about using just P (k) to get to P (k + 1); you can actually use all of the statements P (1) through P (k) to get there! The desired conclusionthat N. P (n)will still follow! Isnt that nice?

We can address aspect (3) quickly right now, before showing you some examples later on. The only dierence between a Strong Induction proof and a Regular Induction proof will be in the IH and the IS. When using Strong Induction, in the IH we will suppose P (1) and P (2) and . . . and P (k) all hold, then use them to deduce P (k + 1) necessarily holds, too. In the IS, we will just have to be careful about pointing out which of the assumptions of the IH we use.

To address aspect (2)when to use Strong Inductionwe will show you several examples. In working through these examples, we will point out precisely why a regular induction proof would fail. By seeing several instances of this, we hope to develop some intuition for when to recognize these situations in the future. That is, we will learn to realize what kinds of claims require a strong IH in their proof. Lets address aspect (1) right now, because it is the most pressing. Before we race on and start using a proof technique, we want to make sure its actually mathematically valid! If youre like us, youre wondering, How is this theorem 5.4. STRONG INDUCTION even True? It says that we need to know a whole lot more about how the instances of P (n) relate to each other. Why should we be allowed to make so many assumptions in the IH and be able to use them later?