How to find the limit of the sequence $x_n =\frac{1}{2}[x_{n-1}+x_{n-2}]$, if $x_0=0$ and $x_1=1$? The formula is only applicable on values for $n\geq 2$.
I know that the sequence is monotonic with a lower bound at $\frac 1 2$, but I am unsure how to find the supremum of the sequence.
EDIT: $x_2 = \frac 1 2, x_3 = \frac 3 4, x_4 = \frac 5 8$. Does that mean that this sequence is only recursive and not monotonic?
 A: You have: $$\begin{bmatrix}x_n\\x_{n-1}\end{bmatrix}=\begin{bmatrix}1/2&1/2\\1&0\end{bmatrix}\begin{bmatrix}x_{n-1}\\x_{n-2}\end{bmatrix}$$
And given the initial condition, 
$$\begin{align}
\begin{bmatrix}x_n\\x_{n-1}\end{bmatrix}
&=\begin{bmatrix}1/2&1/2\\1&0\end{bmatrix}^{n-1}\begin{bmatrix}1\\0\end{bmatrix}\\
\end{align}$$
Diagonalize (or rather, convert to Jordan Normal form) the matrix and you can give an explicit formula for $x_n$, from which the limit is clear.
A: $$2x_n=x_{n-1}+x_{n-2}$$
Lets assume it's geometric, $x_n=q^n$
$$2q^n=q^{n-1}+q^{n-2}$$
$$2q^2-q-1=0$$
$q_1=1$ and $q_2=-0.5$
Lets find the linear combination
$$x_n=\alpha q_1^n+\beta q_2^n$$
 that satisifies $x_1$ and $x_0$
$$\alpha q_1^0 +\beta q_2^0 = 0$$
$$\alpha q_1^1 +\beta q_2^1 = 1$$
When substituting $q_1$ and $q_2$ and $\beta=-\alpha$ we get:
$$\alpha +\frac{\alpha}{2} = 1$$
$$\alpha=\frac{2}{3}$$
And the solution is
$$x_n=\frac{2}{3}-\frac{2}{3}(-\frac{1}{2})^n$$
A: We prove that $x_n = \dfrac{2}{3} - \dfrac{2}{3}\cdot \left(-\dfrac{1}{2}\right)^n$, and from this the limit is $\dfrac{2}{3}$, but this can be done by induction on $n\geq 0$.
A: We first will multiply by 2 to yield $$2x_n=x_{n-1} + x_{n-2}$$
adding $x_{n-1}$ yields $$2x_n + x_{n_1}=2x_{n-1} + x_{n-2}$$
we now have a function in form $f(x_n,x_n-1) = f(x_{n-1},f{x_n-2})$,and so we can apply this formula as much as we want, bring the variables lower and lower, because this formula essentially just says $f(x_n,x_n-1) = f(x_k-1,x_k-2)$, and  this means $$f(x_n,x_n-1) = f(x_1,x_0) \iff 2x_n + x_{n-1} = 2 \cdot 1 + 0 = 2$$
as n tends to infinity, x_n = x_{n-1}, so $$2x_n + x_{n-1} = 2 \implies 2x_\infty + x_\infty = 2 \iff 3x_\infty = 2 \iff x_\infty = \frac{2}{3}$$
A: The function isn't monotone at all. However, consider what $x_n$ is actually doing, in base 4; you can show inductively that if $n$ is odd then $x_n = 0.22\dots23_4$, while if $n$ is even then $x_n = 0.22\dots 2_4$, where the number of quart-digits is $\lfloor \frac{n}{2} \rfloor$.
