If $x_0$ and $x_1$ are positive numbers and $s_n = \frac12(x_n + x_{n-1})$, prove that the sequence converges.

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?

• 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... – David C. Ullrich Nov 7 '15 at 18:31
• i was confused too because that is exactly how it is written on paper – idknuttin Nov 7 '15 at 18:42
• For what it's worth, $0$ is not a positive number. – Arnaud Mortier Jun 6 '18 at 21:49

3 Answers

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

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

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