# 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.

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.

-

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)\frac{1}{1 - (-2)} \\ &= \frac{x_1}{3} + \frac{2 x_2}{3}. \end{align}

-
How do you come up with the geometric series? Why that? –  Desperate Fluffy Sep 23 '13 at 6:01
@DesperateFluffy: it's the standard way to show that contractions like this converge. In general the Cauchy criterion can be written as $\sum_{k=n}^\infty |x_{k+1} - x_{k}| \to 0$ as $n \to \infty$ if you want a systematic path to follow. As for finding the limit, the fact that the geometric series came up in the convergence proof is a big hint. Any time you have a sequence defined by a recurrence of differences like this, writing it as a series is likely to help. –  Anthony Carapetis Sep 23 '13 at 6:10

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

-

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

-

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

-