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 all integers n ≥ 18. a) Show that the statements P (18), P (19), P (20), and P (21) are true, completing the basis step of a proof by strong induction that P (n) is true for all integers n ≥ 18. b) What is the inductive hypothesis of a proof by strong induction that P (n) is true for all integers n ≥ 18? c) What do you need to prove in the inductive step of a proof that P (n) is true for all integers n ≥ 18? d) Complete the inductive step for k ≥ 21. e) Explain why these steps show that P (n) is true for a

Question

Mathematics

Freedom

13 March, 23:25

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 all integers n ≥ 18. a) Show that the statements P (18), P (19), P (20), and P (21) are true, completing the basis step of a proof by strong induction that P (n) is true for all integers n ≥ 18. b) What is the inductive hypothesis of a proof by strong induction that P (n) is true for all integers n ≥ 18? c) What do you need to prove in the inductive step of a proof that P (n) is true for all integers n ≥ 18? d) Complete the inductive step for k ≥ 21. e) Explain why these steps show that P (n) is true for a

+2

Answers (1)

Know the Answer?

Cristopher Rodgers · Answer 1

We have to show that for n ≥ 18, n can be written as a positive (maybe with some null coefficient) linear combination of 4 and 7.

a)

P (18) is True because 18 = 2*7 + 4, in other words, we can form a postage of 18 cents with two 7-cent stamps and one 4-cent stamp.

P (19) is also true because 19 = 7 + 3*4, in other words, we can form 19 cents with one 7-cent stamps and three 4-cent stamps

P (20) is true because 20 = 5*4, we can form 20 cents with five 4-cent stamps

P (21) is true becase we can form 21 cents with 3 7-cent stamps (3*7 = 21).

b) The inductive hypothesis is that if P (n), P (n+1), P (n+2), and P (n+3) are all true, with n ≥ 18, then P (n+4) is also true.

c) We need to prove, in this case, that P (n+4) is true, using as a fact that P (n), P (n+1), P (n+2) and P (n+3) are all true, this means that, given that we can form postages of n, n+1, n+2 and n+3 cents, with n≥18, then we will also be able to form a postage of n+4 cents.

d) We have that P (n), P (n+1), P (n+2), and P (n+3) are true with n≥18. We want to prove that P (n+4) is true.

Since P (n) is true, then n has the form a * 7 + b * 4, where a and b are positive (or null) integers. Therefore, we can replace n in n+4 and obtain

n+4 = (a*7 + b*4) + 4 = a*7 + (b*4 + 4) = a*7 + (b+1) * 4

This shows that n+4 is a positive (or null) linear combination of 7 and 4. In fact, we can form a postage of n+4 cents with a 7-cent and b+1 4-cent stamps.

This shows that P (n+4) is true.

e) Note that P (n) is true for 4 consecutive numbers, starting from 18 until 21. If we show that the property is still true if we add 4 to a number greater or equal than 18, then we are shoiwing in fact that the property is valid for every number greater than or equal than 18; because we can form any number n > 18 by taking one off 18,19,20 or 21 and adding 4 a sufficient number of times. Since by adding 4 to a number, the property is still true, then the property is true for all numbers greater then 18.