Can anyone PROVE the x+1 problem?

[nate9228]

Can anyone PROVE the x+1 problem??

Homework Statement

The problem is this. x_1 is defined to be x_1=m (where m<0). Assuming x_n defined, define x_n+1 to be (x_n)/2 if x_n is even or (x_n)+1 if odd. Prove that this sequence eventually takes the value of 1 no matter what m you choose.

Homework Equations

The Attempt at a Solution

None of my attempts have come close. I know I need to formulate a theorem involving the sequence and then prove my assertion. Help someone pleaseeee. Been working on this for hours.

 

[nate9228]

Correction: m>0 (A natural number)

 

[nate9228]

Cant anyone help? I also believe it is proved by induction.

 

[Dick]

Homework Statement

The problem is this. x_1 is defined to be x_1=m (where m<0). Assuming x_n defined, define x_n+1 to be (x_n)/2 if x_n is even or (x_n)+1 if odd. Prove that this sequence eventually takes the value of 1 no matter what m you choose.

Homework Equations

The Attempt at a Solution

None of my attempts have come close. I know I need to formulate a theorem involving the sequence and then prove my assertion. Help someone pleaseeee. Been working on this for hours.

Induction is a fine idea. Try it. Take P(N) to be the statement that series reaches 1 for all values of m such that 0<m<=N. Can you find a some values of N that make that true? Now can you show if P(N) is true then P(N+1) is true?

 

[Robert1986]

What, exactly, have you done so far? What is your induction base case? What is the IH? What if m is even? What if m is odd?

 

[nate9228]

Induction is what I have been attempting. The part I get stuck at is proving P(N+1) and showing that it in fact holds. Intuitively I know this is true, I just am having trouble showing it. Mostly I am unsure of where to plug in the N+1 and do the following math to show that it hold.

 

[nate9228]

For the base case I started with the integer 1, which is odd, so I added 1 which gives 2. This is even so it is divided by 2 which gives you 1. This sequence would go on continuously.

 

[Dick]

Induction is what I have been attempting. The part I get stuck at is proving P(N+1) and showing that it in fact holds. Intuitively I know this is true, I just am having trouble showing it. Mostly I am unsure of where to plug in the N+1 and do the following math to show that it hold.

Did you check that say P(1), P(2) and P(3) are true? Knowing that what do you have to do to check P(4) is true? Now knowing P(4) is true how would you show P(5) is true? Consider those and try showing P(N)->P(N+1). You might want to break into cases depending on whether N+1 is odd or even.

 

[Redbelly98]

nate9228, did you try using complete induction, a.k.a. "strong induction"?

http://en.wikipedia.org/wiki/Mathematical_induction#Complete_induction

 

[Dick]

For the base case I started with the integer 1, which is odd, so I added 1 which gives 2. This is even so it is divided by 2 which gives you 1. This sequence would go on continuously.

For the base case m=1 you don't even have to go to 2. You are already at 1. That establishes P(1). To do P(2) you need to do m=1 and m=2. But you've already done m=1, so you just need to check m=2. Does it work?

 

[nate9228]

I have shown that P(1), P(2), and P(3) all hold. To show if P(5) holds it would be the same process, i.e. I would first determine if the given integer is odd/even. Then based on this I would plug that into the given "formula" and continue the pattern. And I did that in a way. I stated that x_n= N was even. Therefore x_n= N+1 is odd and goes into the 2nd formula which gives the subsequent number to be (N+1)+1= N+2 which is again even. Then I plugged this into the 1st formula which gives (N+2)/2 which may or may not be even depending upon N (think N=4 vs N=6). If I assume (N+2)/2 is odd again I would go back to the 2nd formula which would now make it ((N+2)/2)+1= (N+4)/2= (N/2)+2. This is now even and would go back into the 1st equation. I keep doing this and the fractions just get bigger.

 

[Dick]

Ok, here's an example what I've been trying to lead you to. Suppose you are doing P(10)->P(11). P(10) means m=1...10 all work. So you just need to do m=11. From 11 the next term is 12. Then you go to 6. Now you don't need to go any further! You already know m=6 works because that's in the definition of P(10) since 6<=10. We are doing 'complete induction' like Redbelly referenced. Can you do that sort of argument for general N?

 

