Page 358 - Discrete Mathematics and Its Applications

5.2 Strong Induction and Well-Ordering 337

situation where there are two piles each with k + 1 − r matches. Because 1 ≤ k + 1 − r ≤ k,
we can now use the inductive hypothesis to conclude that the second player can always win.
We complete the proof by noting that if the first player removes all k + 1 matches from one of
the piles, the second player can win by removing all the remaining matches. ▲

Using the principle of mathematical induction, instead of strong induction, to prove the
results in Examples 2 and 3 is difficult. However, as Example 4 shows, some results can be
readily proved using either the principle of mathematical induction or strong induction.
Before we present Example 4, note that we can slightly modify strong induction to handle
a wider variety of situations. In particular, we can adapt strong induction to handle cases where
the inductive step is valid only for integers greater than a particular integer. Let b beafixed
integer and j a fixed positive integer. The form of strong induction we need tells us that P (n)
is true for all integers n with n ≥ b if we can complete these two steps:
BASIS STEP: We verify that the propositions P(b), P(b + 1),...,P(b + j) are true.
INDUCTIVE STEP: We show that [P(b) ∧ P(b + 1) ∧ ··· ∧ P(k)]→ P(k + 1) is true for
every integer k ≥ b + j.
We will use this alternative form in the strong induction proof in Example 4. That this
alternative form is equivalent to strong induction is left as Exercise 28.

EXAMPLE 4 Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and
5-cent stamps.

Solution: We will prove this result using the principle of mathematical induction. Then we will
present a proof using strong induction. Let P (n) be the statement that postage of n cents can be
formed using 4-cent and 5-cent stamps.
We begin by using the principle of mathematical induction.
BASIS STEP: Postage of 12 cents can be formed using three 4-cent stamps.
INDUCTIVE STEP: The inductive hypothesis is the statement that P(k) is true. That is, under
this hypothesis, postage of k cents can be formed using 4-cent and 5-cent stamps. To complete
the inductive step, we need to show that when we assume P(k) is true, then P(k + 1) is also
true where k ≥ 12. That is, we need to show that if we can form postage of k cents, then we can
form postage of k + 1 cents. So, assume the inductive hypothesis is true; that is, assume that
we can form postage of k cents using 4-cent and 5-cent stamps. We consider two cases, when at
least one 4-cent stamp has been used and when no 4-cent stamps have been used. First, suppose
that at least one 4-cent stamp was used to form postage of k cents. Then we can replace this
stamp with a 5-cent stamp to form postage of k + 1 cents. But if no 4-cent stamps were used,
we can form postage of k cents using only 5-cent stamps. Moreover, because k ≥ 12, we needed
at least three 5-cent stamps to form postage of k cents. So, we can replace three 5-cent stamps
with four 4-cent stamps to form postage of k + 1 cents. This completes the inductive step.
Because we have completed the basis step and the inductive step, we know that P(n) is
true for all n ≥ 12. That is, we can form postage of n cents, where n ≥ 12 using just 4-cent and
5-cent stamps. This completes the proof by mathematical induction.

Next, we will use strong induction to prove the same result. In this proof, in the basis step
we show that P(12), P(13), P(14), and P(15) are true, that is, that postage of 12, 13, 14,
or 15 cents can be formed using just 4-cent and 5-cent stamps. In the inductive step we show
how to get postage of k + 1 cents for k ≥ 15 from postage of k − 3 cents.
BASIS STEP: We can form postage of 12, 13, 14, and 15 cents using three 4-cent stamps, two
4-cent stamps and one 5-cent stamp, one 4-cent stamp and two 5-cent stamps, and three 5-cent
stamps, respectively. This shows that P(12), P(13), P(14), and P(15) are true. This completes
the basis step.