Induction Proof Let P(n) be the statement that a postage of n cents can be forme
ID: 3010693 • Letter: I
Question
Induction Proof
Let P(n) be the statement that a postage of n cents can be formed using just 3-cent stamps and 5-cent stamps. The parts of this exercise outline a strong induction proof that P(n) is true for postages of 8 cents or greater. a. Basis Step: Show that the statement is true for postages of 8, 9, and 10 cents. b. Inductive Hypothesis: What is the inductive hypothesis? c. Need to show: What do you need to show? d. Complete the inductive step for k greaterthanorequalto 10. e. Conclusion: Write a conclusion.Explanation / Answer
(a) 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5, so that P(8), P(9), and P(10) are true.
(b) The inductive hypothesis is that P(n) is true for 8 n k, where k 10. (Notice that this is a strong induction proof, which requires a stronger hypothesis.)
(c) We need to prove in the inductive step that P(k + 1) is true.
(d) If k 10, then k + 1 = (k 2) + 3. Since k 2 8, by the induction hypothesis we have that P(k 2) is true, i.e., a postage of k 2 cents can be paid by using 3-cent and 5-cent stamps. Adding one 3-cent stamp, we can pay a postage of k + 1 cents, i.e., P(k + 1) is true.
(e) Of course, in this question, it is assumed that 3-cent stamps are also available, because otherwise only postage of 5 or 10 cents can be paid. The answer to the first question is “no”, e.g., a postage of 10 cents cannot be paid if we are allowed to use no more than one 5-cent stamp. The answer to the second question is “yes”, because we obtain 8, 9, and 10 using no more than two 5-cent stamps (and, perhaps, some 3-cent stamps), and the argument in the inductive step shows that we can obtain all other amounts from 8, 9, or 10 by just adding a certain number of 3-cent stamps. (Any integer is congruent to either 8 or 9 or 10 modulo 3.)