Question

Let P(n) be the statement that a postage of n cents can be formed using just 4-cent stamps and 7-cent stamps. The 342 5 / Induction and Recursion parts of this exercise outline a strong induction proof that P(n) is true for n ≥ 18. a) Show statements P(18), P(19), P(20), and P(21) are true, completing the basis step of the proof. b) What is the inductive hypothesis of the proof? c) What do you need to prove in the inductive step? d) Complete the inductive step for k ≥ 21. e) Explain why these steps show that this statement is true whenever n ≥ 18.

Answer 1

See explanation

Explanation:

Statement: P(n) = "a postage of n cents can be formed using just 4-cent stamps and 7-cent stamps".

A. P(18) = a postage of 18 cents can be formed using two 7-cent stamps and one 4-cent stamp.

P(19) = a postage of 19 cents can be formed using one 7-cent stamp and three 4-cent stamps.

P(20) = a postage of 20 cents can be formed using five 4-cent stamps.

P(21) = a postage of 21 cents can be formed using three 7-cent stamps.

B. Inductive hypothesis is to assume that P(n) is true for all n < 18

C. In the inductive step we need to prove that P(n+1) is true.

D. Let k ≥ 21, then

• if k = 4l, we get the case of P(20);
• if k = 4l + 1, we get the case of P(21);
• if k = 4l + 2, we get the case of P(18);
• if k = 4l + 3, we get the case of P(19).

E. Since all natural numbers are of the form 4l, 4l + 1, 4l + 2, 4l + 3, we can state that P(n) is true for all n ≥ 18.