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.

Big O

We will make use of the "Big O" notation.

${\displaystyle f(z)=O(g(z))}$ as ${\displaystyle z\to \zeta }$

which means there exists positive real numbers ${\displaystyle M,\delta }$ such that if ${\displaystyle 0<|z-\zeta |<\delta }$:

${\displaystyle |f(z)|\leq Mg(z)}$

Alternatively, we can say that

${\displaystyle f(z)=O(g(n))}$

for positive integer ${\displaystyle n}$, meaning there exists a positive real number ${\displaystyle M}$ and positive integer ${\displaystyle N}$ such that:

${\displaystyle |f(n)|\leq Mg(n)}$ for ${\displaystyle n\geq N}$

Theorem

Theorem due to Wilf^[1].

If we have a function ${\displaystyle (1-z)^{\beta }f(z)}$ where ${\displaystyle \beta \notin \{0,1,2,\ldots \}}$ where ${\displaystyle f(z)}$ has a radius of convergence greater than ${\displaystyle 1}$ and an expansion near 1 of ${\displaystyle \sum _{j\geq 0}f_{j}(1-z)^{j}}$, then:

${\displaystyle [z^{n}](1-z)^{\beta }f(z)=\sum _{j=0}^{m}f_{j}{\frac {n^{-\beta -j-1}}{\Gamma (-\beta -j)}}+O(n^{-m-\beta -2})}$

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

${\displaystyle {\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}=(1-z)^{-{\frac {1}{2}}}e^{-z/2-z^{2}/4}}$

${\displaystyle e^{-z/2-z^{2}/4}}$ is a complete function, so its radius of convergence is greater than 1.

Near 1 it can be expanded using the Taylor series:

${\displaystyle e^{-z/2-z^{2}/4}=e^{-3/4}+e^{-3/4}(1-z)+\cdots }$

Therefore, for ${\displaystyle m=0}$:

${\displaystyle [z^{n}]{\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}=e^{-3/4}{\frac {n^{-{\frac {1}{2}}}}{\Gamma ({\frac {1}{2}})}}+O(n^{-{\frac {3}{2}}})}$

Or, if we want more precision we can set ${\displaystyle m=1}$:

${\displaystyle [z^{n}]{\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}=e^{-3/4}{\frac {n^{-{\frac {1}{2}}}}{\Gamma ({\frac {1}{2}})}}+e^{-3/4}{\frac {n^{-{\frac {3}{2}}}}{\Gamma (-{\frac {1}{2}})}}+O(n^{-{\frac {5}{2}}})}$

and so on.

Proof

Proof due to Wilf^[3].

We have:

${\displaystyle (1-z)^{\beta }f(z)=\sum _{j\geq 0}f_{j}(1-z)^{\beta +j}}$

and:

${\displaystyle \sum _{j\geq 0}f_{j}(1-z)^{\beta +j}=\sum _{j=0}^{m}f_{j}(1-z)^{\beta +j}+\sum _{j>m}f_{j}(1-z)^{\beta +j}}$

By factoring out ${\displaystyle (1-z)^{\beta +m+1}}$ from the last sum:

${\displaystyle \sum _{j>m}f_{j}(1-z)^{\beta +j}=(1-z)^{\beta +m+1}g(z)}$

Therefore:

${\displaystyle (1-z)^{\beta }f(z)=\sum _{j=0}^{m}f_{j}(1-z)^{\beta +j}+(1-z)^{\beta +m+1}g(z)}$

We have to prove that:

1. ${\displaystyle [z^{n}]\sum _{j=0}^{m}f_{j}(1-z)^{\beta +j}=\sum _{j=0}^{m}f_{j}{\frac {n^{-\beta -j-1}}{\Gamma (-\beta -j)}}}$
2. ${\displaystyle [z^{n}](1-z)^{\beta +m+1}g(z)=O(n^{-m-\beta -2})}$

Szegő's theorem

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

If ${\displaystyle f(z)}$ is analytic in ${\displaystyle |z|<1}$, has a finite number of singularities ${\displaystyle e^{i\phi _{1}},e^{i\phi _{2}},\cdots ,e^{i\phi _{r}}}$ on the unit circle ${\displaystyle |z|=1}$ and in the neighbourhood of each singularity has the expansion

${\displaystyle f(z)=\sum _{v\geq 0}c_{v}^{(k)}(1-ze^{-i\phi k})^{\alpha _{k}+v\beta _{k}}\quad (k=1,2,\cdots ,r{\text{ and }}\beta _{k}>0)}$

Then we have the asymptotic series

${\displaystyle [z^{n}]f(z)=\sum _{v\geq 0}\sum _{k=1}^{r}c_{v}^{(k)}{\binom {\alpha _{k}+v\beta _{k}}{n}}(-e^{i\phi k})^{n}}$

Notes

References

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