If $x_12$, 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.

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