Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 5 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|cite|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

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|cite|improve this answer

\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|cite|improve this answer

Your Answer


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.