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!

Proving convergence of recursive sequence.

  1. Mar 23, 2014 #1
    1. The problem statement, all variables and given/known data

    Prove for c>0 the sequence [itex]{x_n} = \frac{1}{2}(x_{n-1} + \frac{c}{x_{n-1}})[/itex] converges.


    3. The attempt at a solution

    This is proving difficult, I have never dealt with recursive sequences before. Any help would be appreciated. Thanks.
     
  2. jcsd
  3. Mar 23, 2014 #2
    So, I have an idea, but i'm not sure if it proves convergence.

    If [itex]x_{n} = g(x_{n-1})[/itex] then all I have to do it let [itex]x = g(x)[/itex].





    EDIT: Upon further thought, it does not as convergence => [itex]x_{n} = g(x_{n-1})[/itex]. It is not a iff situation. Back at square one.
     
    Last edited: Mar 23, 2014
  4. Mar 23, 2014 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    You have the following handy theorem:

    I would start by trying to apply this one. Can you show the sequence is increasing/decreasing? Can you find a lower/upper bound?
     
  5. Mar 23, 2014 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    This is a nice remark, because if the sequence converges, you can find out the limit point this way. Indeed, you have ##x_n = g(x_{n-1})##. Thus

    [tex]x = \lim_{n\rightarrow +\infty} x_n = \lim_{n\rightarrow +\infty} g(x_{n-1}) = g(x)[/tex]

    So can you figure out what the limit point ##x## is? (of course you still have to prove it actually converges!)
     
  6. Mar 23, 2014 #5
    So this is what I have so far.

    [itex] x_0 = r [/itex] r is a non-zero real number

    [itex] x_{n+1} = x_n(\frac{1}{2} + \frac{c}{2x_n^2}) [/itex]


    Case 1: ##r^2 < c~ \Rightarrow## sequence is increasing

    Case 2: ##r^2 > c ~\Rightarrow## sequence is decreasing
     
    Last edited: Mar 23, 2014
  7. Mar 23, 2014 #6

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Not quite:

    Suppose c = 4 and x_0 = 1, then x_1 = 5/2 and x_2 = 89/40, so neither increasing nor decreasing!

    You're on the right track, though.
     
  8. Mar 23, 2014 #7

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    To see what is happening, look at the graph of
    [tex] y = f(x), \text{ where } f(x) = \frac{1}{2} \left( x + \frac{c}{x} \right)[/tex]
    Look up material about "cobweb plots"; see, eg., http://en.wikipedia.org/wiki/Cobweb_plot . This will give you some intuition about what is happening; it is not yet a 'proof', but may help get you started.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proving convergence of recursive sequence.
Loading...