Results 1 to 5 of 5

Math Help - Easy peasy proof help

  1. #1
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2009
    Posts
    125
    Quote Originally Posted by Bruno J. View Post
    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.
    Last edited by Taluivren; October 3rd 2009 at 02:57 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170
    Quote Originally Posted by Taluivren View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2009
    Posts
    125
    Quote Originally Posted by Jones View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Very easy proof
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: May 11th 2011, 11:35 AM
  2. Need help on an easy proof
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: February 23rd 2010, 09:30 PM
  3. Easy Proof Help
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 31st 2007, 01:25 PM
  4. easy peasy
    Posted in the Statistics Forum
    Replies: 3
    Last Post: October 28th 2007, 10:31 AM
  5. Probably an easy gcd proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 5th 2007, 06:51 PM

Search Tags


/mathhelpforum @mathhelpforum