Is this proof using well ordering principle correct? Are all parts necessary?

Question

Example. Suppose the Royal Canadian Mint was to introduce a 3 cent coin like the British three pence to replace the 1 cent penny. Prove that 7 cents is now the largest quantity unable to be made with coins.

Solution. Since coins of value 10 cents and above can all be made with multiple nickels, we use only the 3 cent and 5 cent coins in our proof. Then, we are trying to prove \begin{equation*} \forall x \in \mathbb{N}, \exists y, z \in \mathbb{N}_0,\;\;(x > 7) \to (x=3y+5z). \end{equation*} Suppose, for the sake of contradiction, that there are amounts greater than 7 cents which cannot be paid with 3 cent and 5 cent coins. Let $S$ be the set containing all such amounts. Since $S \subseteq \mathbb{N}$ and we have assumed $S \neq \emptyset$, by the Well-Ordering Principle, $S$ has a least element. Call it $n$. Now look at $n-3$. This cannot be paid with 3 cents and 5 cents either. Then, since $\min(S) = n$, we have $n-3 \leqslant 7 < n$. There are now three cases:

1. If $n-3=7$ then $n = 10 = 2 \times 5$
2. If $n-3=6$ then $n = 9 = 3 \times 3$
3. If $n-3=5$ then $n = 8 = 1 \times 3 + 1 \times 5$

Similarly, the amount $n-5$ cannot be paid with 3 cent and 5 cent coins either. Then we have $n-5 \leqslant 7 < n$ and the following five cases:

1. If $n-5 = 7$ then $n = 12 = 4 \times 3$
2. If $n-5=6$ then $n=11 = 2 \times 3 + 1 \times 5$
3. If $n-5=5$ then $n=10 = 2 \times 5$
4. If $n-5=4$ then $n=9 = 3 \times 3$
5. If $n-5=3$ then $n=8 = 1 \times 3 + 1 \times 5$

In all three cases we have a contradiction because we assumed $n$ cannot be made using 3 cent and 5 cent coins. So $\forall x \in \mathbb{N}, \exists y, z \in \mathbb{N}_0\;(x > 7) \to (x=3y+5z)$ and $S = \emptyset$. $\blacksquare$

---

I would like to know if, first of all, this proof is correct, and secondly, is it necessary to look at both $n-3$ and $n-5$ or just one or the other? This was used as an example in class but the professor used only $n-3$. Mustn't we consider $n \in \{ 11, 12 \}$ as well?

Answer 1

(1) It looks correct to me. (2) It is not necessary to look at $n-5$. After you derive a contradiction, your proof-by-contradiction is done! There is no need to derive two contradictions; it doesn't double the amount of truth in the conclusion.

In particular, no, you don't have to consider the possibility that $n=11$, because you have already proved that the assumptions imply $n-3\leq 7$.