Inequality proof on a 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 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 ?
 A: 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.
A: 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)}}.$$
A: \begin{equation}
  \left\{
u_0 \geq 0 \\
\forall n \in \mathbb{N}^*, u_n = \sqrt{n+u_{n-1}}
    \right.
\end{equation}
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. 
