how to prove a sequence converges linearly or quadractically?

[dinosoup]

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.

[HallsofIvy]

Here are a couple of obvious ones:

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

and certainly \frac{1}{n+2}< 1* \frac{1}{n+1}.

[HallsofIvy]

"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: p_n= \frac{1}{2^{2^n-1}}!

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

You should now be able to create sequences that converge to any number with any power of convergence.

[matt grime]

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.

[dinosoup]

Hi thanks for your reply HallsofIvy. Though I counldn't figure out how to do the question from my assignment. But thanks again.