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.
We will make use of the "Big O" notation.
which means there exists positive real numbers such that if :
Alternatively, we can say that
for positive integer , meaning there exists a positive real number and positive integer such that:
Theorem due to Wilf.
If we have a function where where has a radius of convergence greater than and an expansion near 1 of , then:
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 Wilf:
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 due to Wilf.
By factoring out from the last sum:
We have to prove that:
By applying #Lemma 1:
- (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  because .
where is the rising factorial.
We can apply a similar theorem to functions with multiple singularities. From Wilf and Szegő.
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
- Szegő, Gabor (1975). Orthogonal Polynomials (4th ed.). American Mathematical Society.
- Wilf, Herbert S. (2006). Generatingfunctionology (PDF) (3rd ed.). A K Peters, Ltd.