# How to prove a sequence converges linearly or quadractically?

1. Mar 8, 2004

### 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.

2. Mar 8, 2004

### HallsofIvy

Staff Emeritus
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}$$.

Last edited: Mar 9, 2004
3. Mar 9, 2004

### HallsofIvy

Staff Emeritus
"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.

4. Mar 9, 2004

### 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.

5. Mar 11, 2004

### dinosoup

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