Asymptotic behavior of recursive sequence

Question

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$

Answer 1

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

Answer 2

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.