prove that any integer greater than or equal to 8 can be represented as the sum of nonnegative integer multiples of 3 and 5 This problem asks to use Well Ordering Principle to prove any integer greater than or equal to  8 can be represented as the sum of nonnegative integer multiples of 3 and 5.
Here's where I'm at:
For the sake of contradiction assume that there is a nonempty set C such that,
C :: = {n >= 8 (only positive integers) | n CAN'T be represented as a linear combination of 3 and 5}
By WOP C contains a least element m. m >= 9 because n=8 can be represented as a linear combination of 3 and 5.
I'm stuck here. I have to find a contradiction that shows C is an empty set but not sure how to approach this. Any hints? Thanks.
 A: If $m$ can't be represented as a sum of non-negative integer multiples of $3$ and $5$, then neither can $m-3$. Therefore $m$ cannot be greater than $10$, as if $m \geq 11$ then $m-3 \geq 8$, and thus $m-3$ would be in $C$, contradiction since $m$ is the least element of $C$. Now we just check the few remaining cases, which are $m=8,9,10$.
A: As soon as you can represent three consecutive integers as $3x+5y$, you can represent them all by just adding a $3$ to the previous representations. Since $8=3+5,9=3+3+3$ and $10=5+5$, all the integers $\geq 8$ can be represented.
Another way to prove this is to consider that:
$$ r(n)=|\{(a,b)\in\mathbb{N}^2:3a+5b=n\}|$$
is the coefficient of $x^n$ in the product:
$$ (1+x^3+x^6+x^9+\ldots)(1+x^5+x^{10}+\ldots),$$
hence:
$$\begin{eqnarray*}r(n)&=&[z^{n}]\frac{1}{(1-z^3)(1-z^5)}\\&=&[z^n]\left(\frac{1}{15(1-z)^2}-\frac{1}{5(1-z)}+h(z)\right)\end{eqnarray*}\tag{1}$$
where:
$$h(z) = \sum_{\xi\in Z}\frac{\operatorname{Res}\left(\frac{1}{(1-z^3)(1-z^5)},z=\xi\right)}{\xi-z}$$
and $Z=\left\{\exp\frac{2\pi i}{3},\exp\frac{4\pi i}{3},\exp\frac{2\pi i}{5},\exp\frac{4\pi i}{5},\exp\frac{6\pi i}{5},\exp\frac{8\pi i}{5}\right\}$.
Since the sum of the residues is $0$, the contribute to the coefficients given by the residues in $Z$ can never exceed $\frac{|Z|}{5}=\frac{6}{5}$. Hence we just need to prove that for any $n\geq N$, 
$$[z^n]\left(\frac{1}{15(1-z)^2}-\frac{1}{5(1-z)}\right)>\frac{6}{5}$$
holds, in order to prove that any $n\geq N$ can be represented as $3x+5y$. However:
$$[z^n]\left(\frac{1}{15(1-z)^2}-\frac{1}{5(1-z)}\right)=\frac{n+1}{15}-\frac{1}{5},$$
hence we can take $N=21$ and fill the remaining cases ($n\in[8,20]$) by hand.
A: My proof is similar to Gyu Eun Lee's:
Let S(n) be the proposition that n is an integer greater than or equal to 8, and P(n) be the proposition that n can be written as integer multiples of 3 and 5. 
Let C be the set of counterexamples, C::={n | S(n) and NOT(P(n))}. By W.O.P, there exists a smallest element in C, call it m. We verify P(8), P(9), P(10), so m must be greater than 10 to be a counterexample. Then the number (m-3) is greater than or equal to 8 and less than m, so P(m-3) holds; it follows P(m) must hold as well (m is (m-3) plus a multiple of 3), contradicting NOT(P(m)). Thus C is in fact empty.
A: Can we do it as follows?


*

*Let P(n) = for all natural number n >= 8, exists k_1, k_2 such that n = 3k_1 + 5k_2

*Let C = {n >=8|NOT(P(n))}

*Assume C is not empty. By well ordering principle, there exists a smallest element d in C.

*d does not equal to 3k_1 + 5_k2 for any integer k_1, k_2

*check: P(8),P(9),P(10) holds, so d > 10.

*d > d - 1 >= 8

*so d - 1 = 3k_1 + 5k_2 for some k_1, k_2

*then d = d - 1 + 1 = 3k_1 + 5k_2 + (6 - 5) = 3(k_1 + 2) + 5(k_2 - 1). A contradiction

A: Let P(t) is the property that for every $t \geq 8$ there are exist $k_1,k_2$ such that $t = 3k_1 + 5k_2$.
Let C be the set :
C ::= {t $\in N$ || NOT(P(t))}.
For the purpose of obtaining contradiction we assume that C is not empty.
There is the smallest element, $t_0 \in C$
$t_0 \geq 11$ since P(8),P(9),P(10) holds.
We have that :
$t_0 - 1 = 3k_1 + 5k_2$
$t_0 = 3(k_1 + 2) + 5(k_2 - 1)$
which contradicting the fact that $t_0$ can not be written as a linear combination of 3 and 5
$ -> $ C is empty
