Results 1 to 2 of 2

Math Help - For which natural numbers n do there exist nonnegative integers x and y such that...

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    26

    For which natural numbers n do there exist nonnegative integers x and y such that...

    For which natural numbers n do there exist nonnegative integers x and y such that... n=4x+5y? Justify your conclusion.

    My conjecture/proposition:

    For n=4,5,8,9,10, and 12 and beyond, there exist nonnegative integers x and y such that n=4x+5y. (0 is not a natural number)

    My proof:

    Let x=1, and y=0, thus 4(1)+5(0)=4 which is a natural number.
    Let x=0, and y =1, thus 4(0)+5(1)=5 which is a natural number.
    Let x=2, and y =0, thus 4(2)+5(0)=8 which is a natural number.
    Let x=1, and y=1, thus 4(1)+5(1)=9 which is a natural number.
    Let x=0, and y=2, thus 4(0)=5(2)=10 which is a natural number.

    My initial step:

    Assume P(12) is true. Let x=3, y=0. Thus 4(3)+5(0)=12 which is a natural number and x and y are nonnegative integers.

    Inductive step:

    Must prove that P(k+1)=4x+5y.

    My question is, can I assume K+1=(K-3)+4 and K-3=4x+5y?

    If I can then, K-3=4x+5y, then adding 4 to each side I can show that
    K+1=4x+4+5y,
    K+1=4(x+1)+5y since (x+1) and 5y are nonnegative integers, so are x and y.

    How does this proof seem? If it isn't up to par, what am I missing?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: For which natural numbers n do there exist nonnegative integers x and y such that

    Quote Originally Posted by Brjakewa View Post
    Assume P(12) is true. Let x=3, y=0. Thus 4(3)+5(0)=12
    You don't assume P(12); you have to prove it. Also, it helps to write explicitly what P(n) is. This helps to avoid confusion later in the proof, not to say that all symbols must be defined prior to their use.

    Quote Originally Posted by Brjakewa View Post
    Inductive step:

    Must prove that P(k+1)=4x+5y.
    Again, it helps to write what exactly the induction hypothesis is, which is the real question here.

    Quote Originally Posted by Brjakewa View Post
    My question is, can I assume k+1=(k-3)+4 and k-3=4x+5y?
    You can assume the first equality as long as k > 3 (I am assuming that in this particular equality all operations are on natural numbers), which is true since k >= 12 by assumption. As for P(k - 3), i.e., the fact that there exist nonnegative integers x and y such that k - 3 = 4x + 5y, you cannot assume this for all k >= 12. Indeed, you have shown P(12 - 3) and P(13 - 3), but not P(14 - 3). If you leave it like this, you have a gap in the proof for P(15), P(19), P(23), etc. To cover this gap, it is sufficient to prove separately P(15), i.e., P(k + 1) when k = 14.

    Suppose we are only asked to prove P(k) for k >= 12. Then one has to prove four base cases: P(12), P(13), P(14), P(15) together with the inductive step: P(k - 3) implies P(k + 1) for all k >= 15 (which is the same thing as P(k - 4) implies P(k) for all k >= 16). This way, the base case P(12) plus the inductive step will cover P(12), P(16), P(20), etc.; the base case P(13) will cover P(13), P(17), P(21), etc.; the base case P(14) will cover P(14), P(18), P(22), etc.; and finally P(15) will cover P(15), P(19), P(23), etc. Together, they cover all integers >= 12. For each number n >= 12, you can think back to the chain of numbers m such that P(m) is involved in the proof of P(n): here it is n - 4, n - 8, etc. For each of those numbers m, P(m) must be proved either in the inductive step or in the base case.

    There is also a way to prove this statement by only going from P(k) to P(k + 1). Note that 4(-1) + 5 = 1, so, if 4x + 5y = k, then 4(x - 1) + 5(y + 1) = k + 1. The problem is when x = 0, i.e., 5y = k. But then y > 3 since k >= 12 and 4(4) + 5(y - 3) = k + 1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: December 1st 2011, 04:24 AM
  2. Show that there exist no positive integers ...
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 23rd 2011, 04:49 PM
  3. Nonnegative integers problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 10th 2010, 06:45 AM
  4. Replies: 2
    Last Post: March 3rd 2009, 01:56 PM
  5. Replies: 5
    Last Post: August 6th 2008, 08:27 AM

Search Tags


/mathhelpforum @mathhelpforum