0

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.

Chilote
  • 4,239
  • According to Wikipedia ... What is the exact wording there? It does not necessarily hold true as posted e.g. that's not the general solution if $a=\pm 2$, or if $B=0$ the 2nd inequality is not required etc. – dxiv Jul 08 '18 at 22:58
  • It says: The recurrence is stable, meaning that the iterates converge asymptotically to a fixed value, if and only if the eigenvalues (i.e., the roots of the characteristic equation), whether real or complex, are all less than unity in absolute value. https://en.wikipedia.org/wiki/Recurrence_relation#Relationship_to_difference_equations_narrowly_defined – Chilote Jul 08 '18 at 23:12
  • 1
    That's a bit different from what you asked here. There is no mention of a general form there, for one thing. Also, that's meant to be read as "the recurrence is stable *for all initial conditions* if ...". And, it needs further qualifications, for example $x_{n+1}=x_{n}$ is constant, thus stable, even though the characteristic polynomial has $1$ as a root. – dxiv Jul 08 '18 at 23:20
  • 1
    Hint: suppose $|u| \gt |v|$, then write $Au^n+Bv^n = u^n\left(A+B(v/u)^n\right)$. – dxiv Jul 08 '18 at 23:22
  • 2
    The exercise seems to be rather futile, because the product of $\frac{a+\sqrt{a^2-4}}2$ and $\frac{a-\sqrt{a^2-4}}2$ is $1$. – random Jul 08 '18 at 23:34
  • Thanks, @dxiv your hint helped me to see that: If $\lim Au^n+Bv^n=0$ and $|u|\neq|v|$ then $|u|<1$ and $|v|<1$. But what happens in general when $|u|=|v|$ and the linear recurrence is of order 2? ($x_{n+1}=x_n$ is not of order 2). – Chilote Jul 09 '18 at 00:42
  • @dxiv the sequence is not convergent! I followed a similar process to the one you mention and had some help. See my comments and answer of https://math.stackexchange.com/q/2845083 – Chilote Jul 09 '18 at 02:31
  • @Chilote You should still edit the question to (a) eliminate the case $a = \pm 2$, (b) clarify whether $a,x_0,x_1$ are real or complex, and (c) whether you ask about convergence vs. convergence to $0$. – dxiv Jul 09 '18 at 02:54
  • @dxiv all done! – Chilote Jul 09 '18 at 03:06

1 Answers1

0

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.

dxiv
  • 76,497