Proof of the stability of a linear recurrence relation

416 Views Asked by At

Consider the linear recurrence relation $x_{n+2}=ax_{n+1}-x_n$, where $a\in\mathbb{C}\setminus\{-2,2\}$ and $x_n\in\mathbb{C}$ for all $n\in\mathbb{N}$. The general solution for this is

$$x_n=A\left(\frac{a+\sqrt{a^2-4}}{2}\right)^n+B\left(\frac{a-\sqrt{a^2-4}}{2}\right)^n$$ for $A,B\in\mathbb{C}$.

According to Wikipedia, $\lim_{n\to\infty} x_n=0$ for all $x_1,x_2\in\mathbb{C}$ if and only if $$\left|\frac{a+\sqrt{a^2-4}}{2}\right|<1\mbox{ and }\left|\frac{a-\sqrt{a^2-4}}{2}\right|<1.$$ In that case, of course $\lim_{n\to\infty} x_n=0$.

Question: How do I prove that equivalence? The implication $\Leftarrow$ is clear but how do we prove the implication $\Rightarrow$?

Comment: If you know that this proof is in a book, paper, notes, etc, and you do not want to spend the time typing it you can just cite it and once I check it I will consider it as an answer.

1

There are 1 best solutions below

0
On BEST ANSWER

Let $\,x_n=Au^n+bv^n\,$ where $\,u = \frac{a+\sqrt{a^2-4}}{2}\,$ and $\,v = \frac{a-\sqrt{a^2-4}}{2}\,$ with $\,u \ne v\,$ because $\,a \ne \pm 2\,$.

For $\,x_n\,$ to converge regardless of the choice of $\,A,B\,$, it is necessary that it converges for $\,A=1\,$, $\, B=0\,$, in which case $\,x_n = u^n\,$. The geometric progression $\,u^n=|u|^ne^{i\,n\arg u}\,$ is known to converge iff $\,|u| \lt 1\,$ or $\,|u|=1 \land \arg u = 0$ $\iff u = 1\,$. A symmetric argument applies to $\,v\,$.

Since $\,u \ne v\,$, it follows that:

  • $x_n\,$ converges iff both $\,|u|,|v| \lt 1\,$, or if one of them, say $\,v\,$, has magnitude $\,|v| \lt 1\,$ and the other one is $\,u=1\,$;

  • $x_n\,$ converges to $\,0\,$ iff both $\,|u|, |v| \lt 1\,$.

In the given case here, $\,|u| \cdot |v|=1\,$ so neither of the above is attainable, and therefore $x_n$ diverges.