# Math Help - Easy peasy proof help

1. ## Easy peasy proof help

Hai,

This is the part im worst at, proving stuff
I need to prove that every number $\ge16$

can be written as $3k + 5m$

The statement holds true for 16,17,18 and 19

Where do you start?

2. I suppose k and m must be non-negative integers, or else all integers can be written in this way.

First note that $2\times 5 - 3 \times 3 = 1$.

Write $n = k \times 3 + t$ where $t=0,1$ or 2. Note that $k \geq 5$.

Clearly if $t=0$ you are done.

If $t=1$,

$n = 3k+1 = 3(k-3) + 2 \times 5$

If $t=2$,

$n = 3k+2 = 3(k-6) + 5 \times 4$.

Now to make sure $k-6\geq 0$ just check all cases up to k=6 but you already did that.

3. Originally Posted by Bruno J.
I suppose k and m must be non-negative integers, or else all integers can be written in this way.
to make it a little more interesting lets suppose k and m must be positive integers.

We have two suitable ways how to add 1:
a) -3*3 +2*5
b) +2*3 -1*5
we're starting with
16 = 2*3+2*5. So we are forced to use b) to keep coefficients positive:
17 = 4*3+1*5 now we are forced to use a) to keep coefficients positive:
18 = 1*3+3*5 now we are forced to use b) to keep coefficients positive:
19 = 3*3+2*5 now we must use b):
20 = 5*3+1*5 and now we must use a):
21 = 2*3+3*5.

And now we see we're safe: after this five steps we raised coefficients 2,2 to 2,3 and we avoided to sink to 0 (for each coefficient) along the way. So continuing with repeating the seqence babba again and again will get us to every integer >16 without sinking any of the coefficients to 0 along the way.

4. Originally Posted by Taluivren
to make it a little more interesting lets suppose k and m must be positive integers.

We have two suitable ways how to add 1:
a) -3*3 +2*5
b) +2*3 -1*5
we're starting with
16 = 2*3+2*5. So we are forced to use b) to keep coefficients positive:
17 = 4*3+1*5 now we are forced to use a) to keep coefficients positive:
18 = 1*3+3*5 now we are forced to use b) to keep coefficients positive:
19 = 3*3+2*5 now we must use b):
20 = 5*3+1*5 and now we must use a):
21 = 2*3+3*5.

And now we see we're safe: after this five steps we raised coefficients 2,2 to 2,3 and we avoided to sink to 0 (for each coefficient) along the way. So continuing with repeating the seqence babba again and again will get us to every integer >16 without sinking any of the coefficients to 0 along the way.
But can this really be considered a proof?
Don't you have to show that it holds for every number $\ge16$ by induction?

5. Originally Posted by Jones
But can this really be considered a proof?
Don't you have to show that it holds for every number $\ge16$ by induction?
That’s where you comes in! (: ..to put the idea into a proof of a rigorousity level acceptable for you/your teacher.

In fact it is not difficult to do: since both a and b add 1 to any number, any sequence of letters a,b of length k applied to 16 will produce number 16+k.

We've chosen a special sequence w_k for each 16+k: w_k = babbababbababbababb... of length k such that the resulting expression of the number 16+k has positive coefficients at 3 and at 5. This should be clear from my five-step argument above. If not, I'll write it for you: to obtain 16+k = 16+5q+r where r<5 we apply the sequence (babba)^q followed by the rest of length r. By induction you prove that (babba)^q turns coefficients 2,2 (of the expression of 16) into coefficients 2,2+q (of the expression of 16+5q). My five-step argument then proves that our rest of length r will not decrease the coefficients of the expression of 16+5q+r to 0 (the argument is given for q=0 where we're starting with the coefficients 2,2 so the argument obviously holds for any q (where we're starting with 2,2+q)).

Hope this helps.