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 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

Answer:a) Show that the statements P(18), P(19), P(20), and P(21) are true,

completing the basis step of the proof.

answer: P(18) = 4 + 7 + 7, P(19) = 4 + 4 + 4 + 7,

P(20) = 4 + 4 + 4 + 4 + 4, P(21) = 7 + 7 + 7,

b) The statement that using just 4-cent and 7-cent stamps we

can form j cents postage for all j with 18 ≤ j ≤ k, where we assume

that k ≥ 21

c. ) Assuming the inductive hypothesis, we can form k + 1 cents

postage using just 4-cent and 7-cent stamps.

d) Because k ≥ 21, we know that P(k − 3) is true, that is,

that we can form k − 3 cents of postage. Put one more 4-cent stamp

on the envelope, and we have formed k + 1 cents of postage.

e) We have completed both the basis step and the

inductive step, so by the principle of strong induction, the statement

is true for every integer n greater than or equal to 18.

Step-by-step explanation: