Finding the limit of a recurrence relation?

Question

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!

Answer 1

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.

Answer 2

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

Answer 3

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.