Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
"prove that any integer greater than or equal to 8 can be represented as$\ldots$" could be construed as "Pick any integer greater than or equal to 8 and prove that it can be represented as$\ldots$". But I don't think that's what you mean. Just say "every" instead of "any" and all ambiguity vanishes. –  Michael Hardy Aug 10 at 22:27
1  
Show this minimal criminal can't be $\gt 10$, and then show it is not $8$, $9$, or $10$.. –  André Nicolas Aug 10 at 22:31
2  
@MichaelHardy What is the difference between saying "Prove that every integer $\geq 8$..." and "Prove that any integer $\geq 8$..."? I am not the original poster of the problem, but I am confused by how saying "every" changes the problem –  user46944 Aug 10 at 22:31
    
@user46944 : "Pick any card" does not mean "Pick every card". "Prove that any X is Y" can similarly mean "Pick any X and prove that it is Y". But "Any X is Y" without further context means "Every X is Y". But "Prove that every X is Y" cannot mean "Pick any X and prove that it is Y". ${}\qquad{}$ –  Michael Hardy Aug 10 at 23:04

2 Answers 2

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

share|improve this answer
    
Just note that this argument nicely generlizes if we replace the symbols $3,5,8$ with $a,b,a+b$; in which case: every number at least $a+b$ can be written as a multiple of $a$ and $b$. Also, the remaining cases would then be the integers from $a+b$ upto $a+b+min\{a,b\}-1$ (I think!). –  Moses Aug 11 at 19:16
    
@Moses Not true. For example, if $a=2$ and $b=4$ then you can only get even numbers. If $a$ and $b$ are relatively prime then this will probably work. –  neuguy Aug 12 at 0:23
    
Good call! Maybe just an even-odd pair suffices, rather than relatively prime. I dunno; nonetheless, good thoughts :) –  Moses Aug 12 at 16:11
    
The OP's example is not even-odd. Also, $12$ and $15$ cannot give you $28$, for example; $12$ and $15$ have $3$ as a common factor, so they only generate a subset of the multiples of $3$. –  neuguy Aug 12 at 22:47
    
Neat, so relatively prime may be it :) –  Moses Aug 13 at 21:32

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.

share|improve this answer
    
+1. Unexpected. –  Felix Marin Aug 11 at 23:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.