# Show a certain sequence converges

Let sequence $(x_n)$ be recursively defined as: $x_1=0, x_2=1, x_{n+2}=\frac{1}{2}(x_{n+1}+x_n)$
What I need to do is show that $(x_n)$ converges, not necessarily to show that it converges to $\frac{2}{3}$, just prove that it is convergent. I don't quite know how to start this prove, can the convergence tests for series also be used for sequences?

For equations of this type, you could use the Z-transform approach. That is, assume that the answer takes the form $${x_n} = {Z^n}$$replacing this into your equation gives $$2{Z^2} - Z - 1 = 0$$which is true for $$Z = \left\{ \begin{array}{l}1\\ - \frac{1}{2}\end{array} \right.$$so that by linearity, the answer to your problem is $${x_n} = {c_1} + {\left( { - \frac{1}{2}} \right)^n}{c_2}$$Note that since the magnitude of the roots of the characteristic equation are less than or equal to one, the sequence converges independent from the initial conditions (which give the constants in our answer). Hope it helps ;)

You have that

$$|x_{n+2}-x_{n+1}|=\left|\frac{x_{n+1}}{2}+\frac{x_n}{2}-x_{n+1}\right|=\frac{1}{2}|x_{n+1}-x_n|.$$

Using induct|x_{n+k}-x_{n+1}|ion, we get

$$|x_{n+2}-x_{n+1}|=\frac{1}{2^{n+1}}|x_1-x_0|=\frac{1}{2^{n+1}}.$$

Now, for any $k\ge 2,$ it is

$$|x_{n+k}-x_{n+1}|\le \sum_{i=1}^{k-1}|x_{n+i+1}-x_{n+i}|=\sum_{i=1}^{k-1}\frac{1}{2^{n+i}}=\frac{1}{2^n}-\frac{1}{2^{n+k-1}}.$$ This shows that it is a Cauchy sequence and so it must be convergent.