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

• Nov 29th 2011, 09:26 PM
Brjakewa
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?
• Nov 29th 2011, 10:47 PM
Annatala
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.
• Dec 1st 2011, 05:24 AM
emakarov
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...