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.

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! 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 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. Mar 23 '16 at 10:06

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