3
$\begingroup$

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.

2 Answers 2

2

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

0

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