1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Can anyone PROVE the x+1 problem?

  1. Oct 7, 2012 #1
    Can anyone PROVE the x+1 problem??

    1. The problem statement, all variables and given/known data
    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.


    2. Relevant equations



    3. 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.
     
  2. jcsd
  3. Oct 7, 2012 #2
    Re: Can anyone PROVE the x+1 problem??

    Correction: m>0 (A natural number)
     
  4. Oct 7, 2012 #3
    Re: Can anyone PROVE the x+1 problem??

    Cant anyone help? I also believe it is proved by induction.
     
  5. Oct 7, 2012 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Can anyone PROVE the x+1 problem??

    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?
     
  6. Oct 7, 2012 #5
    Re: Can anyone PROVE the x+1 problem??

    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?
     
  7. Oct 7, 2012 #6
    Re: Can anyone PROVE the x+1 problem??

    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.
     
  8. Oct 7, 2012 #7
    Re: Can anyone PROVE the x+1 problem??

    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.
     
  9. Oct 7, 2012 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Can anyone PROVE the x+1 problem??

    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.
     
    Last edited: Oct 7, 2012
  10. Oct 7, 2012 #9

    Redbelly98

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

  11. Oct 7, 2012 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Can anyone PROVE the x+1 problem??

    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?
     
  12. Oct 7, 2012 #11
    Re: Can anyone PROVE the x+1 problem??

    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.
     
  13. Oct 7, 2012 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Can anyone PROVE the x+1 problem??

    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?
     
  14. Oct 7, 2012 #13
    Re: Can anyone PROVE the x+1 problem??

    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
     
  15. Oct 7, 2012 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Can anyone PROVE the x+1 problem??

    You were doing great in post 11. You just didn't need to go past (N+2)/2, right?
     
  16. Oct 7, 2012 #15
    Re: Can anyone PROVE the x+1 problem??

    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??
     
  17. Oct 7, 2012 #16
    Re: Can anyone PROVE the x+1 problem??

    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.

    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.
     
  18. Oct 7, 2012 #17

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Can anyone PROVE the x+1 problem??

    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'.
     
  19. Oct 8, 2012 #18
    Re: Can anyone PROVE the x+1 problem??

    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.
     
  20. Oct 8, 2012 #19

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Re: Can anyone PROVE the x+1 problem??

    That's exactly how the proof goes, if you omit all the details. Don't forget to explicitly prove a base case.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Can anyone PROVE the x+1 problem?
  1. How to prove x^a >= 1? (Replies: 3)

Loading...