If $x_1<x_2$ are arbitrary real numbers, and $x_n=\frac{1}{2}(x_{n-2}+x_{n-1})$ for $n>2$, show that $(x_n)$ is convergent.

Question

If $x_1<x_2$ are arbitrary real numbers, and $x_n=\frac{1}{2}(x_{n-2}+x_{n-1})$ for $n>2$, show that $(x_n)$ is convergent. What is the limit?

The back of my textbook says that $\lim(x_n)=\frac{1}{3}x_1+\frac{2}{3}x_2$. I was thinking that if I show that the sequence is monotone increasing by induction, then I can "guess" (from the back of my textbook) that there is an upperbound of the limit and show by induction that all elements in $x_n$ are between $x_1$ and the upperbound and so it's bounded. Then by the monotone convergence theorem say it's convergent.

I'm not sure how to show that it is monotone, and then after showing convergence finding the limit, without magically guessing it.

Answer 1

$\displaystyle{z \in {\mathbb C}\,,\quad \left\vert z\right\vert < 1}$.

$$ \sum_{n = 3}^{\infty}x_{n}\,z^{n} = {1 \over 2}\sum_{n = 3}^{\infty}x_{n - 2}\,z^{n} + {1 \over 2}\sum_{n = 3}^{\infty}x_{n - 1}\,z^{n} $$

\begin{align} ------------&------------------\\ \sum_{n = 1}^{\infty}x_{n}\,z^{n} - x_{1}z - x_{2}z^{2} &= {1 \over 2}\,z^{2}\sum_{n = 1}^{\infty}x_{n}\,z^{n} + {1 \over 2}\,z\sum_{n = 2}^{\infty}x_{n}\,z^{n} \\[3mm]&= {1 \over 2}\,z^{2}\sum_{n = 1}^{\infty}x_{n}\,z^{n} + {1 \over 2}\,z\left(\sum_{n = 1}^{\infty}x_{n}\,z^{n} - x_{1}z\right) \\------------&------------------ \end{align}

$$ \left(1 - {1 \over 2}\,z - {1 \over 2}\,z^{2}\right) \sum_{n = 1}^{\infty}x_{n}\,z^{n} = x_{1}z + x_{2}z^{2} - {1 \over 2}\,x_{1}\,z^{2} $$

\begin{align} ----&---------------------------\\ \sum_{n = 1}^{\infty}x_{n}\,z^{n} &= -\, {2x_{1}z + \left(2x_{2} - x_{1}\right)z^{2} \over z^{2} + z - 2} = -\, {2x_{1}z + \left(2x_{2} - x_{1}\right)z^{2} \over \left(z - 1\right)\left(z + 2\right)} \\[3mm]&= -\,{1 \over 3}\,z \left[% {2x_{1} + \left(2x_{2} - x_{1}\right)z \over z - 1} - {2x_{1} + \left(2x_{2} - x_{1}\right)z \over z + 2}\right] \\[3mm]&= -\,{1 \over 3}\,z \left\{% \left[% 2x_{2} - x_{1} + {x_{1} + 2x_{2} \over z - 1} \right] - \left[% 2x_{2} - x_{1} + {4x_{1} - 4x_{2} \over z + 2} \right] \right\} \\[3mm]&= {1 \over 3}\left(x_{1} + 2x_{2}\right)z\,{1 \over 1 - z} + {2 \over 3}\left(x_{1} - x_{2}\right)z\,{1 \over 1 + z/2} \\[3mm]&= {1 \over 3}\left(x_{1} + 2x_{2}\right)\sum_{n = 1}^{\infty}z^{n} + {2 \over 3}\left(x_{1} - x_{2}\right)\sum_{n = 1}^{\infty} \left(-1\right)^{n - 1}{z^{n} \over 2^{n - 1}} \\[3mm]&= \sum_{n = 1}^{\infty}\left[% {1 \over 3}\left(x_{1} + 2x_{2}\right) + {2 \over 3}\left(x_{1} - x_{2}\right)\,{\left(-1\right)^{n - 1} \over 2^{n - 1}} \right]z^{n} \\----&--------------------------- \end{align}

$$ x_{n} = {1 \over 3}\left(x_{1} + 2x_{2}\right) + {2 \over 3}\left(x_{1} - x_{2}\right)\, {\left(-1\right)^{n - 1} \over 2^{n - 1}}\,, \qquad\qquad n \geq 1 $$

$$ \begin{array}{|c|}\hline\\ \color{#ff0000}{\large\quad% \lim_{n \to \infty}x_{n} \color{#000000}{\ =\ } {1 \over 3}\,x_{1} + {2 \over 3}\,x_{2} \quad} \\ \\ \hline \end{array} $$

${\bf 'EASY\ WAY':}$ Look for a solution $x_{n} \propto \mu^{n}$. We get $\mu = 1$ and $\mu = -1/2$. The general solution is $x_{n} = A\ 1^{n} + B\left(-1/2\right)^{n} = A + B\left(-1\right)^{n}/2^{n}$. With $x_{1} = A - B/2$ and $x_{2} = A + B/4$ we get $A = x_{1}/3 + 2x_{2}/3 = \lim_{n \to \infty}x_{n}$. In addition, $B = 4\left(x1 - x_{2}\right)/3$.

Answer 2

A related problem. To prove convergence, note that

$$ x_n=\frac{1}{2}(x_{n-2}+x_{n-1})\implies x_n-x_{n-1}=\frac{1}{2}(x_{n-2}-x_{n-1}) $$

$$ \implies |x_n-x_{n-1}|=\frac{1}{2}|x_{n-1}-x_{n-2}|<\frac{2}{3}|x_{n-1}-x_{n-2}|. $$

This proves that the sequence is a contraction and hence convergent by the Fixed point theorem. To solve it, then assume the solution $x_n=r^n$ and subs back in the equation and solve the resulting polynomial in $r$.

Answer 3

This sequence is not monotone - for example $x_3 = \frac12 (x_1 + x_2) < x_2$. You can prove convergence using the Cauchy criterion - the distance between consecutive terms halves every term:

$$ |x_n - x_{n-1}| = \frac12 |x_{n-1} - x_{n-2}|,$$ so iterating this equality to obtain $|x_n - x_{n-1}| = 2^{-n+2} |x_2 - x_1|$ we can use a geometric series bound (i.e. use $|r| < 1 \implies \sum_{n=0}^\infty r^n = 1/(1-r)$ as an upper bound) to show the sequence is Cauchy:

$$|x_{n+m} - x_n| \le \sum_{k=1}^m |x_{n+k} - x_{n+k-1}|\le 2^{-n}|x_2 - x_1|\sum_{k=1}^m 2^{-k} \le 2^{-n}|x_2-x_1| \to 0 \textrm{ as } n \to \infty.$$

To find the limit, write the sequence as a geometric series similar to the above:

$$ \begin{align} \lim_{n \to \infty} x_n &= x_1 + \sum_{n=2}^\infty (x_n - x_{n-1}) \\ &= x_1 + (x_2-x_1)\sum_{n=2}^\infty (-2)^{-n+2} \\ &= x_1 + (x_2-x_1)\sum_{n=0}^\infty (-2)^{-(n+2)+2} \\ &= x_1 + (x_2-x_1)\sum_{n=0}^\infty (-2)^{-n} \\ &= x_1 + (x_2-x_1)\frac{1}{1 - (-1/2)} \\ &= \frac{x_1}{3} + \frac{2 x_2}{3}. \end{align} $$

Answer 4

Equivalent question solved of Carothers (Real Analysis) in this spanish blog.