# 7 Cents and 11 cents Stamps Mathematical Induction

Assume you can only use 7-cent and 11-cent stamps.
a) Determine which amounts of postage can be formed by the given stamps.
b) Prove your answer using the principle of mathematical induction.
c) Prove your answer using strong induction.

By doing a) i found out that all the numbers after 59 can be created using a combination of 7 cants and 11 cents stamps
In part b , i assumed that the $$n=7k+11l$$ where k is the amount of 7 cents stamps and l is the amount of 11 cents stamps. But how do i proceed? And in the strong induction step what is our inductive hypothesis?

• Think about the recurrence relation formed by reducing the number by one of the stamp's face value! – BBischof Mar 22 '16 at 5:53
• If add to the number 2*11 and subtract 3*7 we can get the next number. Thank you @BBishof – Jack Mar 22 '16 at 5:57
• Sylvester showed in 1884 that the Frobenius number was $f(a,b) = (a-1)(b-1)-1$ mathworld.wolfram.com/FrobeniusNumber.html – bobbym Mar 22 '16 at 5:59
• Okay so we get this from recursion $$n+1=7(k-3)+11(l+2)$$ from the recursion . So our hypothesis is correct? – Jack Mar 22 '16 at 12:17
• This answer says a lot. Not everything, but quite a bit. – Jyrki Lahtonen Mar 23 '16 at 10:06

## 5 Answers

Elementary pedestrian proof (although, I like generating series). - The lowest postage is 7 - Then 11 - After you must be able to decrease $l$ to feed $k$ (and conversely) a rapid examination of the cases leads you to the following amounts [14,18,21,22,25,28,29,32,33,35,36,39,40,42 ... 60,61] - the last one $61$ allows the recurrence using

1. ) $1=2\times 11-3\times 7$
2. ) $1=8\times 7- 5\times 11$

then for your recurrence use alternatively the first and the second expression. From the number $61=3\times 11+4\times 7$ the recurrence works because, if $n=a\times 7+b\times 11\geq 61$, you cannot have $a<8,b<2$ both ($60=7\times 7+1\times 11$) and then you can use (1) or (2).

Not a complete answer, but might help:

• $A_{60} = \{7,7,7,7,7,7,7,11\}$
• $A_{61} = \{7,7,7,7,11,11,11\}$
• $A_{62} = \{7,11,11,11,11,11\}$
• $A_{63} = \{7,7,7,7,7,7,7,7,7\}$
• $A_{64} = \{7,7,7,7,7,7,11,11\}$
• $A_{65} = \{7,7,7,11,11,11,11\}$
• $A_{66} = \{11,11,11,11,11,11\}$
• $A_{n} = \{7\} \cup A_{n-7}$ inductive step
• Thank you for the strong induction approach – Jack Mar 22 '16 at 13:51
• @Jack: You're welcome :) – barak manos Mar 22 '16 at 13:55

To answer a) you can use generating functions:

$\left(1+x^7+x^{14}+x^{21}+x^{28}+x^{35}+x^{42}+x^{49}+x^{56}\right) \left(1+x^{11}+x^{22}+x^{33}+x^{44}+x^{55}\right)$

$= 1+x^7+x^{11}+x^{14}+x^{18}+x^{21}+x^{22}+x^{25}+x^{28}+x^{29}+x^{32}+\ x^{33}+x^{35}+x^{36}+x^{39}+x^{40}+x^{42}+x^{43}+x^{44}+x^{46}+x^{47}+\ x^{49}+x^{50}+x^{51}+x^{53}+x^{54}+x^{55}+x^{56}+x^{57}+x^{58}$

By looking at the powers we can see those numbers that can be represented. For instance, we see x^25 so we know that 25 is representable. We already know by the Frobenius numbers that 59 is the largest number that cannot be represented ( see my comment above ).

Consider $n=7k+11 t$, where $k\geq 3$ or $t\geq 5$. Otherwise, where $k<3$ and $t<5$, we have $n<58$ which is contradiction. To proceed, if $k\geq 3$, then we have $n+1 =7 (k-3)+11(t+2)$. If $t\geq 5$, then we have $n+1 =7(k+8)+11(t-5)$.

• One quibble. If $k < 3$ and $t < 5$, then $n \color{red}{\leq} 7 \cdot 2 + 11 \cdot 4 = 58$. – N. F. Taussig Mar 22 '16 at 10:30

2x11 - 3x7 = 1 and 8x7 -5x11=1

So if you can get n, you can get n+1 by either adding 2 11s and removing 3 7s. This assumes you have at least 3 7s. If you don't you can add 8 7s and remove 5 11s (and then you'll have more than 3) which assumes you have at least 5 11s. If you never get less than 3 11s you can switch back and forth with these techniques.

For n=60 we can do 7 7s and 1 11. Then we add 2 11s and subtract 3 7s to get 61. Do it again to get 62. We will have 5 11s and 1 seven. We then have to switch method but then then at at least 63 if we ever get down to 3 11s we will have at least 4 7s so we can add two 11s and subtract 3 to get the next.