Limit of sequence in which each term is defined by the average of preceding two terms

We have a sequence of numbers $x_n$ determined by the equality

$$x_n = \frac{x_{n-1} + x_{n-2}}{2}$$

The first and zeroth term are $x_1$ and $x_0$.The following limit must be expressed in terms of $x_0$ and $x_1$ $$\lim_{n\rightarrow\infty} x_n $$

The options are:

A)$\frac{x_0 + 2x_1}{3}$ B)$\frac{2x_0 + 2x_1}{3}$

C)$\frac{2x_0 + 3x_1}{3}$ D)$\frac{2x_0 - 3x_1}{3}$

Since it was a multiple choice exam I plugged $x_0=1$ and $x_1=1$. Which means that all terms of this sequence is $1$,i.e, $$x_n=1, n\in \mathbb{N} $$

From this I concluded that option A was correct.I could not find any way to solve this one hence I resorted to this trick. What is the actual method to find the sequence's limit?

$$2x_n = x_{n-1} + x_{n-2}$$

$$2x_2 = x_{1} + x_{0}\\ 2x_3 = x_{2} + x_{1}\\ 2x_4 = x_{3} + x_{2}\\ 2x_5 = x_{4} + x_{3}\\ ...\\ 2x_n = x_{n-1} + x_{n-2}$$

Now sum every equation and get

$$2x_n+x_{n-1}=2x_1+x_0$$

Supposing that $x_n$ has a limit $L$ then making $n\to \infty$ we get:

$$2L+L=2x_1+x_0\to L=\frac{2x_1+x_0}{3}$$

Yet another trick: you can write the recurrence in matrix form: $$ \left(\begin{array}{c} x_n\\ x_{n-1} \end{array} \right) = \left(\begin{array}{cc} 1/2 & 1/2\\ 1 & 0\\ \end{array} \right) \left(\begin{array}{c} x_{n-1}\\ x_{n-2} \end{array} \right). $$ Then, $$ \left(\begin{array}{c} x_n\\ x_{n-1} \end{array} \right) = \left(\begin{array}{cc} 1/2 & 1/2\\ 1 & 0\\ \end{array} \right)^{n-1} \left(\begin{array}{c} x_1\\ x_0 \end{array} \right). $$ Diagonalizing/converting the matrix to the Jordan form, you can find a closed form for the sequence.

First, notice that you can rewrite the recurrence relation as $$2x_{n+2}-x_{n+1}-x_n=0,\quad n\geq 0.$$ Now the key point is that this recurrence relation is linear, and thus if $(y_n)_{n\geq 0}$ and $(z_n)_{n\geq 0}$ satisfy this relation, then for any $\alpha,\beta\in \Bbb R$, $(\alpha y_n+\beta z_n)_{n\geq 0}$ will also satisfy it. So we can try to express $(x_n)$ as a linear combination of simpler sequences $(y_n)$ and $(z_n)$. An example of simple sequence would be a geometric sequence $y_n=r^n$ for some $r$. Can we find a sequence of this form satisfying the recurrence relation? $r$ would have to be such that $$2r^{n+2}-r^{n+1}-r^n=r^{n}(2r^2-r-1)=0,\quad n\geq 0,$$thus it is enough that $$2r^2-r-1=0.$$ This will hold if and only if $r\in \left\{1,\frac{-1}{2}\right\}$.

Thus we know that any sequence of the form

$$\alpha +\beta \left(\frac{-1}{2}\right)^n$$ satisfies our recurrence relation. Then it suffices to check that the first two term are the same, and all the others will follow. Thus you need to find $\alpha,\beta$ such that $$\left\{ \begin{array}{}\alpha+\beta & = & x_0\\ \alpha-\frac{\beta}{2} & = & x_1.\end{array} \right. $$

This is a simple linear system, whose solution is given by $\alpha=\frac{x_0+2x_1}{3}$ and $\beta=\frac{2x_0-2x_1}{3}$.

Thus the $n$-th term must be given by $$x_n=\frac{x_0+2x_1}{3}+\frac{(2x_0-2x_1)(-1)^{n}}{3\cdot 2^n}$$ and thus $\lim_{n\to \infty }x_n = \frac{x_0+2x_1}{3}$.

This method works for a large variety of cases; in fact, it can be applied to give a formula for $x_n$ for any linear recurrence relations (there are some difficulties if the corresponding polynomial equation has multiple roots, because you don't get enough geometric sequences, but you can find other solutions in those case). For example, you can apply the same method to the Fibonacci sequence, and it gives you the Binet formula (you can find more details in the answers to this question).

Here's yet another way to look at the problem, that might not lead directly to a proof, but might give intuitive insight into the sequence.

Note that from $x_0$, we go $x_1-x_0$ up to $x_1$, then $\frac12(x_1-x_0)$ down to $x_2$, then $\frac14(x_1-x_0)$ up to $x_3$, etc. You might be able to prove this by induction, but might not want to. If $x_0=0$ and $x_1=1$, one can put this in a picture: ($A=(0,x_0)$, $B=(1,x_1)$, ...)

We conclude that, since the jump from $x_0$ to $x_1$ can really be seen a a jump of $1=(-1/2)^0$ relative to $x_0$:

$$x_n = x_0 + (x_1-x_0)\sum_{i=0}^{n-1} \left(-\frac12\right)^i$$

Then the limit for $n \rightarrow \infty$ is:

$$\lim_{n\rightarrow\infty} x_n = x_0 + (x_1-x_0)\sum_{i=0}^\infty \left(-\frac12\right)^i = x_0 + (x_1-x_0)\frac1{1+\frac12}$$

by the geometric series (since $\lvert-\frac12\rvert < 1$). Then this is equal to:

$$\begin{align*} x_0 + (x_1-x_0)\frac1{1+\frac12} &= x_0 + \frac23(x_1-x_0) = \frac{3x_0+2x_1-2x_0}3 \\ &= \frac{x_0 + 2x_1}3. \end{align*}$$