# Representing Any $n \geq 4$ as a Sum of 2's and 5's

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?

-
Suggestions: (1) Please read this carefully regarding how to ask homework questions. (2) Please also improve your acceptance rate by going back through the questions you've asked that have received answers and selecting the best one by clicking on the checkmark next to the answer. (3) Then, come back and rephrase your question based on what you've learned. Cheers. :) –  cardinal Jan 16 '12 at 23:56
It may be useful when attempting to make $n+1$ cents to realize that if you've made $n$ cents out of $2$ and $5$ cent coins, then removing a $5$ cent coin and adding three $2$ two cent coins gives you $n+1$ cents, or removing two $2$ cent coins and adding a $5$ cent coin gives you $n+1$ cents. You just need to be careful that you have at least two $2$ cent coins or at least one $5$ cent coin already. –  yunone Jan 17 '12 at 0:00
@cardinal first. it is not homework. second. I didnot know about it and I did it. –  Q123 Jan 17 '12 at 2:20
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 ;) –  N. S. Jan 17 '12 at 6:19

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.

-

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.

-