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

3 Answers 3

5

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.

  • 0
    Thank you for the really clear answer !2012-09-04
  • 0
    @Skydreamer - Happy to help!2012-09-04
3

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

1

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