Analytic Combinatorics/Darboux Method

Introduction Darboux's method is one way of estimating the coefficients of generating functions involving roots. It is easier than Singularity Analysis, but it applies to a smaller set of functions. Theorem Theorem due to WilfWilf 2006, pp. 194.. If we have a function where where has a radius of convergence greater than and an expansion near 1 of , then: Example The theorem is a bit abstract, so I will show an example of how you might use it before going into the proof. Taking an example from WilfWilf 2006, pp. 195.: is a complete function, so its radius of convergence is greater than 1. Near 1 it can be expanded using the Taylor series: Therefore, for : Or, if we want more precision we can set : and so on. Proof Proof due to WilfWilf 2006, pp. 193-195.. We have: and: By factoring out from the last sum: Therefore: We have to prove that: Proof of 1 By applying #Lemma 1: Proof of 2 (by #Lemma 1) (because, by assumption in the theorem, the radius of convergence is greater than and Cauchy's inequality tells us that and ) (for constants and assuming that ). because because . Putting it all together: because w:Big_O_notation#Little-o_notation. because w:Big_O_notation#Orders_of_common_functions.. Lemma 1 Proof: w:Falling_and_rising_factorials#Properties. where is the rising factorial. Szegő's theorem We can apply a similar theorem to functions with multiple singularities. From WilfWilf 2006, pp. 196. and SzegőSzegő 1975, pp. 207-208.. If is analytic in , has a finite number of singularities on the unit circle and in the neighbourhood of each singularity has the expansion Then we have the asymptotic series Notes References Szegő Gabor Orthogonal Polynomials 4th American Mathematical Society 1975 Wilf Herbert S. Generatingfunctionology 3rd A K Peters, Ltd 2006 https://www2.math.upenn.edu/~wilf/gfology2.pdf