n-cents stamp (Strong induction)

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.