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