Mathematical induction: using 3 cent and 7 cent stamps

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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