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

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.