Finding limit of a contractive sequence

Question

There is a sequence which I proved to be a contractive sequence, I have problem in finding its limit. If $x_1 < x_2$ are arbitrary real numbers and $\displaystyle x_n = \frac{x_{n-1} + x_{n-2}}{2}$ for $n>2$. Find limit of $x_n$.

Answer 1

This is just a simple example of a second order homogenous linear recurrence relation with constant coefficients. There is a general formula for these: first start by finding the roots of the characteristic polynomial. This polynomial is obtained by substituting $a_n=x^n$ on the recurrence relation. After simplifying, one gets: $$x^2=\frac{x+1}{2} \rightarrow x=1,-\frac{1}{2}$$ Then the expression of $x_n$ is simply: $x_n=A(r_1)^n+B(r_2)^n=A(1)^n+B(-\frac{1}{2})^n$, because the two roots of the characteristic polynomial are different. You can then solve for $A$ and $B$ with the values of $x_1$ and $x_2$, as:

$$ \begin{cases} x_1=A-\frac{1}{2}B \\ x_2=A+\frac{1}{4}B\\ \end{cases} $$

For more on this try reading this.

EDIT: Hope it is clearer now. I encourage you to read about the math behind this on the link above.