What is the rate of convergence? [closed]

Question

How quickly does the series defined by $$x_0 = 0, \ x_{n+1} = \frac{x_n^2+1}{2}$$ converge to $1$?

Answer 1

Putting $x_n = 1+y_n$, we have $y_{n+1} = y_n + \frac{y_n^2}{2}$. There is a standard method for analyzing recursions of the form $y_{n+1} = y_n+O(y_n^2)$. A good introduction is chapter 8.4 in de Bruijn's Asymptotic Methods in Analysis.

I'll do the first terms of the expansion for you. Set $z_n = 1/y_n$. Then $$z_{n+1} = \frac{1}{z_n^{-1}+z_n^{-2}/2} = z_n - 1/2 + O(1/z_n). \quad (\ast)$$ Since $x_n \to 1^{-}$, we have $y_n \to 0^{-}$ and $z_n \to - \infty$. Thus, for any $\epsilon>0$, we have $|z_{n+1} - (z_n-1/2)| < \epsilon$ for $n$ large enough and we deduce $z_n = - n/2 (1+o(1))$. Reversing our substitutions, $x_n = 1-2(1+o(1))/n$.

We can then deduce tighter bounds by "bootstrapping", plugging our previous bounds in $(\ast)$ to give $$z_{n+1} = z_n - 1/2 + O(1/n)$$ and thus $$z_{n} = -n/2+O(\log n).$$ Taking more terms in the Taylor series $(\ast)$, and bootstrapping repeatedly, we can get an asymtopic series in powers of $n^{-1}$ and $\log n$.