1
$\begingroup$

If $x_0$ and $x_1$ are positive numbers and $s_n = \frac12(x_n + x_{n-1})$, prove that the sequence converges.
(Hint : use the "Nested closed intervals Theorem")

I know what the nested closed interval theorem is and how to prove it, but I have no idea how to prove that the sequence converges. I am also having trouble interpreting the sequence, for example if $n=1$ do you get $\frac12(1+0)$?
Can I prove this buy figuring out if it is an increasing or decreasing sequence and then find an upper or lower bound?

$\endgroup$
  • 1
    $\begingroup$ What sequence? The notation in your post would appear to indicate there's a sequence called $x_n$ and another sequence called $s_n$. You haven't given enough information to specify either one, and you haven't said which one you want to show converges. Try copying the problem much more carefully... $\endgroup$ – David C. Ullrich Nov 7 '15 at 18:31
  • $\begingroup$ i was confused too because that is exactly how it is written on paper $\endgroup$ – idknuttin Nov 7 '15 at 18:42
  • $\begingroup$ For what it's worth, $0$ is not a positive number. $\endgroup$ – Arnaud Mortier Jun 6 '18 at 21:49
4
$\begingroup$

Probably you mean ${\displaystyle x_{n+1} = {x_n + x_{n-1} \over 2}}$. If that's the case, the idea is that the interval $I_n = [x_n,x_{n+1}]$ (or $[x_{n+1},x_n]$ if $x_n > x_{n+1}$) is a subinterval of $I_{n-1}$ of half the length of $I_{n-1}$.

$\endgroup$
4
$\begingroup$

More generally, if $x_{n+1} =ax_n+(1-a)x_{n-1} $, where $0 < a < 1$, then $x_n$ converges.

This problem has $a = \frac12$.

Proof:

If $x_{n+1} =ax_n+(1-a)x_{n-1} $, where $0 < a < 1$, then

$\begin{array}\\ x_{n+1}-x_n &=(a-1)x_n+(1-a)x_{n-1}\\ &=(a-1)(x_n-x_{n-1})\\ \text{by induction}\\ x_{n+k}-x_{n+k-1} &=(a-1)^k(x_n-x_{n-1})\\ \text{so that, setting }n=1,\\ x_{k+1}-x_{k} &=(a-1)^k(x_1-x_{0})\\ \end{array} $

Since $-1 < a-1 < 0$, $x_n$ converges.

Also, summing $x_{k+1}-x_{k} =(a-1)^k(x_1-x_{0}) $ from $0$ to $n-1$,

$\begin{array}\\ x_n-x_0 &=\sum_{k=0}^{n-1} (x_{k+1}-x_{k})\\ &=\sum_{k=0}^{n-1} ((a-1)^k(x_1-x_{0}))\\ &=(x_1-x_{0})\sum_{k=0}^{n-1} (a-1)^k\\ &=(x_1-x_{0})\frac{1-(a-1)^n}{1-(a-1)} \\ &=\frac{(x_1-x_{0})(1-(a-1)^n)}{2-a} \\ &=\frac{x_1-x_{0}}{2-a} -\frac{(x_1-x_{0})(a-1)^n)}{2-a} \\ \text{so that}\\ x_n &=x_0+\frac{x_1-x_{0}}{2-a} -\frac{(x_1-x_{0})(a-1)^n)}{2-a} \\ &=\frac{x_0(2-a)+x_1-x_{0}}{2-a} -\frac{(x_1-x_{0})(a-1)^n)}{2-a} \\ &=\frac{x_0(1-a)+x_1}{2-a} -\frac{(x_1-x_{0})(a-1)^n)}{2-a} \\ \text{so that}\\ \lim_{n \to \infty} x_n &=\frac{x_0(1-a)+x_1}{2-a} \\ \end{array} $

$\endgroup$
0
$\begingroup$

Although @martycohen's answer is quite complete, I'd like to share another method of solving the problem in this particular case. Working in base $2$ helps in figuring out the limit, for here is what the sequence $\{ x_n \}$ looks like in base $2$: $$ \begin{align} x_0 &= 0\\ x_1 &= 1\\ x_2 &= 0.1\\ x_3 &= 0.11\\ x_4 &= 0.101\\ x_5 &= 0.1011\\ x_6 &= 0.10101\\ x_7 &= 0.101011\\ x_8 &= 0.1010101\\ x_9 &= 0.10101011\\ x_{10}&= 0.101010101\\ &\ \, \vdots \end{align} $$ The pattern should be obvious, and the limit is exactly what you'd expect it to be: $$\lim_{n \to \infty} x_n = 0.\overline{10} = 0.10101010\dots.$$ Thus, the limit equals $$ \sum_{i=1}^\infty \frac{1}{2^{2k-1}} = \frac{1/2}{1-(1/4)} = \frac{2}{3}. $$

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