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