[Math] Prove that for $n\ge 8$ there are nonnegative integers x and y s.t $3x+5y=n$

inductionproof-writing

Prove that for every integer $n\ge 8$ there are nonnegative integers $x$ and $y$ such that $3x+5y=n$

Attempt: First of all I want to make it clear whether zero is a nonnegative integer. It should be since it is necessary for the statement to work. Second, I am not sure what method to use. Will proof by cases work? I will have four cases: x is even y is even, x is even y is odd, x is odd y is even, x is odd y is odd. I am not sure how to show that it will cover all integers greater than eight. Thank you for your help.

Best Answer

One more solution.

Use the induction.

  1. Check that the statement is true for $n=8,9,\ldots,16.$

  2. Suppose we already prove it for all numbers less than $n$, $n>16.$ Since $n>16$ then we can write $n=n_1+n_2$ where $n_1,n_2 >8.$ By induction assumption we may write $3x_1+5y_1=n_1$, $3x_2+5y_2=n_2$ for some $x_1,x_2,y_1,y_2 \geq 0.$ Therefore $n=n_1+n_2=3(x_1+x_2)+5(y_1+y_2)$ and $x_1+x_2 \geq 0,$ and $y_1+y_2 \geq 0$ as required.

Related Question