# 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!

-
The solution is wrong (or you copied it incorrectly). Try looking at $x_{n+1}-x_n$. – David Mar 26 '14 at 23:58
Solve the recurrence relation and then try to find the limit. – Mhenni Benghorbal Mar 26 '14 at 23:59
@David Ah I see! $x_{n+1} - x_n$ yields the term on the RHS. – joe Mar 27 '14 at 0:02

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

-
This is the most procedural method, +1. – Nameless Mar 27 '14 at 0:56

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.

-

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.

-