Example 16.5.

Show that using only 5c/ stamps and 9c/ stamps, any postage amount 32c/ or greater can be formed. Proof. Basis: 32c/ can be formed by using one 5c/ stamp and three 9c/ stamps. Inductive Step: Now suppose we can form nc/ postage for some n 32. We need to show we can form (n + 1)c/ postage. Since n 32, when we form nc/ postage, we must use either (1) at least seven 5c/ stamps, or (2) at least one 9c/ stamps. For if both of those possibilities are wrong, we will have at most 30c/ postage. case 1: If there are seven (or more) 5c/ stamps in the nc/ postage, remove seven 5c/, and put in four 9c/ stamps. Since we removed 35c/ and put back 36c/, we now have (n + 1)c/ postage. case 2: If there is one (or more) 9c/ stamps in the nc/ postage, remove one 9c/, and put back two 5c/. Since we removed 9c/ and put back 10c/, we now have (n + 1)c/ postage. So, in any case, if we can make nc/ postage for some n 32, we can form (n + 1)c/ postage. Thus, by induction, we can make any postage amount 32c/ or greater.

(1)Use the first form of induction (see example 16.5) to show that using only 4/c stamps and 7/c stamps, any postage amount 18/c or greater can be formed.

(2)Redo the previous problem using the second form of induction (see example in the text). The basis step is just a bit messier this time, but the inductive step is much easier.