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?

$\endgroup$
0

3 Answers 3

6
$\begingroup$

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

$\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.

$\endgroup$
0
$\begingroup$

see also

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

$\endgroup$

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.