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.
as ![{\displaystyle z\to \zeta }](https://wikimedia.org/api/rest_v1/media/math/render/svg/50032c154a78fdba13db964c979e24d77fbfb53f)
which means there exists positive real numbers
such that if
:
![{\displaystyle |f(z)|\leq Mg(z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec56201addbbc9cb4a600f879c8aa6ef0789fcb0)
Alternatively, we can say that
![{\displaystyle f(z)=O(g(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a25f51c7d95e6b8400b0594986424260f02ab557)
for positive integer
, meaning there exists a positive real number
and positive integer
such that:
for ![{\displaystyle n\geq N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b67a4f8e2ce89617f08316bfdcc6f33887b5629)
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:
![{\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})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/59ebdc6be74262b8d77bdc7959a202c9dfe0a11e)
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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c63d9e0a566c082b3be02d9937e4fe6c678c86d)
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 }](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cec8999d250e4c58fe8dcf5f2eda9d5c0d524c6)
Therefore, for
:
![{\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}}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67929786694dc34d2b2587d973c308113bfea710)
Or, if we want more precision we can set
:
![{\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}}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/556f802bc6d6e34857e42ecd73d73e6ad493b35b)
and so on.
Proof due to Wilf[3].
We have:
![{\displaystyle (1-z)^{\beta }f(z)=\sum _{j\geq 0}f_{j}(1-z)^{\beta +j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/496fdf34a6cca07797fd139badfd38adddf774e5)
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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afce74fe8cacd8dca0c7a13c3a6552f32c742f9c)
By factoring out
from the last sum:
![{\displaystyle \sum _{j>m}f_{j}(1-z)^{\beta +j}=(1-z)^{\beta +m+1}g(z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ee80267bfdc7cce69655730b1530e7f745ce6c4)
Therefore:
![{\displaystyle (1-z)^{\beta }f(z)=\sum _{j=0}^{m}f_{j}(1-z)^{\beta +j}+(1-z)^{\beta +m+1}g(z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da40be20dac0aa837b8a86e873ff651619cea1a3)
We have to prove that:
![{\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)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b1f9171542889b980efe6622a4e7095b75538dd)
![{\displaystyle [z^{n}](1-z)^{\beta +m+1}g(z)=O(n^{-m-\beta -2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65970044c651e53385c2128cfa00b035293d6359)
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)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5406986cc8fb43fa3cda8d450e1d1385501b2c7c)
(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
).
![{\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})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/151e93a3967bd7e87a4609f44eb386a004498a9d)
because
because
.
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})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93149f1ff8a68187862626453c13bc53b85ca102)
because
[4] because
[5].
![{\displaystyle [z^{n}](1-z)^{\beta }\sim {\frac {n^{-\beta -1}}{\Gamma (-\beta )}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47f81026f6b6c905f991a59232ef98385b494d74)
Proof:
[6]
where
is the rising factorial.
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
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa2d65b5162a7323a0d53f480ea05e403d958abe)
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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/860c6df152d2f0833d88ec0c874a1876a36335c1)
- Szegő, Gabor (1975). Orthogonal Polynomials (4th ed.). American Mathematical Society.
- Wilf, Herbert S. (2006). Generatingfunctionology (PDF) (3rd ed.). A K Peters, Ltd.