Author: Eiko

Tags: Asymptotics, Generating Functions, Residue Theorem, Mathematics, Complex Analysis

Time: 2024-09-10 15:32:22 - 2024-09-10 15:32:22 (UTC)

Use Residue Theorem To Compute The Asymptotics Of Generating Functions

Let’s say we have a generating function

$$f(z)=\sum _{n\ge 0}{a}_n{z}^n$$

and we want to know about the asymptotics of the coefficients $a_n$.

The forgotten formula

In complex analysis we have a very simple formula that computes the $n$-th coefficient as a contour integral around the origin

$$a_n=\frac{1}{2\pi i}\oint \frac{f(z)}{z^{n+1}}dz$$

but we rarely use it because the integral is very hard to compute and does not seem helpful, it was only used to prove some vanishing results, besides that people have forgotten about it.

So it in fact comes to a surprise to me that we can get the asymptotics of $a_n$ very easily without crazy techniques (well, not that crazy) like the saddle point method.

Basic Principle

For a large class of functions with poles as their singularities, the integral actually allows us to see the asymptotics instantly by capturing the size of poles and their residues. But we have to shift the focus from our original function $f(z)$ to $\frac{f(z)}{z^{n+1}}$.

Example

For example let’s consider the asymptotic of $f(z)=\frac{1}{2-e^z}$. Consider a small circle that surrounds the origin, the integral captures the pole at $0$ of $\frac{f(z)}{z^{n+1}}$ which is just $a_n$.

Now let’s enlarge our circle, before it encounters any singularities, the integral should stay the same. Keep enlarging until it just contain the pole $z_0=\log 2$ with smallest absolute value, with residue $-\frac{1}{2}$. Other poles have larger absolute values. This gives

$$\frac{1}{2\pi i}\int \frac{f(z)}{z^{n+1}}dz=a_n+{\mathrm{Res}}_{z_0}\frac{f(z)}{z^{n+1}}.$$

Here a key observation is that the integral is controlled by $O(\underset{|z|=r}{sup}|f(z)|r^{-n})=O(r^{-n})$, where the $sup|f|$ part does not depend on $n$, this immediately gives us the asymptotic

$$a_n=-{\mathrm{Res}}_{z_0}\frac{f(z)}{z^{n+1}}+O(r^{-n})$$

where $r>|z_0|$ can be any number smaller than other poles, in this case $f(z)=\frac{1}{2-e^z}$ we have

$$a_n=\frac{1}{2(\log 2{)}^{n+1}}+O(|\log 2+2\pi i{|}^{-(1-\epsilon )n}).$$

Series Expansion

In fact this method allows us to expand more terms using the other poles and get better approximations. For rational functions this sum is finite and exact.

Try for yourself!

• What is the asymptotic of $\frac{1}{(z-1{)}^m}$ ? How many poles are there, and why is this an exact formula?

• Try to figure out the asymptotic of $\frac{1}{1-\sin z}$. Note that the smallest rule is not a simple pole.