4
$\begingroup$

Use induction on $n$ to prove that for all integers $n\geq 4$, postage of $n$ cents can be realized using only $2$ cent and $5$ cent stamps.

I thinks it is little bit different. How can I use induction to this kind of problem?

  • 0
    BTW: Induction is way overkill in this problem. If $n=2k$ then, $k$ 2-cent stamps will do it, while if $n=2k+1$, then $k \geq 2$ and one $5$-cent stamp and $(k-2)$ two-cents stamps will do... If you check both solutions below, both of them basically lead by induction to exactly this solution ;)2012-01-17

2 Answers 2

10

It is trivial that $4$ and $5$ are achievable. Now it's all over. From those two, you can get any greater postage you want by adding a suitable number of $2$ cent stamps.

More formally, we want to show that for every $n \ge 2$, both $2n$ and $2n+1$ are achievable. Since every integer is even or odd, that will do it. We prove this by induction on $n$. The result is certainly true for the base case $n=2$.

Now suppose that for a certain $k\ge 2$, both $2k$ and $2k+1$ are achievable. We want to show that $2(k+1)$ and $2(k+1)+1$ are achievable. That is easy: add a $2$ cent stamp.

8

The base case is 4 cents, which can be realized using two 2-cent stamps.

Suppose now that we can realize $n$ cents. We want to prove that we can realize $n + 1$ cents.

Consider two cases: either a 5-cent stamp is used in our hypothetical realization of $n$ cents or not.

If there is, remove it and add three 2-cent stamps. We now have $n - 5 + 3 \cdot 2 = n+1$; a realization of $n+1$ cents.

If there is not, then it must be that only 2-cent stamps are used. Moreover, since $n \geq 4$, at least two 2-cent stamps are used. Remove two of these and add a single 5-cent stamp. We now have $n - 2 \cdot 2 + 5 = n+1$; a realization of $n+1$ cents.