# What is the asymptotic behavior of a linear recurrence relation (equiv: rational g.f.)?

The question sounds simple: find the roots of the characteristic equation, take the one with the largest absolute value, and find its coefficient. Repeated roots do not substantially complicate matters.

But what about two roots with equal absolute value? Is there any way to determine the asymptotic behavior of such a sequence?

For example, $$a_n = 4a_{n-2} - 6a_{n-4} + 4a_{n-6} - a_{n-8}$$

has characteristic equation $x^8-4x^6+6x^4-4x^2+1=(x-1)^4(x+1)^4$ and so it has two roots of equal magnitude and multiplicity. In this case the asymptotic behavior should be $|a(n)|=O(n^3)$, and finding the corresponding polynomials from the initial values should allow a lower bound as well as coefficients. In this case the sequence is a quasipolynomial, so there's no interference between the values. But can there be? Are there sequences with nontrivial† characteristic polynomial, e.g., $(x-2)^4(x+2)^4(x-1)^3$ that, because of cancellation, yields a sequence that is actually $O(n^2)$?

† That is, leading coefficient not zero -- the characteristic equation is of the lowest degree for the particular starting values, or equivalently the g.f. is written with gcd(numerator, denominator) = 1. (No writing $a_n=4a_{n-2}$ if $a_n=2a_{n-1}$, for example.)

-
Are you talking about the asymptotic behavior of the characteristic equation or of the sequence $a_n$? How is having a leading coefficient not zero "nontrivial"? –  anon Sep 6 '11 at 19:43
@anon: Of the sequence. I'm not sure why you question my use of nontrivial; to me, calling the sequence $a_n=2n$ a quadratic equation with recurrence $a_n=3a_{n-1}-3a_{n-2}+a_{n-3}$ (essentially, calling it $a_n=0n^2+2n+0$) is a bit fake, since it's more easily expressed as $a_n=2a_{n-1}-a_{n-2}$. But if you have a better term, please suggest it! –  Charles Sep 7 '11 at 2:31
Okay, so I think you're asking "under what conditions does a linear recurrence relation with characteristic polynomial of degree $k$ have a solution $f(n)$ which is a polynomial of degree $<k$?" You confused me by saying an 11th-degree ch. polynomial in $x$ could be $O(x^2)$ (when I think you meant the actual sequence was $O(n^2)$ - this is very different.) As for when two roots of maximum modulus are opposite signs, the asymptotic behavior depends on their multiplicities and the initial conditions. –  anon Sep 7 '11 at 4:01
@anon: You're right on my lax use of terminology and variables. On the rest... that's not what I meant, no. If the characteristic polynomial is $x-2$ then the behavior of the sequence is never polynomial at all, unless the characteristic polynomial is not minimal/reduced/nontrivial. That would correspond to, e.g., $a_n=2^n.$ –  Charles Sep 7 '11 at 4:12
Each smallest singularity (pole in this case) $\rho$ of the generating function produces a term $c_\rho n^{m-1} \rho^{-n}$ in the asymptotic formula, where $c_\rho$ is a constant determined by the initial conditions and $m$ is the multiplicity of the pole. With more than one smallest singularity, such terms are added together. It is not possible for them to cancel each other out, since any set of distinct infinite sequences of the form $1,x,x^2,\ldots$ is linearly independent. To read more about this, check out "Darboux's method", for example in the book generatingfunctionology of Herb Wilf (available free online).