# Prove that the order of convergence must be $\geq 1$

Given a sequence $\{x_n\}_n$ and real numbers $c > 0$ and $L$, such that $\displaystyle\lim_{n \to \infty}x_n - L = 0$ and $\displaystyle\lim_{n \to \infty} \frac{| x_{n+1} - L |}{|x_n - L|^p} = c$, prove that $p \geq 1$.

This is assumed without proof in my textbook and I'd like a rigorous one, but I can't come up with it.

-
Your question title leads to confusion : in the title you should put $\ge$ instead of $>$. – Patrick Da Silva Feb 6 '12 at 23:39
thanks, updated – asmodius Feb 7 '12 at 0:11
Which textbook is this? Have you provided us the whole context? – Aryabhata Feb 7 '12 at 0:36
You should've mentioned $c > 0$ if this is behind the definition of order of convergence. – Patrick Da Silva Feb 7 '12 at 0:53
thanks again, "Calcolo Numerico" by Brugnano et al. didn't mention this. – asmodius Feb 7 '12 at 1:08

If we allow $c = 0$, then this is not true.

Take $$x_n = \frac{1}{n}$$

where we can pick $p = 0.5$

If $c \gt 0$, then I believe it is true.

We use the following fact:

If $f_n \to \infty$ and if $\dfrac{f_{n+1}}{f_n} \to p$, then $p \ge 1$.

(because otherwise $\sum f_n$ would be absolutely convergent, by the ratio test!)

Assuming $x_n \neq L$ for any $n$ (otherwise problem is meaningless I suppose).

Picking $f_n = -\log |x_n - L|$ will give the result, as I believe we can then show that $\dfrac{f_{n+1}}{f_n} \to p$.

-
In the context of numerical analysis, we usually assume $c > 0$. Can you still find something? I thought of $1/n$ too but I knew somehow OP just forgot to mention that, but I should've commented it. The idea is that in the hypothesis of OP's question, we have the definition of order of convergence. – Patrick Da Silva Feb 7 '12 at 0:52
@PatrickDaSilva: I see. Thanks. – Aryabhata Feb 7 '12 at 0:59
@PatrickDaSilva: If $c \gt 0$, then it is true I think. I have added a sketch of a proof/approach. – Aryabhata Feb 7 '12 at 1:49
Yes, this is essentially the approach. I went down through my numerical analysis notes and that's similar to the proof I found there. Good work! – Patrick Da Silva Feb 7 '12 at 7:55
@PatrickDaSilva: Thanks! – Aryabhata Feb 7 '12 at 19:25