[nate9228]

Ok, I see your argument. You know P(10) is true already, meaning any m<10 you also know to be true. When you do P(11) you get 11+1=12 which you would divide by 2 which gives you 6 which is less then 10 and therefore known to be true, therefore P(11) is also true. Now I just need to formulate that into symbols lol

 

[Dick]

Ok, I see your argument. You know P(10) is true already, meaning any m<10 you also know to be true. When you do P(11) you get 11+1=12 which you would divide by 2 which gives you 6 which is less then 10 and therefore known to be true, therefore P(11) is also true. Now I just need to formulate that into symbols lol

You were doing great in post 11. You just didn't need to go past (N+2)/2, right?

 

[nate9228]

Hmm right. How about this. Starting at the inductive step we have this:
I assume x_n is true for a given N. I will also assume this N is even. Then by the formula x_n= N/2 and I assume that this is odd. Now to show P(N+1). If N is even, N+1 is odd, therefore goes into the 2nd formula giving N+1+1= N+2 which is even again and goes into the 1st formula. This becomes (N+2)/2= (N/2)+(2/2)= (N/2)+1. As stated above, x_n= N/2, so (N/2)+1= (x_n)+1 and this is precisely the definition of x_n+1 when x_n is odd. Sound about right Dick??

 

[Robert1986]

Hmm right. How about this. Starting at the inductive step we have this:
I assume x_n is true for a given N. I will also assume this N is even. Then by the formula x_n= N/2 and I assume that this is odd.

Why do you assume it is odd? What if N=30? All you need to know is that it is LESS than the number you started with, now apply the induction hypothesis on this number.

Now to show P(N+1). If N is even, N+1 is odd, therefore goes into the 2nd formula giving N+1+1= N+2 which is even again and goes into the 1st formula. This becomes (N+2)/2= (N/2)+(2/2)= (N/2)+1. As stated above, x_n= N/2, so (N/2)+1= (x_n)+1 and this is precisely the definition of x_n+1 when x_n is odd. Sound about right Dick??

Well, I'm not Dick, but perhaps I can help.

What do you think you have shown at this step? And what exactly are you doing with p(N+1) if you are assuming N is even?

You need to use complete induction which means you assume that the statement is true for ALL M < N (not just N-1.) Then you need to split the induction into two cases: N is even and N is odd. Then,
you need to use the fact that it is true for all M < N to prove it is true for N.

 

[Dick]

Hmm right. How about this. Starting at the inductive step we have this:
I assume x_n is true for a given N. I will also assume this N is even. Then by the formula x_n= N/2 and I assume that this is odd. Now to show P(N+1). If N is even, N+1 is odd, therefore goes into the 2nd formula giving N+1+1= N+2 which is even again and goes into the 1st formula. This becomes (N+2)/2= (N/2)+(2/2)= (N/2)+1. As stated above, x_n= N/2, so (N/2)+1= (x_n)+1 and this is precisely the definition of x_n+1 when x_n is odd. Sound about right Dick??

It's pretty garbled from the beginning "I assume x_n is true for a given N". x_n is neither true nor false, it's a number in the sequence and I'm not even sure which one you mean. I'm pretty sure you get the idea but you are using the words and symbols all wrong. Look back at my post 12 where I explained how to do P(10) to P(11). Try to explain how to go from P(11) to P(12) in a similar way. It is really helpful to work with specific numbers before you jump to the abstract 'N'.

 

[nate9228]

Oh yes I agree that my last post was garbled and the language was wrong. I have it written much more precisely on my paper here. I just wanted to make sure my general logic was finally correct, namely that I assumed P(N) was true (not x_n) and that that it holds for all m<N and then in one case I would assume N was even and do the math similar to what I stated before, and then in another case I would say N was odd and do it again.

 

[Dick]

Oh yes I agree that my last post was garbled and the language was wrong. I have it written much more precisely on my paper here. I just wanted to make sure my general logic was finally correct, namely that I assumed P(N) was true (not x_n) and that that it holds for all m<N and then in one case I would assume N was even and do the math similar to what I stated before, and then in another case I would say N was odd and do it again.

That's exactly how the proof goes, if you omit all the details. Don't forget to explicitly prove a base case.