# 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.)

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

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