Subsection 8.9.3 Induction Can be an Alternative Even When Other Proofs Exist
Many of the claims that we can prove by induction can also be proved in other ways. This shouldn’t come as a surprise. We’ve already seen many other examples in which there existed more than one proof for a given claim.
Recall the stamp problem, which we’ve already proved using Case Enumeration:
Suppose that the postage required to mail a letter is always at least 6¢. Prove that it is possible to apply any required postage to a letter given only 2¢ and 7¢ stamps.
P(n) It is possible to apply n¢ using only 2¢ and 7¢ stamps.
Base case: Let b = 6. We can apply 6¢ by applying three 2¢ stamps.
Induction step: Prove:
[1] possible to apply n¢ possible to apply (n+1)¢
Induction hypothesis: possible to apply n¢
We’ll now use Case Enumeration:
To apply n¢, we used at least one 7¢ stamp. In that case, to apply (n+1)¢, remove the 7¢ stamp and add four 2¢ stamps. We’ve added 1¢ to the total postage.
To apply n¢, we used only 2¢ stamps. Since n is at least 6, we must have used at least three of the 2¢ stamps. Remove three of them and add one 7¢ stamp. We’ve added 1¢ to the total postage.
So, by the Principle of Mathematical Induction, we have that it is possible to apply any required postage (i.e., any amount that is at least 6¢).
