# 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.

## 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})}$

### Proof of 1

By applying #Lemma 1:

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

### Proof of 2

${\displaystyle [z^{n}](1-z)^{\beta +m+1}=O(n^{-m-\beta -2})}$ (by #Lemma 1)
${\displaystyle [z^{n}]g(z)=O(\theta ^{n})\quad (0<\theta <1)}$ (because, by assumption in the theorem, the radius of convergence ${\displaystyle R}$ is greater than ${\displaystyle 1}$ and Cauchy's inequality tells us that ${\displaystyle [z^{n}]g(z)=O\left({\frac {1}{R^{n}}}\right)}$ and ${\displaystyle {\frac {1}{R^{n}}}<1}$)
${\displaystyle \left|\sum _{0\leq k\leq {\frac {n}{2}}}h_{k}g_{n-k}\right|\leq \left\{\max _{0\leq k\leq {\frac {n}{2}}}|h_{k}|\right\}\left\{\sum _{0\leq k\leq {\frac {n}{2}}}A\theta ^{n-k}\right\}=\max\{B,Bn^{-m-\beta -2}\}C\theta ^{\frac {n}{2}}\leq D\theta ^{\frac {n}{2}}=O(\theta ^{\frac {n}{2}})}$ (for ${\displaystyle A,B,C,D}$ constants and assuming that ${\displaystyle -m-\beta -2<0}$).
${\displaystyle \left|\sum _{{\frac {n}{2}}\leq k\leq n}h_{k}g_{n-k}\right|\leq \left\{\max _{{\frac {n}{2}}\leq k\leq n}|h_{k}|\right\}\left\{\sum _{{\frac {n}{2}}\leq k\leq n}A\theta ^{n-k}\right\}\leq Bn^{-m-\beta -2}=O(n^{-m-\beta -2})}$

because ${\displaystyle \left\{\sum _{{\frac {n}{2}}\leq k\leq n}A\theta ^{n-k}\right\}\leq C\max _{{\frac {n}{2}}\leq k\leq n}\theta ^{n-k}=C}$ because ${\displaystyle \theta ^{2}\leq \theta ^{1}\leq \theta ^{0}=1}$.

Putting it all together:

${\displaystyle [z^{n}](1-z)^{\beta +m+1}g(z)=O(\theta ^{\frac {n}{2}})+O(n^{-m-\beta -2})=O(n^{-m-\beta -2})}$

because ${\displaystyle C\theta ^{\frac {n}{2}}=o(n^{-m-\beta -2})}$[4] because ${\displaystyle \theta <1}$[5].

### Lemma 1

${\displaystyle [z^{n}](1-z)^{\beta }\sim {\frac {n^{-\beta -1}}{\Gamma (-\beta )}}}$

Proof:

${\displaystyle [z^{n}](1-z)^{\beta }={\binom {\beta }{n}}(-1)^{n}={\binom {n-\beta -1}{n}}={\frac {\Gamma (n-\beta )}{\Gamma (-\beta )\Gamma (n+1)}}={\frac {1}{\Gamma (-\beta )(n-\beta )^{(\beta +1)}}}\sim {\frac {n^{-\beta -1}}{\Gamma (-\beta )}}}$[6]

where ${\displaystyle x^{(n)}}$ is the rising factorial.

## 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

1. Wilf 2006, pp. 194.
2. Wilf 2006, pp. 195.
3. Wilf 2006, pp. 193-195.
4. Wilf 2006, pp. 196.
5. Szegő 1975, pp. 207-208.

## References

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