Stamp Induction problem

Question

Suppose you have an unlimited supply of 5-cent postage stamps and 7-cent postage stamps. Show that you can make any amount of postage which is 24 cents or larger using only these stamps.

Answer 1

First of all, you can realize : $24$ cents postage : $2\times5+2\times7=24$.

Now let $N\ge24$ be a integer for which there exists a solution : $N=n_5\times5+n_7\times7$. Let's try to realize a postage of $N+1$ cents.

There is basically two ways to add $1$ cent : $3\times5-2\times7=1=3\times7-4\times5$. Problem is : you have to subtract some $5$ cents or $7$ cents stamps.

Suppose now that $n_5<4$, so that we can't add three $7$ cents stamps and remove four $5$ cents stamps.

As $N\ge24$ and $n_5\le3$, $N-n_5\times5\ge 24-3\times5=9$, so there is at least two $7$ cents stamps, and we can use the other solution : remove two $7$ cents stamps and add three $5$ cents stamps.

In all cases, we can find a solution for the $N+1$ postage problem.