For a given ordinary generating function $f(x)=a_0+a_1x+...$, are there any methods to determine the growth rate of its coefficients based on that of $f$ ? In particular if we are given the extra information that $$\lim\limits_{a \to 1^-}\frac{1-a}{a}*\log f(a)=\frac{\pi^2}{12}$$ Can we strengthen our asymptotic estimate?


Determining the asymptotic growth of the coefficients of a generating function is essentially the entire subject of Analytic Combinatorics, on which see the 810-page book by Flajolet and Sedgewick available online.

The basic setup is this: for a large class of generating functions $G(z) = g_0 + g_1z + g_2z^2 + \dots$, we can show that the coefficients satisfy $$g_n = [z^n]G(z) = A^n \theta(n),$$ where $A^n$ is the exponential rate of growth and $\theta(n)$ is a subexponential factor.

Here, the exponential rate of growth $A = \lim \sup |g_n|^{1/n}$ is determined by the location of the singularities of the function $G(z)$: under nice conditions, it is simply the reciprocal of the radius of convergence ($A = 1/R$).

When $A > 1$, for many purposes it's sufficient to determine $A$, but when $A = 1$ it's not very informative.

The subexponential factor $\theta(n)$ is determined by the "nature" of the singularities (in a way that's made clear in the book).

  • 1
    $\begingroup$ Thank you. One cannot be displeased with a 810-page answer. I will look into the book :) $\endgroup$ – Elie Bergman Feb 21 '14 at 13:29
  • $\begingroup$ Can anything be said for the case when the radius of convergence is infinite, i..e for entire generating functions? $\endgroup$ – Michael Jun 18 '15 at 10:13
  • $\begingroup$ @Michael Yes, their Chapter VIII on the saddle-point method covers such generating functions. $\endgroup$ – ShreevatsaR Jun 18 '15 at 15:20

By the Cauchy-Hadamard theorem, $\limsup\sqrt[n]{|a_n|}=1/R$. If the lim sup is in reality a lim, and even better, if the limit of the quotient formula exists, then the asymptotic growth rate is about the reciprocal of the distance of the origin to the closest singularity of $f$.

  • $\begingroup$ "the asymptotic growth rate is about the reciprocal of the distance of the origin to the closest singularity of f" So the asymptotic growth rate is a constant in this case? Do you mean a_n approx (1/R)^n? $\endgroup$ – Elie Bergman Feb 20 '14 at 12:43
  • $\begingroup$ If the radius of convergence is finite and if it can be computed as an actual limit. Of course one can construct examples where the coefficients come alternatingly from different sequences, for instance $f(x)=\frac1{4-x^2}+\frac{x}{9-x^2}$. Then you would have to measure the growth by observing the maximum value among the first n coefficients. $\endgroup$ – Dr. Lutz Lehmann Feb 20 '14 at 12:49
  • $\begingroup$ Ok if the radius of convergence = 1, Seemingly this method won't tell us a lot though? $\endgroup$ – Elie Bergman Feb 20 '14 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.