Problem to understand a recurrence relation 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? 
 A: 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$.
A: 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.$$
