Convincing Myself of Stamp Induction Induction Proof?

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.

So for this I understand that it can be solved using induction without a strong hypothesis.

Base cases:

$$ n = 12 : 3*4 + 7*0$$ $$ n = 13 : 3*2 + 7*1$$ $$ n = 14 : 3*0 + 7*2$$

Induction hypothesis: Assume for some $k>14$ that $k = 3a + 7b$ for $a, b \in Z$.

Induction step: We will show that $k + 1$ can be made up of 3 and 7 cent stamps.

$$k+1 = 3a + 7b + 1$$ $$k+1 = 3a + 7b + 7 -6$$ $$k+1 = 3a - 6 + 7b + 7$$ $$k+1 = 3(a-2) + 7(b+1)$$

So when $a > 2$ we can make $k + 1$ stamps.

Is it at this point that I need to also clarify when $a = 1$ and $a = 0$ that other cases of $k$ will hold as well? Have I already proven my original statement? Or is this covered because I have shown the pattern in the base cases?

Answer 1

Simplest version: [Induction by $n+3$]

It holds for $n=12,13,14$ as you already showed. If it holds for $n$, then $$n=3a+7b$$ $$n+3=3(a+1)+7b$$

Therefore it also holds for $n+3$. So, it holds for all $n\geq12$.

$$ \\ $$

---

$$ \\ $$

Different version: [Induction by $n+1$]

Assume it holds for $n$, and $a\geq2,b\geq1\text{ or }a\geq0,b\geq2\text{ or }a\geq4,b\geq0$ holds, then $$n=3a+7b\quad (a\geq2,b\geq1\text{ or }a\geq0,b\geq2\text{ or }a\geq4,b\geq0)$$ i) If $a\geq2,b\geq1$, $$n+1=3(a-2)+7(b+1)\quad (a-2\geq0,b+1\geq2)$$ ii) If $a\geq0,b\geq2$, $$n+1=3(a+5)+7(b-2)\quad (a+5\geq4,b-2\geq0)$$ iii) If $a\geq4,b\geq0$, $$n+1=3(a-2)+7(b+1)\quad (a-2\geq2,b+1\geq1)$$

Therefore it also holds for $n+1$ and still $a\geq2,b\geq1\text{ or }a\geq0,b\geq2\text{ or }a\geq4,b\geq0$ holds.

So, it holds for all $n\geq12$.

Answer 2

Yes you do need to cover the cases of when $a=1$ or $0$.

This does not even cover the case of $n=15$

If you trace the logic, it says:

$$14=3*0+7*2$$

Thus,

$$15 = 3*(-2)+7*3$$

But this is invalid because you can't have $-2$ stamps.

Answer 3

Base case: $12=3\cdot 4+7\cdot 0$, $13=3\cdot 2+7\cdot 1$, $14=3\cdot 0+7\cdot 2$.

Inductive hypothesis: Assume that for some (not for all, like you said) $k\ge 12$ we have $k=3m_1+7n_1,k+1=3m_2+7n_2,k+2=3m_3+7n_3$ for some $m_i,n_i\ge 0$.

Inductive step: $k+3=3(m_1+1)+7n_1$ and $k+4=3(m_2+1)+7n_2$ and $k+5=3(m_3+1)+7n_3$.

It also follows from the Chicken McNugget Theorem:

If $a,b\ge 1, \gcd(a,b)=1$, then the greatest integer not of the form $am+bn$ for some $m,n\ge 0$ is $ab-a-b$.

Answer 4

The base of induction is good: you can start from $n=14$.

Now beware: the induction hypothesis is that for $k\ge14$ (not $k>14$), $k=3a+7b$ for non negative integers $a$ and $b$.

At this point you can divide into cases for $k+1=3a+7b+1$.

1. If $a=0$ or $a=1$, then $b\ge2$ (because $3+7=10<k$) and $$3a+7b+1=3a+7(b-2)+14+1=3(a+5)+7(b-2);$$
2. If $a\ge2$, then $3a+7b+1=3(a-2)+7(b+1)$.