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?
Best Answer
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
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).