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?

  • 2
    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.2012-01-17
  • 0
    @cardinal first. it is not homework. second. I didnot know about it and I did it.2012-01-17
  • 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