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

• It just shows that as $x_0=y_0$ and $x_1=y_1$, then by recurrence $x_n=y_n$ for all $n$.
– user65203
Commented Oct 30, 2014 at 9:45
• But why is $x_0=y_0$ and $x_1=y_1$? Commented Oct 30, 2014 at 9:45
• Because the equations were solved for $A$ and$B$ so that it is precisely the case. (Think that $y_0=A+B$ and $y_1=A\alpha+B\beta$.)
– user65203
Commented Oct 30, 2014 at 9:47
• Could you please explain that? I think about that very long but do not understand this. ;( Commented Oct 30, 2014 at 9:48
• Does my answer help ?
– user65203
Commented Oct 30, 2014 at 10:02

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

• Great, thank you. And how can I prove that $x_n=y_n$ for all $n$? Commented Oct 30, 2014 at 10:01
• @mathfemi By induction. It is already true for $n=0,1$. For $n>1$, use the reccurence relation in the inductive step.
– 5xum
Commented Oct 30, 2014 at 10:03
• You mean I have to show by induction that $a(y_{n+1}-x_{n+1})+b(y_n-x_n)+c(y_{n-1}-x_{n-1})=0$? Commented Oct 30, 2014 at 10:14
• @mathfemi No, you have to show by induction that $y_n = x_n$.
– 5xum
Commented Oct 30, 2014 at 10:15
• Ok the induction is very short: Suppose it is shown for $n$, now do the inductive step $n\mapsto n+1$, then $ay_{n+1}=-by_n-cy_{n-1}=-bx_n-cx_{n-1}=ax_{n+1}$ so $y_{n+1}=x_{n+1}$. Thats it. Commented Oct 30, 2014 at 10:22

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

• Why is $a(y_{n+1}-x_{n+1})+b(y_n-x_n)+c(y_{n-1}-x_{n-1})=0$ for all n and why does from this follow by induction that $x_n=y_n$ for all $n$? Commented Oct 30, 2014 at 10:09
• By subtraction of the two recurrences in $x$ and $y$, and because $y_n-x_n=0$.
– user65203
Commented Oct 30, 2014 at 10:38
• But that $x_n=y_n$ is to show... Commented Oct 30, 2014 at 10:40