Finding the limit of a recurrence relation? I have a sequence defined by the relation $$x_{n+1} = \alpha x_n + (1-\alpha)x_{n-1}$$ for $n\geq 1$, and I want to find the limit in terms of $\alpha , x_0,x_1$. I tried to do this by setting up a matrix equation, but that didn't work out, so I took a peek at the solution. It said that I first needed to realize that $x_n-x_{n-1} = (\alpha - 1)(x_n-x_{n-1})$. I've tried playing around with the initial relation algebraically, but I'm stuck as to how to get this second relation below.
Any pointers would be greatly appreciated!
 A: The characteristic equation is
$$r^2-\alpha r+(\alpha-1)=0,\qquad \Delta=\alpha^2-4\alpha+4=(\alpha-2)^2$$
and its roots are
$$r_{1}=\alpha-1\quad;\quad r_2=1$$
hence if $\alpha\ne2$:
$$x_n=a(\alpha-1)^n+b$$
and if $\alpha=2$:
$$x_n=an+b$$
and $a$ and $b$ are determined using $x_0$ and $x_1$.
A: Subtract $x_n$ from both sides, to get $$x_{n+1}-x_n=(\alpha-1)x_n+(1-\alpha)x_{n-1}$$
Then collect to get $$x_{n+1}-x_n=(\alpha-1)(x_n-x_{n-1})$$
It's not exactly the hint, the index is off by one.  However the conclusion is the same -- if $0< \alpha <1$, then the limit of $(\alpha-1)^n$ is zero.
A: Use generating functions, no creativity involved... write:
$$
x_{n + 2} = \alpha x_{n + 1} + (1 - \alpha) x_n
$$
Define $X(z) = \sum_{n \ge 0} x_n z^n$, multiply the recurrence by $z^n$, add over $n \ge 0$, recognize some sums:
$$
\frac{X(z) - x_0 - x_1 z}{z^2}
  = \alpha \frac{X(z) - x_0}{z} + (1 - \alpha) X(z)
$$
Solve and write as partial fractions:
$$
X(z) = \frac{x_1 + (1 - \alpha) x_0}{2 - \alpha} \cdot \frac{1}{1 - z}
         - \frac{x_1 - x_0}{2 - \alpha} \cdot \frac{1}{1 + (1 - \alpha) z}
$$
This is just two geometric series:
$$
x_n
  = \frac{x_1 + (1 - \alpha) x_0}{2 - \alpha}
      - \frac{x_1 - x_0}{2 - \alpha} \cdot (-1)^n (1 - \alpha)^n
$$
As presumably $0 < \alpha < 1$, this tells you it converges and what the limit is.
