Imagine that your country's postal system only issues 2 cent and 5 cent stamps. Prove that it possible to pay for postage using only these stamps for any amount n cents, where n is at least 4.
My attempt (using Strong induction, I know we can use induction but since they say you can can apply strong induction for generalized/weak induction cases):
Base case: $$n=4: 2 \times2cents$$ $$n=5: 0 \times 5cents$$ $$n=6: 3 \times 2cents$$ $$n=7: 1 \times 2 cents + 1 \times 5 cents$$
You might ask why I have so many base cases, this is my reason why: The question states that we can pay for postage using 2 and 5 cents only. Hence, we have 3 general cases:
1: ONLY 2-cents stamps are used
2: ONLY 5-cents stamps are used
3: 2-cents and 5-cents stamps are used.
(Till now, are my base cases valid?)
Assume that for n=k, P(k) is true and that we need to show P(k+1)
$\textbf{Induction hypothesis:}$ P(k) is true when $4\le i \le k$ and $k \ge 7$
Since $4\le (k-3) \le k$ , P(k-3) or i is true by Induction hypothesis.
Now, k-3 cents can be formed using 2 and 5-cent stamps.
To get k+1 stamps, we can just replace it with $\textbf{four}$ 2-cent stamps?
Thank you! Is my proof valid or no? Any alternatives for this question using strong induction? Also, if I have used strong mathematical induction wrong or any of the steps are incorrect, please explain why.
$\endgroup$4 Answers
$\begingroup$Here's another induction-free proof, using the fact that integers are even or odd:
If $n$ is even, then $n=2k$ and we are done ($k$ two-cent stamps).
If $n$ is odd, so $n=2k+1$, then since $n\ge4$ we have $k\ge\frac32$ whence $k\ge2$ because $k$ is an integer. Therefore $m=k-2\ge0$, and $n=2m+5$, so we can use $m$ two-cent stamps and one five-cent stamp.
$\endgroup$ 2 $\begingroup$You can avoid explicit induction by verifying a finite number of cases like 4,5,6,7,8 and then note that any higher natural number is separated from one of these by a multiple of 5.
Strictly logically that last step requires induction as well but the proof is much easier.
$\endgroup$ 2 $\begingroup$You can do all even amounts, and you can do all odd amounts $\geq5$. It follows that the only positive amounts you cannot do are $1$ and $3$.
$\endgroup$ $\begingroup$Let's assume you know how to pay $n$ cents using only 2- and 5-cents stamps. You want to find a way to pay $n+1$ cents. There are two cases:
- If your sequence for the $n$ contains a 5-cents stamp, take it out and replace it by three 2-cent stamps.
- If your sequence contains only 2-cents stamps, then it must contain at least two of them (remember condition $n\ge 4$?) - in this case take these two stamps out and replace them by one 5-cent stamp.
That'll be a strong induction.
$\endgroup$
