recursive sequence Given $0<a<b$, $\forall n$ define $x_n$ as $x_1=a$, $x_2=b$, $x_{n+2}=\frac{x_n+x_{n+1}}{2}$. Show that $(x_n)$ converges and find the limit.
In order to prove the convergence, I claim that $|x_{n+2}-x_{n+1}|\le\lambda|x_{n+1}-x_{n}|$, $0<\lambda<1$. In fact, $|x_{n+2}-x_{n+1}|\le|\frac{x_{n+1}+x{n}}{2}-x_{n+1}|=\frac{1}{2}|x_{n+1}-x_n|$.But I have no idea about how to find the limit. I'd like to get some help.
 A: The recurrence can be rewritten as 
$$x_{n+2}-x_{n+1}=\frac{1}{2}(x_n-x_{n+1}).$$
Let $\delta_{i}=x_{i+1}-x_i$. Then 
$$\delta_{i+1}=-\frac{1}{2}\delta_i,$$
and therefore 
$$\delta_{i}=
\left(\frac{-1}{2}\right)^{i-1}\delta_1.$$
Add up the $x_{i+1}-x_i$, from $i=1$ to $n$. By cancellation, we get $x_{n+1}-x_1$. But we also get
$$\sum_{i=1}^n \left(\frac{-1}{2}\right)^{i-1}\delta_1,$$
which is equal to $\frac{2}{3}\left(1-\frac{(-1)^n}{2^n}\right)\delta_1$. 
We conclude that
$$x_{n+1}=a+\frac{2}{3}\left(1-\frac{(-1)^n}{2^n}\right)(b-a).$$
Let $n\to\infty$. We find that $x_{n+1}\to a+\frac{2}{3}(b-a)=\frac{1}{3}(a+2b)$. 
A: Define $A(z) = \displaystyle\sum_{n=1}^{\infty} x_n z^n.$ 
$$A(z) = x_1z + x_2 z^2 + x_3 z^3 + \cdots = x_1 z + x_2 z^2 + \frac{ x_1+x_2}{2} z^3 + \frac{x_2+x_3}{2} z^4 + \cdots.$$
Subtracting the first two terms of the RHS and multiplying by $2/z$ gives:
$$\frac{2(A(z)-x_1 z - x_2z^2)}{z} = (x_1+x_2) z^2+ (x_2+x_3)z^3 = zA(z) + A(z)-x_1z$$
so solving that for $A(z)$ and performing partial fractions: $$A(z) = \frac{(x_1-2x_2)z^2-2x_1 z}{(z+2)(z-1)}= z\left( \frac{\alpha}{z+2} + \frac{\beta}{z-1}\right).$$
where $\alpha = 4(x_1-x_2)/3$ and $\beta = (-x_1-2x_2)/3.$ Now it shouldn't be too hard to expand $A(z)$ around $z=0,$ off the coefficients and take the limit.

If you've seen some of the theory of linear recurrences, from $\displaystyle x_{n+2} = \frac{x_{n+1}+x_n}{2}$ we get the characteristic polynomial $\lambda^2-\lambda/2-1/2$ which has roots $\lambda=1,-1/2.$ Then $x_n = \alpha + \beta (-1/2)^n$ for some $\alpha,\beta$ which can be found by plugging in the initial conditions $x_1=a, x_2=b$ and solving the simultaneous equations. Then $x_n \to \alpha.$
A: Simpler: For $A(z) = \sum_{n \ge 0} x_{n + 1} z^n$ the recurrence directly translates into
$$
\frac{A(z) - x_1 - x_2 z}{z^2} 
   = \frac{1}{2} \frac{A(z) - x_1}{z} + \frac{A(z)}{2}
$$
This gives:
$$
A(z) = \frac{2 a + (2 b - a) z}{2 - z - z^2}
     = \frac{2 a - 2 b}{3} \frac{1}{1 + z / 2} + \frac{a + 2 b}{3} \frac{1}{1 - z}
$$
These are two geometric series:
$$
x_n = \frac{2 a - 2 b}{3} 2^{-n - 1} + \frac{a + 2 b}{3}
    = \frac{a - b}{3} 2^{-n} + \frac{a + 2 b}{3}
$$
Thus $x_n \rightarrow (a + 2 b) / 3$.
