Use mathematical induction (and proof by division into cases) to show that any postage of at least 12 cents can be obtained using 3 cent and 7 cent stamps.

I thought this was the simple kind of induction but came to realize it wasn't. I think the term I found on the internet was strong induction. I am specially confused about the cases part.

  • 2
    $\begingroup$ Welcome to Mathematics Stack Exchange! I would suggest you to explain a little bit how you tried to solve it, so other people could help you better. Good luck! $\endgroup$ – iadvd Aug 31 '15 at 4:49
  • $\begingroup$ yea thats where i am confused. $\endgroup$ – user265685 Aug 31 '15 at 4:54
  • 3
    $\begingroup$ Here what you can do: try to find three consecutive numbers payable with those stamps (this will be your base case) and then proceed by induction. $\endgroup$ – zhoraster Aug 31 '15 at 4:58
  • $\begingroup$ This is sometimes called the chicken macnugget problem. You might be interested in Googling it. $\endgroup$ – steven gregory Aug 31 '15 at 4:59
  • $\begingroup$ Doh, how silly of me. Thanks Alan $\endgroup$ – User0112358 Aug 31 '15 at 5:00

$n=12$ is obvious.

For $n+1$, we have by hypothesis that


If $q\geq 2$, $ \quad n+1=3p+7(q-2)+15=3(p+5)+7(q-2)$

If $q=1$, $ \quad n+1=3p+7+1=3(p-2)+6+8=3(p-2)+14=3(p-2)+7(2) \quad$ (Note that $p \geq 2$ necessarily)

If $q=0$, $\quad n+1=3p+1=3(p-2)+6+1=3(p-2)+7 \quad $ (Again, $p \geq 2$ necessarily)


If you can show that $12, 13, 14$ are possible, you are off the hook as from those you can construct $12 + 3 k$, $13 + 3 k$ and $14 + 3 k$, and thus all values above $12$.


$\begin{align} 12 &= 4 \cdot 3 + 0 \cdot 7 \\ 13 &= 2 \cdot 3 + 1 \cdot 7 \\ 14 &= 0 \cdot 3 + 2 \cdot 7 \end{align}$

By checking all possibilities (there aren't that many) you see that $11$ is impossible.

To make the above into a "proper" induction proof, you have to consider the three base cases given, and then show that any $n \ge 12$ you can write as one of the base cases plus a certain number of $3$.


We will show by induction that n cents of postage can be made with 3-cent and 7-cent stamps for any $n\ge12$:

1) When $n=12$, we have $12=3(4)+7(0)$.

2) Suppose $n$ is an integer with $n\ge12$ and $n=3a+7b$ for some integers $a,b\ge0$.

$\hspace{.2 in}$ i) If $a\ge2,\;$ then $3(a-2)+7(b+1)=n+1$.

$\hspace {.18 in}$ii) If $a\le1,\;$ then $3a+7b=n\ge12\implies 7b\ge9\implies b\ge2,\;$ so $3(a+5)+7(b-2)=n+1$.

Therefore $n+1$ cents postage can be made in either case with 3-cent and 7-cent stamps, and this completes the induction step.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.