Calculate a limit of recursive sequence Prove that infinite recursive sequence 
has limit and calculate it.
$x_{1}=0, x_{2}=1$
$x_{n+2}=\frac{1}{2}(x_{n}+x_{n+1})$
I've tried to separate it to even and odd partial series and it looks like one of them is increasing and another is decreasing. But I can't prove that they are increasing and decreasing, because I don't know how to express $x_{n}$ from a recurrence relation. 
What should I do for example with $x_{n+1}$ when I work with the even partial series? 
And that is why I can't calculate the limits too, because I need to express somehow $x_{n}$.
 A: $\mathbf x_n = \begin{bmatrix} x_{n+1}\\x_{n}\end{bmatrix}$
$\mathbf x_n = \begin{bmatrix} \frac 12 &\frac 12\\1&0\end{bmatrix}\mathbf x_{n-1}$
$\mathbf x_n = \begin{bmatrix} \frac 12 &\frac 12\\1&0\end{bmatrix}^n\mathbf x_{0}$
$\begin{bmatrix} \frac 12 &\frac 12\\1&0\end{bmatrix} = P D P^{-1}$ 
$\begin{bmatrix} \frac 12 &\frac 12\\1&0\end{bmatrix} = P D^n P^{-1}$
$\begin{bmatrix} \frac 12 &\frac 12\\1&0\end{bmatrix} =\frac 13\begin{bmatrix} 1 &-1\\1&2\end{bmatrix}\begin{bmatrix} 1 &0\\0&-\frac 12\end{bmatrix}\begin{bmatrix} 2 &1\\-1&1\end{bmatrix}$
The limit exists if one of the eigenvalues equals 1 and absolute value of the other eigenvalue is less than 1, which is indeed the case.
$\lim_\limits{n\to\infty} \mathbf x_n = \frac 13\begin{bmatrix} 1 &-1\\1&2\end{bmatrix}\begin{bmatrix} 1 &0\\0&0\end{bmatrix}\begin{bmatrix} 2 &1\\-1&1\end{bmatrix}\begin{bmatrix} 1\\0\end{bmatrix}=\begin{bmatrix} \frac 23\\\frac23\end{bmatrix}$
A: This is "easily" solvable if you interpret the meaning of this recurrence formula!
$x_{n+2} = \frac12(x_{n+1} + x_n)$ is the same as saying that $x_{n+2}$ is the average of the last two terms! Because $x_0 = 0$ and $x_1 = 1$ we can see that $x_2 = \frac12$, $x_3 = \frac34$, $x_4 = \frac38$ and so on and so forth.
We can now see that each step we add/subtract a power of $\frac12$. If you separate the sums where you add powers of $\frac12$ from the one where you subtract powers of $\frac12$ you can compute each sum individually and then add everything together to find your answer.
You should arrive at $\frac23$.
A: Notice $|x_n-x_{n-1}|=|\frac{1}{2}(x_{n-1}-x_{n-2})|=\dots= |\frac{1}{2^{n-1}} (x_1-x_0)|=\frac{1}{2^{n-1}}$, this approaches to $0$ as $n$ grows, the sequence is then cauchy and converges in $\mathbb{R}$.
A: Your hunches are indeed correct. For instance,


*

*a) Show by induction that if $n$ is even, then $x_n > x_{n-1}$.

*b) Use a) to show that if $n$ is even, then $x_n < x_{n-2}$.

A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{x_{1} = 0\,,\quad x_{2} = 1}$.

\begin{align}
\sum_{n = 1}^{\infty}x_{n + 2}\,\, z^{n} & =
{1 \over 2}\sum_{n = 1}^{\infty}x_{n}z^{n} +
{1 \over 2}\sum_{n = 1}^{\infty}x_{n + 1}\,\,z^{n}
\\[5mm]
\implies 2\sum_{n = 3}^{\infty}x_{n}z^{n} & =
z^{2}\sum_{n = 1}^{\infty}x_{n}z^{n} +
z\sum_{n = 2}^{\infty}x_{n}\,\,z^{n}
\\[5mm]
\implies 2\sum_{n = 1}^{\infty}x_{n}z^{n} - 2x_{1}z - 2\, x_{2}\, z^{2} & =
z^{2}\sum_{n = 1}^{\infty}x_{n}z^{n} +
z\sum_{n = 1}^{\infty}x_{n}\,\,z^{n} - z\,x_{1}z
\end{align}

\begin{align}
\sum_{n = 1}^{\infty}x_{n}z^{n} & =
-2\,{z^{2} \over z^{2} + z - 2} =
-2\,{z^{2} \over \pars{z + 2}\pars{z - 1}} =
-\,{2 \over 3}\,\pars{{z^{2} \over z -1 } - {z^{2} \over z + 2}}
\\[5mm] & =
-\,{2 \over 3}\,\braces{\bracks{{1 \over z -1} + 2 + \pars{z - 1}} -
\bracks{{4 \over z + 2} - 4 + \pars{z + 2}}}
\\[5mm] & =
{2 \over 3}\,{1 \over 1 - z} + {4 \over 3}\,{1 \over 1 + z/2} - 2 =
{2 \over 3}\sum_{n = 1}^{\infty}z^{n} +
{4 \over 3}\sum_{n = 1}^{\infty}\pars{-\,{z \over 2}}^{n}
\\[5mm] & =
\sum_{n = 1}^{\infty}\bracks{{2 \over 3} +
2\,\pars{-1}^{n}\,{2^{1 - n} \over 3}}z^{n}
\end{align}

$$
\bbx{x_{n} = {2 \over 3}\bracks{1 + {\pars{-1}^{n} \over 2^{n - 1}}}}
$$
A: As each term is the average of the last two terms, the step size is halved each time and with an alternating sign step size, i.e.
difference between consecutive terms is $1, -\frac12, \frac 14, -\frac 18,\cdots$ which is a geometric progression (GP) with $r=-\frac 12$. As the first term is zero, the limit of the original series of the sum to infinity of the series of differences (the GP), as given by 
$$\frac 1{1-(-\frac 12)}=\color{red}{\frac 23}$$
