Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof about a sequence.

  1. Jan 23, 2012 #1
    1. The problem statement, all variables and given/known data
    Show that the sequence [itex] (x_1,x_2,x_3,....) [/itex]
    defined by; Let [itex] x_1=1 [/itex] for each [itex] n \in \mathbb{N} [/itex]
    [itex] x_{n+1}= \frac{x_n}{2}+1 [/itex]
    [itex] x_2=\frac{3}{2} [/itex]
    Show that this sequence is bounded above by 2; that is prove that [itex] x_n\leq2 [/itex] for all [itex] n\in\mathbb{N} [/itex]
    3. The attempt at a solution
    This seems weird to me because it doesn't seem like it would be bounded above by 2, I could find some x that was bigger that 2. unless I don't understand the question.
     
  2. jcsd
  3. Jan 23, 2012 #2

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The statement that it's bounded from above by 2 means precisely that all terms in the sequence are ≤2. If you can find a term that's >2, then you have proved that it's not bounded from above by 2.

    I suggest that you try to determine what the consequences would be if there's an integer N≥2 such that ##x_N>2##.
     
    Last edited: Jan 23, 2012
  4. Jan 23, 2012 #3
    You can show it by using induction.
     
  5. Jan 23, 2012 #4
    okay I should have looked at it closer, it does look like it will stay below 2. so should I try to manipulate it into a form that will work and then use induction. thanks for the replies by the way.
     
  6. Jan 23, 2012 #5

    Curious3141

    User Avatar
    Homework Helper

    You can arrive at a nice contradiction by "going backward".

    Suppose there was some k (k > 1) such that [itex]x_k = 2 + \epsilon[/itex], where [itex]\epsilon \geq 0[/itex].

    Calculate [itex]x_{k-1}, x_{k-2}[/itex] (observe that they're increasing as you're going backward) and derive the general term [itex]x_{k-r}[/itex]. Prove this by induction (really easy).

    Now set [itex]r = k-1[/itex]. What do you get?
     
  7. Jan 23, 2012 #6

    Curious3141

    User Avatar
    Homework Helper

    Even more easily, using the same approach I detailed you can prove the "forward" case by induction. If you show that [itex]x_k < 2 \Rightarrow x_{k+1} < 2[/itex], you're done.
     
  8. Jan 23, 2012 #7
    can I do this. [itex] x_1=1 [/itex] so 1 is less than 2 so the base case is confirmed.
    now [itex] 2(x_{n+1}-1)=x_n\leq2 [/itex]
    then say that [itex] 2(x_{n+1}-1)\leq2 [/itex]
    the divide both sides by 2 and then add the 1 so now we have
    [itex] x_{n+1}\leq2 [/itex]
    so does this work, kinda seems recursive
     
  9. Jan 23, 2012 #8

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This is a good way to do it. Since you have found one solution, I don't mind telling you another. This is what I had in mind before:

    For all n such that ##x_n>2##, we have ##\frac{x_{n-1}}{2}+1<2##, which implies that ##x_{n-1}>2##. So if one term is >2, every one that came before it is too. This contradicts ##x_1\leq 2##.
     
  10. Jan 23, 2012 #9
    interesting idea fredrik, thanks to everyone who made a post.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook