Asymptotic analysis of a recurring sequence Let $(u_n)$ be a sequence defined by:
$$\begin{equation}
  \left\{
u_0 \geq 0 \\
\forall n \in \mathbb{N}^*, u_n = \sqrt{n+u_{n-1}}
    \right.
\end{equation}$$
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.
 A: 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
$$
A: 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$.
