3

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?

mathfemi
  • 2,631

2 Answers2

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

5xum
  • 123,496
  • 6
  • 128
  • 204
  • Great, thank you. And how can I prove that $x_n=y_n$ for all $n$? – mathfemi Oct 30 '14 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 Oct 30 '14 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$? – mathfemi Oct 30 '14 at 10:14
  • @mathfemi No, you have to show by induction that $y_n = x_n$. – 5xum Oct 30 '14 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. – mathfemi Oct 30 '14 at 10:22
  • But I do not understand why $a(y_{n+1}-x_{n+1})+b(y_n-x_n)+c(y_{n-1}-x_{n-1})=0$ for all $n$ and for what I need this. Because this only holds if $x_n=y_n$ for all $n$ but this is to show. – mathfemi Oct 30 '14 at 10:30
  • I think I do not need this at all. – mathfemi Oct 30 '14 at 10:43
  • @mathfemi The way you proved it, you really don't need it. What the textbook did was prove that $x_n - y_n = 0$ for all $n$ by proving that $x_0-y_0 = 0$ and $x_1-y_1$ and then using induction to prove that $x_{n+1} - y_{n+1} = 0$. But your method is just as valid. – 5xum Oct 30 '14 at 11:02
1

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