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$?

Question

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?

Answer 1

$$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$$

Answer 2

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$.

Answer 3

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$.

Answer 4

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.