2
$\begingroup$

I have a generating function that has a closed form like $1/(\log(z-a)+b)$ and I would like to get asymptotics for the size of the coefficients of it.

I was going to use the methods in Chapter 5 of Wilf's Generatingfunctionology using the singularities. However, there is a branch point of log(z-a) at z=a. In Section 5.3 of Wilf's book, he discusses how to handle algebraic singularities (e.g., the branch point at $z=1$ of $\sqrt{z-1}$, but I have not been able to find anything about how to handle branch points when the function is transcendental (like the log function that I am considering).

Are there any known techniques for handling the branch points of such functions? If so, would anyone have references they could provide on this, please?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
6
$\begingroup$

See Chapter VI of Flajolet and Sedgewick, Analytic combinatorics, Cambridge 2009.

Improve this answer
$\endgroup$
2
$\begingroup$

That method described in the book by Flajolet & Sedgewick is implemented in a Maple function "equivalent" of the Algolib library that you can download from http://algo.inria.fr/libraries/ . The code is not maintained any more, but still works in your example:

equivalent(1/(log(a-z)+b),z,n) assuming a>0;

$$\frac{a^{-n}}{n\log^2n}\left(1+O\left(\frac1{\log n}\right)\right),$$ (this is a slightly simplified form of the actual output). Note that compared with your initial question, I've changed log(z-a) into log(a-z) which makes more sense for a generating function.

Improve this answer
$\endgroup$
0
$\begingroup$

see also

P. Flajolet & A. Odlyzko, "Singularity analysis of generating functions" Siam. J. Disc. Math. 3 (1990) 216--240

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .