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

How to prove a sequence converges linearly or quadractically?

  1. Mar 8, 2004 #1
    I have a question from my assignment which requires me to prove that a sequence converges to 0 linearly, and another sequence that converges quadractically. I have no idea how to do this. The prof didn't talk much about it neither have the TA.

    The textbook book just gives the following about convergence:

    "A method that produces a sequence of {pn} of approximations that converge to a number p converges linearly if, for large values of n, a constant 0 < M < 1 exists with

    |p - p(n+1)| <= M|p - pn|

    The sequence converges quadractically if, for large values of n, a constant 0 < M exists with

    |p - p(n+1)| <= M|p - pn|^2

    The n, (n+1) are meant to be subscripts. Could someone prove an example sequence which converges linearly or quadractically? Or give me some tips on how to do so? Thanks.
  2. jcsd
  3. Mar 8, 2004 #2


    User Avatar
    Science Advisor

    Here are a couple of obvious ones:

    [tex]\frac{3n+2}{n+1}[/tex] converges to 3 linearly because
    [tex]|3-\frac{3(n+1)+2}{(n+1)+1}|= \frac{1}{n+2}[/tex]
    while [tex]|3-\frac{3n+2}{n+1}|= \frac{1}{n+1}[/tex]

    and certainly [tex] \frac{1}{n+2}< 1* \frac{1}{n+1}[/tex].
    Last edited by a moderator: Mar 9, 2004
  4. Mar 9, 2004 #3


    User Avatar
    Science Advisor

    "quadratic" convergence is a little harder (which is why it wasn't in my first post. I had to think about it!) but here is an obvious example:

    Take p0= 1 and then define recursively:
    pn+1= (1/2)pn2.

    That is: p0= 1
    p1= 1/2
    p2= 1/2(1/4)= 1/8
    p3= 1/2(1/64)= 1/128 etc.

    That clearly converges to 0. for any n, |p- pn+1| = pn+1= (1/2)p2 so it obviously of quadratic convergence (with M= 1/2).

    The recursive formula makes that obvious. I could have blown your mind by handing you the result: [tex]p_n= \frac{1}{2^{2^n-1}}[/tex]!

    You can get a sequence that converges to any number, m, by simply adding m to that sequence: would you have guessed that
    [tex]p_n= \frac{(5)(2^{2^n}-1)}{2^{2^n-1}} [/tex] converges quadratically to 5?

    You should now be able to create sequences that converge to any number with any power of convergence.
  5. Mar 9, 2004 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Thanks for that clarifying post. I've never heard of these types of convergence, and it worried me slightly that a non-convergent (in the usual sense) sequence could be said to converge quadratically, as appeared in the original version of the first reply.
  6. Mar 11, 2004 #5
    Hi thanks for your reply HallsofIvy. Though I counldn't figure out how to do the question from my assignment. But thanks again.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook