Question

Suppose that we have access to an unlimited number of 5 and 11 cent stamps. Prove, using simple induction, that we can use these stamps to make any amount of postage that is at least 40 cents.

Answer 1

P(n) is the statement that we can make a postage of n cents using 5-cent and 11-cent stamps

P(40) is true as so using 8 stamps of 5-cents each we can make 40-cent stampage

Induction assumption: Any postage of stampage can be made, i.e. P(n) is true for this range of numbers

This means for some (non-negative integers)

We want to show that P(k+1) is true

So

Noting that we have

And so we can also create a stamping of amount k+1

Unless in which case we write

So that

Which is another valid way to create a stamping of amount k+1 unless

The only way in which none of the above two ways work is the case when for and

But for this range of values we have

And we have chose k atleast 40

So this means we can always extend the stamping for k to a stamping for k+1

Thus P(k+1) is also true and by the principle of mathematical induction, we can always use these stamps to make any amount of postage that is at least 40 cents.

Hope this was helpful. Please do leave a positive rating if you liked this answer. Thanks and have a good day!