Upper bound of a recursive sequence for a fixed $n$

Question

I have a recursive sequence given by $$x_n = \sqrt{\frac{1+x_{n-1}}{2}},\ x_1=0$$ I can easily show that it is increasing, bounded and thus converges with its limit being $1$. But what if I wanted to upper bound $x_{n_0}$ for some fixed $n_0$? This bound should be dependent on $n$. How should I proceed?

Answer 1

$$ x_0=\cos \frac{\pi}{2}\\ x_1=\cos \frac{\pi}{4}\\ \vdots\\ x_n=\cos 2^{-n-1}\pi $$

Answer 2

Your sequence is increasing and you probably know it converges, so you can assume that $x_n \approx x_{n-1}$. \begin{eqnarray} x_n^2 = 0.5 + 0.5 x_n \\ x_n^2 - 0.5 - 0.5 x_n =0 \\ \to x_n = \frac{1}{4} \pm \sqrt{\frac{1}{16} + \frac{1}{2}}= \frac{1}{4}\pm\frac{3}{4}=1 \end{eqnarray} This is your upper bound.

Answer 3

If $x_n = \sqrt{\frac{1+x_{n-1}}{2}},\ x_1=0 $, then $x_n \to 1$, so let's look at $y_n = 1-x_n$.

$1-y_n = \sqrt{\frac{1+(1-y_{n-1})}{2}} = \sqrt{\frac{1+(1-y_{n-1})}{2}} = \sqrt{1-\frac{y_{n-1}}{2}} $ so $1-2y_n+y_n^2 =1-\frac{y_{n-1}}{2} $ or $y_n-\frac14 y_n^2 =\frac14 y_{n-1} $.

Since $0 \le x_n < 1$, $0 < y_n \le 1$. Therefore $y_n \le \frac14 y_{n-1}+ \frac14 y_{n}^2 \le \frac14 (y_{n-1}+1) $ and $y_n \ge \frac14 y_{n-1} $. From the second, since $y_1 = 1$, $y_n \ge 1/4^{n-1}$.

For an upper bound. we have $y_1 = 1, y_2 \le \frac14(1+1) =\frac12, $ and $y_n \le \frac12$ for $n \ge 2$.

Therefore $y_n(1-\frac14 y_n) =\frac14 y_{n-1} $ so, for $n \ge 2$, $y_n =\dfrac{ y_{n-1}}{4(1-\frac14 y_n)} \le\dfrac{ y_{n-1}}{4(1-\frac14 \frac12)} =\dfrac{ y_{n-1}}{4(\frac78)} =\dfrac{2 y_{n-1}}{7} $.

Therefore, for $n \ge 3$, $y_n \le \frac12(2/7)^{n-2} $.