Problem to understand a recurrence relation

Question

In Norris, Markov chains, I found the following:

[...] a recurrence relation of the form $$ ax_{n+1}+bx_n+cx_{n-1}=0 $$ where $a$ and $c$ were both non-zero. Let us try a solution of the form $x_n=\lambda^n$; then $a\lambda^2+b\lambda+c=0$. Denote by $\alpha$ and $\beta$ the roots of this quadratic. Then $$ y_n=A\alpha^n+B\beta^n $$ is a solution.

Up to here everything is clear to me.

But I do not understand the following:

If $\alpha\neq\beta$ then we can solve the equations $$ x_0=A+B,~~~~~x_1=A\alpha+B\beta $$ such that $y_0=x_0$ and $y_1=x_1$; but $$ a(y_{n+1}-x_{n+1})+b(y_n-x_n)+c(y_{n-1}-x_{n-1})=0 $$ for all $n$, so by induction $y_n=x_n$ for all $n$.

Could you please explain me this passage?

Answer 1

The point is that in step $1$, you define $$y_n = A \alpha^n + B \beta ^n$$ and you "notice" that for any values of $A,B$, you know that $y_n$ will satisfy the reccurence equation.

In the second part, you set $A$ and $B$ to such values that $y_0=x_0$ and $y_1=x_1$. That is, you set $A$ and $B$ to satisfy the equations $A+B=x_0$ and $A\alpha + B\beta = x_1$, meaning that $$y_0 = A\alpha^0 + B\beta^0 = A + B = x_0$$ and $$y_1=A\alpha^1 + B\beta^1 = A\alpha + B\beta = x_1$$

As a result you know that $y_n$ is a sequence that satisfies:

$$y_0=x_0\\ y_1=x_1\\ \forall n\in\mathbb N: ay_{n+1} + by_n + cy_{n-1} = 0$$

and using these three equations, you can prove that $x_n=y_n$ for all values of $n$, meaning that the solution to the reccurence relation is $x_n = A\alpha^n + B\beta^n$, where $\alpha, \beta$ are the roots of your polynomial ($a\lambda^2 + b\lambda + c$) and $A, B$ are such that $A+B=x_0$ and $A\alpha + B\beta = x_1$.

Answer 2

The unknown sequence is such that $$ax_{n+1}+bx_n+cx_{n-1}=0.$$

We found a general sequence (with two free parameters $A$ and $B$), $y_n=A\alpha^n+B\beta^n$ that is a solution this recurrence. Indeed, after simplification, $$ay_{n+1}+by_n+cy_{n-1}=a(A\alpha^{n+1}+B\beta^{n+1})+b(A\alpha^n+B\beta^n)+c(A\alpha^{n-1}+B\beta^{n-1})=(a\alpha^2+b\alpha+c)A\alpha^{n-1}+(a\beta^2+b\beta+c)B\beta^{n-1}=0.$$ Now, if we choose $A$ and $B$ in such a way that $y_0=x_0$ and $y_1=x_1$, by recurrence this will extend to $y_n=x_n$, because the differences $y_n-x_n$ also verify the recurrence and are identically $0$:

$$a(y_{n+1}-x_{n+1})+b(y_{n}-x_{n})+c(y_{n-1}-x_{n-1})=0,$$ with $$y_0-x_0=0\text{ and }x_1-y_1=0.$$