Question

Prove that any amount of postage greater than or equal to 64 cents can be obtained using only 5-cent and 17-cent stamps?

Answer 1

Let P(n) be "a postage of n cents can be formed using 5-cent and 17-cent stamps if n is greater than 63".Basis step: P(64) is true since 64 cents postage can be formed with one 5-cent and one 17-cent stamp.Inductive step: Assume that P(n) is true, that is, postage of n cents can be formed using 5-cent and 17-cent stamps. We will show how to form postage of n + 1 cents. By the inductive hypothesis postage of n cents can be formed using 5-cent and 17-cent stamps. If this included a 17-cent stamp, replace this 17-cent stamp with two 5-cent stamps to obtain n + 1 cents postage. Otherwise, only 5-cent stamps were used and n  65. Hence there are at least three 5-cent stamps forming n cents. Remove three of these 5-cent stamps and replace them with two 17-cent stamps to obtain n + 1 cents postage.Hence P(n + 1) is true.