Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
add comment

3 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.