Results 1 to 3 of 3

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?

    I used a proof by induction.

    My proposition: For the natural numbers n>= 12 there exist nonnegative integers x and y such that n=4x+5y.

    Initial step: Prove P(12) is true. Let x=3 and y=0 ... 12=4(3)+5(0), 12=12. So that checks out.

    Now my trouble is on the inductive step.

    Here is how my proof goes so far....

    I had said that we will now prove that for n>=12 there exist nonnegative integers x and y such that n=4x+5y. We must first let P(n) be there exist x and y in the integers with x and y greater than or equal to zero, and x+y >= 4 such that n=4x+5y.

    My first mistake: I used x = 3 and y = 0, which doesn't go with x+y>= 4, what can I do to fix that?

    My proof continued: For inductive step, we prove that for all k in N with k>=12, if P(k) is true then P(K+1) is true. So let k be natural and assume P(k) or P(12) is true. I said we must show that K+1=4x+5y.

    My second mistake: My instructor said "x and y are what" I'm assuming I can fix that by saying x and y are nonnegative integers?

    My proof continued: Notice that 4(-1)+5=1. Since K=4x+5y...

    My third mistake: My instructor said "same x and y??" What can I do to fix this or do differently.

    My proof continued: K+1=4(x-1) + 5(y+1) by algebra. Since x and y are nonnegative integers, so are (x-1) and (y+1).

    My final mistake, apparently: My instructor said "what if x = 0" So how can I fix this?

    I will now finish the proof, to show you my work:

    Thus, we have shown that K+1=4x+5y and therefore P(K+1) is true and inductive step has been established. Thus for the natural numbers n>=12, there exist nonnegative integers x and y with x+y>=4 such that n=4x+5y. Q.E.D.

    We are allowed to submit corrections, so what errors are in my proof, can anyone help? it seems by my instructor's comments, and my work... I had almost got it?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2011
    Posts
    127

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

    I'll describe your mistakes first, but the problem here isn't the mistakes you cite. It's that you don't understand what you're doing with the induction. I'll answer the real problem after commenting on your "mistakes" below.

    First mistake: why even say x+y >= 4? Why is that necessary or helpful?
    Second mistake: No. The problem is you're claiming a certain property exists wrt "4x+5y" without describing how to arrive at the values of x and y.
    Third mistake: This is the same as second mistake.
    Final mistake: Your formula isn't correct if it allows negative values.

    But those aren't really the mistake here. Here's the problem--you don't prove things by induction by manipulating the same variables over and over. You do it by showing that based on previous cases where a property holds, successive cases must also hold.

    I'll give you a hint: you should really be using strong induction here. Try this format:

    1) Prove that for n = 12, 13, 14, and 15, P(n) is true.
    2) Assume P(n), P(n+1), P(n+2), and P(n+3) hold. Let a = the value of x such that P(n) holds and b = the value of y such that P(n) holds. Can you show that this must imply that P(n+4) holds?
    3) If so, by FIP, you have proven P(n) holds for all natural numbers 12 and larger.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

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

    This problem has also been discussed in this thread.

    Edit: I missed that the OP apparently knows this...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: November 20th 2011, 09:13 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