0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How sharp a bound are you looking for? Already $x_{14}=0.999999982$ $\endgroup$ – lulu Apr 13 '18 at 14:01
  • $\begingroup$ 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. $\endgroup$ – Jules Apr 13 '18 at 14:04
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Was that a guess given the first two elements or is there some deeper reasoning to your answer? $\endgroup$ – Jules Apr 13 '18 at 14:06
  • 1
    $\begingroup$ I recognized the formula for $\cos \theta/2$ and just set $x_0=\cos\arccos 0$ $\endgroup$ – saulspatz Apr 13 '18 at 14:13
  • $\begingroup$ 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.$ $\endgroup$ – DanielWainfleet Apr 13 '18 at 21:27
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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