# Asymptotic analysis of a recurring sequence

Let $(u_n)$ be a sequence defined by:

$$$$\left\{ u_0 \geq 0 \\ \forall n \in \mathbb{N}^*, u_n = \sqrt{n+u_{n-1}} \right.$$$$

I'd like to prove that when $n \rightarrow +\infty$ :

$$u_n \sim \sqrt n$$

This would basically mean that : $$\lim_{n\rightarrow\infty}\frac{u_n}{\sqrt{n}} = 1$$ That's to say : $$\lim_{n\rightarrow\infty}\sqrt{\frac{n+u_{n-1}}{n}} = 1$$

Well, we can't replace $u_{n-1}$ and go on down to $u_0$... The result seems quite logic though I have no idea how I can really prove that.

-

From a previous question of yours, we have: $$\forall n \in \mathbb{N} : u_n \leq n + \frac{u_0}{2^n} \tag{1}$$

Clearly, $u_{n-1} \ge 0$. Therefore: $$\sqrt{n} \le \sqrt{n + u_{n-1}} = u_n$$

This gives us a lower bound for the limit we want to prove: $$\frac{u_n}{\sqrt{n}} \ge 1 \Rightarrow \lim_{n \to \infty} \frac{u_n}{\sqrt{n}} \ge 1$$

Using the definition of $u_n$ twice, we have: $$u_n = \sqrt{n + u_{n-1}} = \sqrt{n + \sqrt{n - 1 + u_{n-2}}}$$

Using the inequality in (1): $$u_n \le \sqrt{n + \sqrt{n - 1 + n - 2 + \frac{u_0}{2^{n-2}}}}$$

Hence: $$\frac{u_n}{\sqrt{n}} \le \sqrt{1 + \sqrt{\frac{2}{n} - \frac{3}{n^2} + \frac{u_0}{n^2 2^{n-2}}}}$$

The RHS converges to $1$ as $n \to \infty$. This gives us the upper bound we seek. Therefore: $$\lim_{n \to \infty} \frac{u_n}{\sqrt{n}} = 1$$

-

Let $v_n = u_n/\sqrt{n}$. Then $$v_n = \frac{\sqrt{n+u_{n-1}}}{\sqrt{n}} = \sqrt{1 + \frac{\sqrt{n-1}}{{n}} v_{n-1}}$$

Since $v_{n-1} \ge 0$ we get $v_n \ge 1$. Moreover, since $\sqrt{1+t} \le 1 + t/2$ for $t \ge 0$ we get $v_n \le 1 + \dfrac{\sqrt{n-1}}{2n} v_{n-1}$. For any $\epsilon > 0$, take $N$ large enough that $\sqrt{N-1}/(2N) < \epsilon$. Then for $n > N$ we have $v_n \le 1 + \epsilon v_{n-1}$, which implies $v_n \le \frac{1}{1-\epsilon} + C \epsilon^n$ for $n > N$ where $C$ is some constant, and in particular $\limsup_{n \to \infty} v_n \le 1/(1-\epsilon)$. This being the case for all $\epsilon > 0$, we conclude that $\lim_{n \to \infty} v_n = 1$.

-