4
$\begingroup$

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?

$\endgroup$

4 Answers 4

Reset to default
5
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ It doesn't need to. Since 12 is true, it follows that 15 is true and 18 is true and 23 is true etc. since 13 is true it follows that 16 is true and 19 is true etc. since 14 is true it follows that 17 is true and 20 is true etc. note that these cases cover all natural numbers greater than 11 $\endgroup$
    – ASKASK
    Dec 6, 2015 at 5:10
  • 1
    $\begingroup$ I added induction by $n+1$ case. $\endgroup$
    – Kay K.
    Dec 6, 2015 at 5:14
  • 1
    $\begingroup$ Yes, ASKASK is still right. $\endgroup$
    – Kay K.
    Dec 6, 2015 at 5:19
  • 1
    $\begingroup$ I think it was this answer that suggested thinking of induction not as building up from one case of a problem to the next, but breaking down a given case into simpler cases of the same problem. I think that might be useful here for the $n+3$ induction. Given this problem for any $n>14$, you can reduce it to the same problem with $n-3$, and then $n-6$, etc., and you will eventually run into one of the proven base cases 12, 13, or 14. That's equivalent to the induction argument, just in the other direction. $\endgroup$
    – David Z
    Dec 6, 2015 at 13:40
  • 1
    $\begingroup$ I revised my $n+1$ case. To stick with the $n+1$ induction, you should divide it into 3 cases and should show that you'll be still within those 3 cases. Thanks Adam, it was an interesting question and very good example to learn about induction. as David says. $\endgroup$
    – Kay K.
    Dec 6, 2015 at 15:44
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Great point. But it does cover the n=16 case right? I'm trying to understand how it is different from Kay's answer if it is only proving one of the specific cases after the three base cases? $\endgroup$
    – Adam Thompson
    Dec 6, 2015 at 5:08
  • 1
    $\begingroup$ Well if you consider that $15=3*5+7*0$, then yes it does cover the case of $n=16$ since 5>1. $\endgroup$
    – ASKASK
    Dec 6, 2015 at 5:12
  • 1
    $\begingroup$ I commented on Kay's answer explaining why his works $\endgroup$
    – ASKASK
    Dec 6, 2015 at 5:12
  • $\begingroup$ It just clicked for me, thank you ASKASK. $\endgroup$
    – Adam Thompson
    Dec 6, 2015 at 5:25
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I understand, thank you. Would it be better to just use strong induction instead of multiple hypotheses in this case? $\endgroup$
    – Adam Thompson
    Dec 6, 2015 at 5:09
  • 1
    $\begingroup$ @AdamThompson There was only one hypothesis here. I assumed that for some one $k$ all of $k,k+1,k+2$ are of the form $3a+7b$ for some $a,b\ge 0$. $\endgroup$
    – user236182
    Dec 6, 2015 at 5:10
1
$\begingroup$

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)$.
$\endgroup$

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.