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