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