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

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?

• How sharp a bound are you looking for? Already $x_{14}=0.999999982$ – lulu Apr 13 '18 at 14:01
• I think I'm asking whether it is possible to obtain some clever functional bound $f(n)$ on this recursive sequence. I need a bound for a proof and $1$ doesn't cut it, some formula dependent on $n$ would be better, but I do not know whether I can retrieve something like that. – Jules Apr 13 '18 at 14:04

## 3 Answers

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

• Was that a guess given the first two elements or is there some deeper reasoning to your answer? – Jules Apr 13 '18 at 14:06
• I recognized the formula for $\cos \theta/2$ and just set $x_0=\cos\arccos 0$ – saulspatz Apr 13 '18 at 14:13
• For any $y\in \Bbb R,$ if $\cos y \ne 1$ then $1-y^2/2+y^4/24>\cos y>1-y^2/2.$ So $0<1-x_n=( (y_n)^2/2 )(1-(y_n)^2\delta_n/12) <(y_n)^2/2,$ where $y_n=2^{-n-1}\pi$ and $0<\delta_n<1.$ – DanielWainfleet Apr 13 '18 at 21:27

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.

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