Analytic Combinatorics/Darboux Method

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Introduction[edit | edit source]

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.

Big O[edit | edit source]

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[edit | edit source]

Theorem due to Wilf[1].

If we have a function where where has a radius of convergence greater than and an expansion near 1 of , then:

Example[edit | edit source]

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[2]:

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[edit | edit source]

Proof due to Wilf[3].

We have:


By factoring out from the last sum:


We have to prove that:

Proof of 1[edit | edit source]

By applying #Lemma 1:

Proof of 2[edit | edit source]

(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 [4] because [5].

Lemma 1[edit | edit source]



where is the rising factorial.

Szegő's theorem[edit | edit source]

We can apply a similar theorem to functions with multiple singularities. From Wilf[7] and Szegő[8].

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[edit | edit source]

  1. Wilf 2006, pp. 194.
  2. Wilf 2006, pp. 195.
  3. Wilf 2006, pp. 193-195.
  4. w:Big_O_notation#Little-o_notation.
  5. w:Big_O_notation#Orders_of_common_functions.
  6. w:Falling_and_rising_factorials#Properties.
  7. Wilf 2006, pp. 196.
  8. Szegő 1975, pp. 207-208.

References[edit | edit source]

  • Szegő, Gabor (1975). Orthogonal Polynomials (4th ed.). American Mathematical Society.
  • Wilf, Herbert S. (2006). Generatingfunctionology (PDF) (3rd ed.). A K Peters, Ltd.