Inequality proof on a 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 have to prove that : $$u_n \leq n + \frac{u_0}{2^n}$$

I don't really know where I should start to prove this... Can someone give me an hint ?

-

Let's use mathematical induction to prove this.

The inequality clearly holds for base case $n = 0$: $$u_0 \le 0 + \frac{u_0}{2^0}$$

Assume the inequality holds for $n - 1$: $$u_{n-1} \le n - 1 + \frac{u_0}{2^{n-1}} \tag{1}$$

We have:

\begin{align*} u_n &= \sqrt{n + u_{n-1}} \\ \Rightarrow u_n^2 &= n + u_{n-1} \end{align*}

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

Rearrange to get: $$\frac{u_n^2 + 1}{2} \le n + \frac{u_0}{2^n}$$

In a previous question of yours, you've seen that: $$a \le \frac{a^2 + 1}{2}$$

Therefore: $$u_n \le \frac{u_n^2 + 1}{2} \le n + \frac{u_0}{2^n}$$

Which is what we want to prove.

-
Thank you for the really clear answer ! –  Skydreamer Sep 4 '12 at 20:58
@Skydreamer - Happy to help! –  Ayman Hourieh Sep 4 '12 at 21:00

As the definition of $u_n$ suggests, we have to use induction. For $n=0$, we have equality, and if it's true for a $n\geq 0$, then $$u_{n+1}=\sqrt{n+1+u_n}\leq \sqrt{n+1+n+\frac{u_0}{2^n}}=\sqrt{2n+1+\frac{u_0}{2^n}}.$$ We have to show that $$2n+1+\frac{u_0}{2^n}\leq \left(n+1+\frac{u_0}{2^{n+1}}\right)^2,$$ which is the case, as $u_0\geq 0$ and $$\left(n+1+\frac{u_0}{2^{n+1}}\right)^2=n^2+\color{red}{2n+1}+(n+\color{red}1)\color{red}{\frac{u_0}{2^n}}+\frac{u_0^2}{2^{2(n+1)}}.$$

-

$$\left\{ u_0 \geq 0 \\ \forall n \in \mathbb{N}^*, u_n = \sqrt{n+u_{n-1}} \right.$$ we have to prove that : $$u_n \leq n + \frac{u_0}{2^n}$$

$u_{1}=\sqrt{1+u_{0}}$ and we verify that : $\displaystyle u_{1} \leq 1+\frac{u_{0}}{2}$ $\Leftrightarrow$ $\displaystyle \sqrt{(1+u_{0})\cdot 1} \leq \frac{1+u_{0}+1}{2}=1+\frac{u_{0}}{2},$ so the firts step is done for induction.

-