# Mathematical induction: using 3 cent and 7 cent stamps

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.

• 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! – iadvd Aug 31 '15 at 4:49
• yea thats where i am confused. – user265685 Aug 31 '15 at 4:54
• 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. – zhoraster Aug 31 '15 at 4:58
• This is sometimes called the chicken macnugget problem. You might be interested in Googling it. – steven gregory Aug 31 '15 at 4:59
• Doh, how silly of me. Thanks Alan – User0112358 Aug 31 '15 at 5:00

$n=12$ is obvious.

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

$n+1=3p+7q+1$

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$.

Now:

\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.