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|Singularity Analysis]], but it applies to a smaller set of functions.

Big O

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

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

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

$|f(z)|\le Mg(z)$

Alternatively, we can say that

$f(z)=O(g(n))$

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

$|f(n)|\le Mg(n)$ for $n\ge N$

Theorem

Theorem due to Wilf.

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

$[z^n](1-z{)}^{\beta }f(z)=\sum _{j=0}^m{f}_j\frac{n^{-\beta -j-1}}{\mathrm{\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:

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

$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:

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

Therefore, for $m=0$:

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

Or, if we want more precision we can set $m=1$:

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

and so on.

Proof

Proof due to Wilf.

We have:

$(1-z{)}^{\beta }f(z)=\sum _{j\ge 0}{f}_j(1-z{)}^{\beta +j}$

and:

$\sum _{j\ge 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 $(1-z{)}^{\beta +m+1}$ from the last sum:

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

Therefore:

$(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. $[z^n]\sum _{j=0}^m{f}_j(1-z{)}^{\beta +j}=\sum _{j=0}^m{f}_j\frac{n^{-\beta -j-1}}{\mathrm{\Gamma }(-\beta -j)}$
2. $[z^n](1-z{)}^{\beta +m+1}g(z)=O(n^{-m-\beta -2})$

Proof of 1

By applying #Lemma 1:

$[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}}{\mathrm{\Gamma }(-\beta -j)}$

Proof of 2

$[z^n](1-z{)}^{\beta +m+1}=O(n^{-m-\beta -2})$ (by #Lemma 1)

$[z^n]g(z)=O({\theta }^n)(0<\theta <1)$ (because, by assumption in the theorem, the radius of convergence $R$ is greater than $1$ and Cauchy's inequality tells us that $[z^n]g(z)=O\left(\frac{1}{R^n}\right)$ and $\frac{1}{R^n}<1$)

$\left|\sum _{0\le k\le \frac{n}{2}}{h}_k{g}_{n-k}\right|\le \{\underset{0\le k\le \frac{n}{2}}{\max }|h_k|\}\left\{\sum _{0\le k\le \frac{n}{2}}A{\theta }^{n-k}\right\}=\max \{B,B{n}^{-m-\beta -2}\}C{\theta }^{\frac{n}{2}}\le D{\theta }^{\frac{n}{2}}=O({\theta }^{\frac{n}{2}})$ (for $A,B,C,D$ constants and assuming that $-m-\beta -2<0$).

$\left|\sum _{\frac{n}{2}\le k\le n}{h}_k{g}_{n-k}\right|\le \{\underset{\frac{n}{2}\le k\le n}{\max }|h_k|\}\left\{\sum _{\frac{n}{2}\le k\le n}A{\theta }^{n-k}\right\}\le B{n}^{-m-\beta -2}=O(n^{-m-\beta -2})$

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

Putting it all together:

$[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 $C{\theta }^{\frac{n}{2}}=o(n^{-m-\beta -2})$ because $\theta <1$.

Lemma 1

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

Proof:

$[z^n](1-z{)}^{\beta }=(\genfrac{}{}{0ex}{}{\beta }{n})(-1{)}^n=(\genfrac{}{}{0ex}{}{n-\beta -1}{n})=\frac{\mathrm{\Gamma }(n-\beta )}{\mathrm{\Gamma }(-\beta )\mathrm{\Gamma }(n+1)}=\frac{1}{\mathrm{\Gamma }(-\beta )(n-\beta {)}^{(\beta +1)}}\sim \frac{n^{-\beta -1}}{\mathrm{\Gamma }(-\beta )}$

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

Szegő's theorem

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

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

$f(z)=\sum _{v\ge 0}{c}_v^{(k)}(1-z{e}^{-i\varphi k}{)}^{{\alpha }_k+v{\beta }_k}(k=1,2,\cdots ,r\text{ and }{\beta }_k>0)$

Then we have the asymptotic series

$[z^n]f(z)=\sum _{v\ge 0}\sum _{k=1}^r{c}_v^{(k)}(\genfrac{}{}{0ex}{}{{\alpha }_k+v{\beta }_k}{n})(-e^{i\varphi k}{)}^n$

References

• Template:Cite book
• Template:Cite book