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!

Homework Help: Prove sequence converges

  1. Nov 1, 2009 #1
    1. The problem statement, all variablproves and given/known data
    X0=1, Xn+1=1/4 (1+2/Xn) for n=0,1,2,3,4....
    prove that this sequence converges ,and find the limit

    2. Relevant equations

    3. The attempt at a solution
    I though that Squeeze law might be used ,and let L=1/4(1+2/L) L=0.8437
    and the sequence is not monotonic
    so , how can i prove it next ?
  2. jcsd
  3. Nov 1, 2009 #2


    Staff: Mentor

    I would calculate a few terms in the series to see if I could come up with a non-recursive formula for xn.
  4. Nov 1, 2009 #3
    but how can i apply Squeeze law.
  5. Nov 1, 2009 #4


    Staff: Mentor

    First things first. Try to find a non-recursive formula for xn, and then worry about the technique to use to see if the sequence converges or not.
  6. Nov 1, 2009 #5


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    [edit] oops, made a mistake, deleting it so I can fix it
  7. Nov 3, 2009 #6
    I'm interested how this is solved. Has anyone done it? If so, how.
  8. Nov 3, 2009 #7
    I've just been having a pop at this and decided to turn it into two sequences, one increasing, one decreasing, where:

    X_n+1 = 1/4 + 2/(1+2/X_n)
    With X_0 = 1 or 3/4

    Would it be sufficient to show that one or both of these are bounded and monotonic?
  9. Nov 4, 2009 #8


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I think I finally found a solution, but it's ugly and hopefully someone knows a much cleaner way.

    Let [itex]L[/itex] be the positive solution to

    [tex]L = \frac{1}{4}\left(1 + \frac{2}{L}\right)[/tex]

    or equivalently

    [tex]4L^2 - L - 2 = 0[/tex]

    Thus, [tex]L \approx0.84307[/tex].

    If [itex](x_n)[/itex] has a limit, then it must be [itex]L[/itex] because it's easy to see that [itex]x_n[/itex] is never negative.

    The hard part is proving that [itex](x_n)[/itex] has a limit. I shall do this by proving that the sequence

    [tex]y_n = x_n - L[/tex]

    has a limit of 0. To do this, I shall find a constant [itex]C < 1[/itex] such that

    [tex]\left|\frac{y_{n+1}}{y_n}\right| < C[/tex]

    for all [itex]n[/itex].

    First, I need a small lemma, namely:

    [tex]|y_n| < 0.2[/tex] for all n

    This will be proved inductively. Clearly it's true for [itex]n = 0[/itex], because

    [tex]|y_0| = |x_0 - L| \approx |1 - 0.84307| \approx 0.15693[/tex]

    Now suppose that [itex]|y_n| < 0.2[/itex]; we must show that this implies [itex]|y_{n+1}| < 0.2[/itex]. Indeed, [itex]|y_n| < 0.2[/itex] implies that [itex]L - 0.2 < x_n < L + 0.2[/itex]. Therefore,

    [tex]\frac{2}{L+0.2} < \frac{2}{x_n} < \frac{2}{L-0.2}[/tex]

    and this means

    [tex]\frac{1}{4}\left(1 + \frac{2}{L+0.2}\right) < \frac{1}{4}\left(1 + \frac{2}{x_n}\right) < \frac{1}{4}\left(1 + \frac{2}{L - 0.2}\right)[/tex]

    This is the same as

    [tex]0.72935 < x_{n+1} < 1.0275[/tex]

    and we also have [itex]L - 0.2 < 0.72935[/itex] and [itex]1.0275 < L + 0.2[/itex], so

    [tex]L - 0.2 < x_{n+1} < L + 0.2[/tex]

    or equivalently

    [tex]|y_{n+1}| < 0.2[/tex], concluding the proof of the lemma.

    For the rest of the proof, we substitute [itex]x_n = y_n + L[/itex] into the original recurrence relation, cross-multiply the denominator, and use the fact that [itex]4L^2 - L - 2 = 0[/itex] to simplify the result to

    [tex]4y_{n+1}y_n + 4L(y_n + y_{n+1}) = y_n[/tex]

    and solving for [itex]y_{n+1}[/itex] we get

    [tex]y_{n+1} = \frac{y_n(1 - 4L)}{4(y_n+L)}[/tex]

    Then, using the fact that

    [tex]\frac{1}{|y_n+L|} = \frac{1}{|x_n|} = \frac{1}{x_n} < \frac{1}{L - 0.2}[/tex]

    we have

    [tex]|y_{n+1}| = \frac{|y_n| \cdot |1 - 4L|}{4|y_n+L|} < \frac{|y_n| \cdot |1 - 4L|}{4|L - 0.2|} = |y_n| \cdot 0.92225[/tex]


    [tex]\frac{|y_{n+1}|}{|y_n|} < C[/tex]

    where [itex]C = 0.92225[/itex], concluding the proof.

    It ain't pretty, but it gets the job done, unless I screwed up somewhere.

    By the way, there is nothing magic about the number 0.2. At some point I concluded that I needed a number less than 0.25 but big enough to handle the variation of the sequence about its limit, and I chose 0.2 after "cheating" by plotting the sequence in Matlab.
    Last edited: Nov 4, 2009
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook