0

Consider the following linear recurrence relation: $x_1=1, x_2= a, x_{n+2}=ax_{n+1}-x_n$.

The only solution for this is

$$x_n=\frac{1}{\sqrt{a^2-4}}\left(\frac{a+\sqrt{a^2-4}}{2}\right)^n+\frac{1}{\sqrt{a^2-4}}\left(\frac{a-\sqrt{a^2-4}}{2}\right)^n$$

Question: If there any $a\in\mathbb{C}$ for which $\lim_{n\to\infty}x_n=0$?

According to Wikipedia, "a linear 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."

For this particular recurrence relation, the eigenvalues are $r_1=\frac{a+\sqrt{a^2-4}}{2}$ and $r_2=\frac{a-\sqrt{a^2-4}}{2}$ with $a^2\neq 4$.

It is impossible to have $|r_1|<1$ and $|r_2|<1$ simultaneously because that would imply that $1=|r_1r_2|<1$. But I am not sure whether this implies that $\lim_{n\to\infty}x_n\neq0$ for all $a\in\mathbb{C}$, because Wikipedia does not provide any citation of the result quoted above.

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
  • Since one of the roots has absolute value less than $1$, for large $n$ your terms approach $C\times r^n$, where $r$ is the root with absolute value greater than $1$, and $C$ is not $0$. Thus the terms can't go to $0$. – lulu Jul 08 '18 at 23:52
  • how do you know that one of the roots has an absolute value less than 1? – Chilote Jul 09 '18 at 00:12
  • Because the product of their absolute values is $1$ and they are not both $1$. – lulu Jul 09 '18 at 01:01
  • Actually, both have the same absolute value because both are roots of the same quadratic polynomial, so $r_1=\overline{r_2}$. – Chilote Jul 09 '18 at 01:06
  • If, say, $a=3$ then the roots are about $4.79$ and $.209$ But, yes, I was assuming $a>2$ and real. Though for most complex values for $a$ it is still the case that one root has norm greater than $1$ and the other has norm less than $1$. – lulu Jul 09 '18 at 01:08
  • Thanks, @lulu for showing me the light! I was plain wrong. – Chilote Jul 09 '18 at 01:11
  • If $r_1\in\mathbb{R}$ or $r_2\in\mathbb{R}$, then ${r_1,r_2}\subset\mathbb{R}$, because they are roots of the same quadratic polynomial. Then $a=r_1+r_2\in\mathbb{R}$. Hence $\sqrt{a^2-4}>0$ so $r_2<r_1$. Since $|r_1r_2|=1$, we have that $|r_1|=|r_2|=1$ if and only if $r_2=-1$ and $r_1=1$ if and only if a=0 (contradiction). Hence $|r_1|\neq1\neq|r_2|$ and therefore one root has absolute value $>1$ and the other $<1$ so $\lim x_n\neq 0$ when at least one of the roots is in $\mathbb{R}$ – Chilote Jul 09 '18 at 01:48

1 Answers1

1

What Wikipedia means to say is that ALL the solutions of a linear recurrence have limit zero if and only if all the roots of the characteristic equation have module strictly lower than one. It doesn't mean that a particular solution of a linear recurrence can't have limit zero even if this condition is not realized. For example, the null sequence is always a solution of a linear recurrence, even when every other solution is not bounded.

Here, all you have to say is that either one (and only one) of the roots has a module greater than one (for $r_1r_2=1$), and then with your general expression, $(x_n)$ can't be bounded, or both have module $1$.

In the later case, $r_1=e^{i\theta}$ and $r_2=\overline{r_1}=e^{-i\theta}$, then $x_n=\frac{2}{\sqrt{a^2-4}}\cos(n\theta)$ doesn't have limit $0$ (which is not completely evident to prove, but easier with $\cos(n\theta)$ than with $\sin(n\theta)$).

Nicolas FRANCOIS
  • 4,846