Let $\{x_n\}_{n=0}^\infty$ be a sequence of numbers such that $\frac{\vert x_n\vert}{\vert x_{n-1}\vert^2}\leq C$, where $C>0$ is a constant independent of $n$. Is it guaranteed that $\lim_{n\to\infty}x_n=0$, if $x_0$ is small enough (for example, $\vert x_0\vert<1$)?
By definition, if $\vert x_{n}\vert\leq C\vert x_{n-1}\vert^2,\;\;(C>0)$, the convergence is quadratic. Also, if $\vert x_{n}\vert\leq C\vert x_{n-1}\vert,\;\;(0<C<1)$, the convergence is linear. So I'm wondering why there is not restriction that $C<1$ for the quadratic convergence?
Best Answer
I got the hint about the correct answer from Erik Parkinson's answer. The convergence is guaranteed if $\vert x_0\vert C<1$.
Under the above assumption, we can show that the sequence $\{\vert x_n\vert\}_{n=0}^\infty$ is a decreasing sequence. Since the sequence is bounded from below by $0$, it converges. The decreasing nature of the sequence can be proved using induction. We have $\vert x_1\vert\leq C\vert x_0\vert^2< \vert x_0\vert$. Then, using the inductive assumption, we have \begin{equation} \vert x_{n+1}\vert\leq C\vert x_n\vert^2< \vert x_n\vert C \vert x_{0}\vert< \vert x_n\vert. \end{equation} Thus, the sequence converges if $x_0<\frac{1}{C}$.