1. Limited time only! Sign up for a free 30min personal 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!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof about a sequence.
  1. Sequence proof (Replies: 6)

Loading...