How quickly does the series defined by $$x\_0 = 0, \ x\_{n+1} = \frac{x\_n^2+1}{2}$$ converge to $1$?



What is the rate of convergence?
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](https://books.google.com/books?id=_tnwmvHmVwMC&lpg=PP1&pg=PA153#v=onepage&q&f=false).


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


