Proving Non-Negativity of m and n for x>=8

[antiemptyv]

Homework Statement

Prove that for all integers x >= 8, x can be written in the form 3m + 5n, where m and n are non-negative integers.

Homework Equations

The Attempt at a Solution

Proof by induction on n that every integer n >= 8 can be expressed as n = 5x + 3y, with some integers x and y.

Let n = 8. Then n = 8 = 5(1) + 3(1), so the proposition is true for the base case.
Suppose the proposition is true for some number integer n = k > 8, i.e. k = 5x + 3y, for integers x and y. Consider the case when n = k + 1.

Then we have

k + 1 = 5x + 3y + 1
= 5x + 3y + 1 + 5 - 5
= 5x - 5 + 3y + 6
= 5(x - 1) + 3(y + 2).

Since the proposition is true for the base case and it being true for n = k implies
that it is true for n = k + 1, then n = 5x + 3y for some integers x and y.

I think that's almost it, but what about showing that m and n will never have to be negative?

 

[Dick]

9 is 0*5+3*3. 0 and 3 are non-negative. But your induction step is flawed. It would say 10=(-1)*5+5*3, which is true enough, but -1 is not non-negative. Luckily your induction can only fail for numbers k that are divisible by 3. Can you think of an alternative argument for these cases?

 

[NateTG]

I think that's almost it, but what about showing that m and n will never have to be negative?

You got to:
k+1=5(x-1)+3(y+2)
but, as you point out, you can't be sure that (x-1)\geq 0.

One way might be to split this into two cases - one where x>0 and one where x=0 (you'll have to take advantage of k+1 \geq 9 in this case).

 

[NateTG]

I don't think the text of the problem is correct. If x=9, what are "m" and "n" equal to ?

9=3 \times 3 + 5 \times 0
Zero is a non-negative integer.

 

[dextercioby]

My solution Any natural number greater or equal to 8 is a member of this set

\left\{8, 9, 10, 11, 12, ...\right\}. All elements of this set can be written as

8+3k, 9+3k, 10+3k, \ k\in\left\{0,1,2,3,...\right\}

But

8+3k= 5\cdot 1+3\cdot p \ , \ p\in\left\{1,2,3,...\right\} when

k=0\longrightarrow p=1 , \ k=1\longrightarrow p=2, \ ,...

9+3k= 5\cdot 0+3\cdot p' \ , \ p'\in\left\{3,4,5,...\right\} when

k=0\longrightarrow p'=3 , \ k=1\longrightarrow p'=4, \ ,...

10+3k= 5\cdot 2+3\cdot p'' \ , \ p''\in\left\{0,1,2,...\right\} when

k=0\longrightarrow p''=0 , \ k=1\longrightarrow p''=1, \ ,...

So the problem is solved. Any element x\in\left\{8, 9, 10, 11, 12, ...\right\} can be written as x=5m+3n, with m\in\left\{0,1,2\right\} and n\in\mathbb{N}.

BTM, this is neither calculus, nor beyond

EDIT: I deleted that erroneous post Nate quoted above.

 

[Dick]

Alternatively, the cases that fail your inductive step are k=3*n for n>=3. In this case k+1=3*(n-3)+3*3+1=3*(n-3)+2*5.

 

[uiulic]

My method isthe same as dextercioby. But I organize it in another way, which maybe look simpler.

1 n=8,obvious
So we can start from 9, let k=3n,3n+1,3n+2, n>=3
2 k=3n, obvious
3 k=3n+1=3(n-3)+10,obvious
4 k=3n+2=3(n-1)+5,obvious

From 1,2,3,4, the conclusion is obvious