Question

oo Verizon LTE 5:18 PM 88%-. 3 of 3 5) Prove by induction If one had an infinile sapply of 4e and 7e stamps, then every postape o 18 ca, be writen 18e or higher could be made· (This is the same as saying every integer as a lincar combination of 4 and 7(-4x+y) 3-1 Bon)-ore

Answer 1

Proof by induction:
Let n be an arbitrary integer greater than 17.

Let us assume that for any integer k such that 17 < k < n, we can make k cents in postage.

Now, there are five cases to consider: n = 18, n = 19, n = 20, n = 21, and n > 22.

The change for these cases can be made as follows:

18 = 7 + 7 + 4
19 = 7 + 4 + 4 + 4
20 = 4 + 4 + 4 + 4 + 4
21 = 7 + 7 + 7

Now, suppose n > 21
Then, 17 < n-4 < 21

Thus, using the induction hypothesis, we should be able to make n-4 cents in postage. This is possible if we simply add another 4-cent stamp, to give us n cents in postage.
Hence, we can make n cents in every case.