Proof of convergence of a recursive sequence How do I prove that 
$x_{n+2}=\frac{1}{2} \cdot (x_n + x_{n+1})$
$x_1=1$
$x_2=2$
is convergent?
 A: Given:
$$x_{n+2} = \frac{1}{2}(x_n + x_{n+1}) $$ 
It follows that if 
$$ x_n \le x_{n+1} $$ 
$$ x_n \le x_{n+2} \le x_{n+1} $$ 
Or if:
$$ x_n \ge x_{n+1} $$ 
Then:
$$ x_n \ge x_{n+2} \ge x_{n+1} $$ 
We note that equality only occurs if 
$$ x_n = x_{n+1}$$ 
Thus consider the difference 
$$ |x_{n+1} - x_n| = r $$
It then follows that 
$$ |x_{n+2} - x_{n+1}| = \frac{r}{2}$$ 
(Verify this for the case of $x_{n+2} > x_{n+1}$ vs. $x_{n+2} < x_{n+1}$)
Thus 
$$ |x_{n+k} - x_{n+k-1}| = \frac{r}{2^{k-1}} $$
(Verify this by induction)
Therefore as k approaches infinity
$$ |x_{n+k} - x_{n+k-1}| \rightarrow 0 $$
A: Hint: how does $x_{n+2} - x_{n+1}$ relate to $x_{n+1} - x_n$?
A: Let $$y_n \equiv x_n - \frac{x_0-x_1}{2}$$
Then it is easy to see that 
$$y_0 = \frac{x_0-x_1}{2} \\
y_1 = \frac{x_1-x_0}{2} = - y_0
$$
and with a wee bit of algebra, the relation 
$x_{n+2}= \frac{1}{2}(x_n+x_{n+1}$ becomes
$$y_{n+2}= \frac{1}{2}(y_n+y_{n+1})$$
But because $y_1 = -y_0$ the behavior of $y_n$ is easy to see:
$$
y_0 = y_0\\y_1 = -y_0
y_2 = 0 \\
y_3 = -\frac{1}{2} y_0 \\
y_4 = -\frac{1}{4} y_0 \\
y_5 = -\frac{3}{8} y_0 \\
y_6 = -\frac{5}{16} y_0 \\
y_7 = -\frac{11}{32} y_0 \\
$$
and in general, it is easy to show by induction that for $n > 3$
$$y_n = -\left( \frac{2}{3} + \frac{(-1)^{n-1} }{3\cdot 2^{n-2}} \right) y_0 $$
the limit of $y_n$ is always $\frac{2}{3}$
Then $x_n$ is obtained by adding back the average of $x_0$ and $x_1$ so it too has a finite limit.
A: As pointed by @RobertIsrael,
$$x_{n+2}-x_{n+1}=-\frac12(x_{n+1}-x_n).$$
The first order differences decrease geometrically so that their sum converges.
A: If $x_{n+1}=x_n$ then $x_{n+2}=x_{n+1}$ and by induction the sequence is constant, thus convergent.
If $x_{n+1}\ne x_n$ and w.l.o.g. $x_{n+1} > x_n$ then $x_{n+1} > x_{n+2} > x_n$. This makes each pair of adjacent terms closer than previous pair:
$$|x_{n+2}-x_{n+1}|<|x_{n+1}-x_n|$$
Additionally, each term is a midpoint of the range defined by two preceding terms, so each pair distance is a half of the previous pair distance:
$$|x_{n+2}-x_{n+1}|= \frac 12 |x_{n+1}-x_n| = \frac 1{2^n} |x_2-x_1|$$
so the sequence is Cauchy, which implies (in $\Bbb R$) it's convergent.
You can also note that the subsequences of every other term are monotone: $(x_{2i+1})_{i\in\Bbb N}$ is increasing and bounded by $x_2$, while $(x_{2i})_{i\in\Bbb N}$ is decreasing and bounded by $x_1$, so they are both convergent (however that alone does not prove $(x_n)$ is convergent).
EDIT
Let $d = x_2 - x_1$, then:
$\begin{align}
x_{2n+1} & = x_1 + d\sum_{i=1}^n\frac 1{2^{2i-1}} \\
x_{2n+2} & = x_2 - d\sum_{i=1}^n\frac 1{2^{2i}}
\end{align}$
For $n=0$ both sums are empty and expressions result in $x_1$ and $x_2$, respectively.
For $n\to\infty$ both sums are geometric series with ratio $\tfrac14$, so:
$\lim_{n\to\infty} x_{2n+1} = x_1 + d\frac {\frac 12}{1-\frac 14} = x_1 + \frac23d$
$\lim_{n\to\infty} x_{2n+2} = x_2 - d\frac {\frac 14}{1-\frac 14} = x_2 - \frac13d$
so they are equal, thus
$\lim_{n\to\infty} x_n = \frac13 x_1 + \frac23 x_2$
