Asymptotic behavior of recursive sequence Suppose, the real sequence
$x_{n+1}=\frac{1}{2}(x_n+\sqrt{x_n^2+c})$ with c>0 is given.
Find the asymptotic behavior of this sequence.
I have shown, that this sequence goes to infinity as $n\to\infty$ per contradiction. I guess, that it holds
$x_n \approx \frac{1}{2}\sqrt{cn}$
which is motivated by 
$x_{n+1}^2=\frac{1}{2}x_n^2(1+\sqrt{1+\frac{c}{x_n}})+\frac{1}{4}c \approx x_n^2 + \frac{1}{4}c$
where I used the approximation $\sqrt{1+\frac{c}{x_n}} \approx 1$ as $n \to \infty$.
I have problems, to turn this into a formal proof, since it holds for the error term for my approximation
$\frac{1}{2}x_n^2(1-\sqrt{1+\frac{c}{x_n}}) \to \infty$
 A: If we set $y_n=x_n^2$ then
$$y_{n+1}=\frac{y_n}2+\frac c4+\frac{y_n}2\sqrt{1+\frac{c}{y_n}}=y_n+\frac{c}2+O(y_n^{-1}).$$
This proves that $(y_n)$ grows at least linearly, so that $y_n^{-1}=O(n^{-1})$.
Therefore
$$y_n=\frac{cn}2+O(\ln n)$$
and
$$x_n=\sqrt{\frac{cn}2}+O\left(\frac{\ln n}{\sqrt n}\right).$$
A: You've already derived that
\begin{align}
x_{n+1}^2 - x_n^2 &= \frac 12 \left(\sqrt{1 + \frac{c}{x_n^2}} -1 \right) + \frac c4 \\
&= \frac{c}{2x_n^2} \frac{1}{\sqrt{1 + \frac{c}{x_n^2}} +1} + \frac c4. 
\end{align}
Taking $n \to \infty$ we obtain
\begin{equation}
\lim\limits_{n\to\infty}\left[x_{n+1}^2 - x_n^2 \right] = \frac c4.
\end{equation}
Let $\epsilon > 0$ be arbitrary. Then there exists $N \in \mathbb{N}$ such that for all $n \geq N$ it holds that
\begin{equation}
\left| x_{n+1}^2 - x_n^2 - \frac c4\right| < \epsilon. 
\end{equation}
We can then write
\begin{align}
\left|\frac{x_n^2}{n} - \frac c4\right| &= \left|\frac{(x_n^2 - x_{n-1}^2 - \frac c4) + ... + (x_{N+1}^2 - x_N^2 - \frac c4)}{n} + \frac{x_N^2}{n} - \frac{cN}{4n}\right| \\
&\leq \frac{(n-N)\epsilon}{n} + \frac{x_N^2}{n} + \frac{cN}{4n}. 
\end{align}
Taking $n \to \infty$ yields
\begin{equation}
\limsup\limits_{n \to \infty} \left|\frac{x_n^2}{n} - \frac c4 \right| \leq \epsilon.
\end{equation}
As $\epsilon$ was arbitrary we get
\begin{equation}
\lim\limits_{n \to \infty} \frac{x_n^2}{n} = \frac c4
\end{equation}
as desired. 
