Generating Functions

3.1 Generating Functions of Sequences

The ordinary generating function (OGF) of a sequence of real numbers \((a_k)_{k \ge 0}\) is the power series \[ \begin{aligned} A(x) := \sum_{k \ge 0} a_k x^k. \end{aligned} \]

Consider a \(2 \times n\) rectangle. We want to tile it using \(1 \times 2\) dominoes, placed either horizontally or vertically, without overlap and without leaving any square uncovered. Let \(a_n\) denote the number of such tilings. Considering the leftmost tile gives \(a_n=a_{n-1}+a_{n-2}\) for \(n\ge2\). The first two values are:

\[ \begin{aligned} a_0 = 1, \quad a_1 = 1. \end{aligned} \]

What is the value of \(a_n\) for general \(n\)?

\[ \begin{aligned} A(x) = \frac{1}{1 - x - x^2}. \end{aligned} \]

Then we can decompose \(A(x)\) into partial fractions:

\[ \begin{aligned} A(x) = \frac{\alpha}{1 - \varphi x} + \frac{\beta}{1 - \psi x} \end{aligned} \]

where \(\varphi=(1+\sqrt5)/2\), \(\psi=(1-\sqrt5)/2\), and \((\alpha, \beta)\) is the solution to \(\alpha(1 - \psi x) + \beta(1 - \varphi x) = 1\):

\[ \begin{aligned} \alpha = \frac{\sqrt{5} + 1}{2\sqrt{5}}, \quad \beta = \frac{\sqrt{5} - 1}{2\sqrt{5}}. \end{aligned} \]

Expanding each term as a geometric series gives

\[ \begin{aligned} A(x) = \sum_{n \ge 0} \alpha \varphi^n x^n + \sum_{n \ge 0} \beta \psi^n x^n = \sum_{n \ge 0} (\alpha \varphi^n + \beta \psi^n) x^n. \end{aligned} \]

Therefore, we obtain that the number of domino tilings of a \(2 \times n\) rectangle is

\[ \begin{aligned} a_n = \alpha \varphi^n + \beta \psi^n = \frac{\sqrt{5} + 1}{2\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^n + \frac{\sqrt{5} - 1}{2\sqrt{5}} \left( \frac{1 - \sqrt{5}}{2} \right)^n. \end{aligned} \]

Let \(a_n\) be the number of ways to fully parenthesize the following expression:

\[ \begin{aligned} x_1 + x_2 + \dots + x_n. \end{aligned} \]

Here, “fully parenthesized” means that every addition operation is enclosed in parentheses. Equivalently, \(a_n\) is the number of ways to evaluate the expression using only binary additions.

\[ \begin{aligned} a_1 = 1, \quad a_n = \sum_{k=1}^{n-1} a_k a_{n-k} \quad \text{for all } n \ge 2. \end{aligned} \]

This can be further simplified as the following quadratic equation:

\[ \begin{aligned} A(x)^2 - A(x) + x = 0. \end{aligned} \]

Solving this quadratic equation gives

\[ \begin{aligned} A(x) = \frac{1 \pm \sqrt{1 - 4x}}{2}. \end{aligned} \]

There are two possible solutions, but since \(A(0) = \sum_{n \ge 1} a_n 0^n = 0\), we must choose the minus sign:

\[ \begin{aligned} A(x) = \frac{1 - \sqrt{1 - 4x}}{2}. \end{aligned} \]

we get

\[ \begin{aligned} a_n = -\frac{1}{2}(-4)^n \cdot \frac{(-1)^{n-1}}{2^{2n-1}} \cdot \frac{(2n-2)!}{(n-1)!n!} = \frac{(2n-2)!}{(n-1)!n!}. \end{aligned} \]

In combinatorics, Catalan numbers, named after the French mathematician Eugène Catalan, are a sequence of natural numbers that appear in many counting problems. These numbers are defined as:

\[ \begin{aligned} C_n = \frac{1}{n + 1} \binom{2n}{n} = \frac{(2n)!}{n!(n + 1)!} \end{aligned} \]

We ask: Given \(n\) variables \(x_1, \dots, x_n\), how many essentially different ways are there to compute their sum by repeatedly adding two terms at a time, where the order of operands in each addition is ignored?

Using \(a_1=1\) and the exponential generating function \(A(x)=\sum_{n\ge1}a_nx^n/n!\), the recurrence is

\[ \begin{aligned} a_n = \frac{1}{2} \sum_{k=1}^{n-1} \binom{n}{k} a_k a_{n-k}. \end{aligned} \]

\[ \begin{aligned} A(x)^2 - 2A(x) + 2x = 0. \end{aligned} \]

\[ \begin{aligned} {A}(x) = 1 - \sqrt{1 - 2x}. \end{aligned} \]

Therefore, the number of ways to compute the sum of \(n\) variables is

\[ \begin{aligned} a_n = (2n - 3)!!. \end{aligned} \]

The exponential generating function (EGF) of a sequence of real numbers \((a_k)_{k \ge 0}\) is the power series

\[ \begin{aligned} \widehat{A}(x) := \sum_{k \ge 0} a_k \frac{x^k}{k!}. \end{aligned} \]

Theorem 3.1 (EGF of Prefix Sums) Let \(s_n=\sum_{k=0}^n a_k\), \(\hat A(x)=\sum_{n\ge0}a_nx^n/n!\), and \(\hat S(x)=\sum_{n\ge0}s_nx^n/n!\). Since \(s_{n+1}=s_n+a_{n+1}\), differentiating term by term gives \[ \begin{aligned} \hat{S}'(x) &= \sum_{n \ge 0} s_{n+1} \frac{x^n}{n!} \\ &= \sum_{n \ge 0} s_n \frac{x^n}{n!} + \sum_{n \ge 0} a_{n+1} \frac{x^n}{n!} \\ &= \hat{S}(x) + \hat{A}'(x). \end{aligned} \]

So \(\hat{S}\) satisfies the linear differential equation \[ \begin{aligned} \hat{S}'(x) - \hat{S}(x) &= \hat{A}'(x), & \hat{S}(0) &= s_0 = a_0. \end{aligned} \]

Multiplying by \(e^{-x}\) on both sides gives \[ \begin{aligned} \frac{\text{d}}{\text{dx}} (\hat{S}(x)e^{-x}) = \hat{A}'(x)e^{-x}. \end{aligned} \]

Integrating both sides from \(0\) to \(x\), we obtain \[ \begin{aligned} \hat{S}(x)e^{-x} = a_0 + \int_0^x \hat{A}'(t)e^{-t} \text{dt}, \end{aligned} \]

where we used the initial condition \(\hat{S}(0) = a_0\). Therefore, the EGF of the prefix sums is \[ \begin{aligned} \hat{S}(x) = a_0 e^x + \int_0^x \hat{A}'(t)e^{x-t} \text{dt}. \end{aligned} \]

Equivalently, by integrating by parts, we can also write this as \[ \begin{aligned} \hat{S}(x) = \hat{A}(x) + \int_0^x \hat{A}(t)e^{x-t} \text{dt}. \end{aligned} \]

The Laplace transform of a function \(f\) is defined by \[ \begin{aligned} \mathcal{L}[f](s) := \int_0^\infty f(t)e^{-st} \text{dt}. \end{aligned} \]

If the OGF and EGF of a sequence \((a_n)_{n \ge 0}\) are given by \[ \begin{aligned} A(z) := \sum_{n \ge 0} a_n z^n \quad \text{and} \quad \hat{A}(t) := \sum_{n \ge 0} a_n \frac{t^n}{n!}, \end{aligned} \]

then, whenever termwise integration is justified (for example by absolute convergence), \[ \begin{aligned} \mathcal{L}[\hat{A}](s) &= \int_0^\infty \left( \sum_{n \ge 0} a_n \frac{t^n}{n!} \right) e^{-st} \text{dt} \\ &= \sum_{n \ge 0} \frac{a_n}{n!} \int_0^\infty t^n e^{-st} \text{dt}. \end{aligned} \] With the change of variables \(u = st\), we can rewrite the integral in terms of the Gamma function \(\Gamma(z) := \int_0^\infty u^{z-1}e^{-u} \text{ du}\): \[ \begin{aligned} \int_0^\infty t^n e^{-st} \text{ dt} = \frac{1}{s^{n+1}} \int_0^\infty u^n e^{-u} \text{ du} = \frac{1}{s^{n+1}} \Gamma(n+1) = \frac{n!}{s^{n+1}}, \end{aligned} \]

where the last step uses the fact that \(\Gamma(n+1) = n!\) for all integers \(n \ge 0\).

Plugging this back into the Laplace transform, we obtain \[ \begin{aligned} \mathcal{L}[\hat{A}](s) = \sum_{n \ge 0} \frac{a_n}{n!} \cdot \frac{n!}{s^{n+1}} = \frac{1}{s} A \left( \frac{1}{s} \right). \end{aligned} \]

Setting \(s = \frac{1}{z}\) gives \[ \begin{aligned} \frac{1}{z} \mathcal{L}[\hat{A}] \left( \frac{1}{z} \right) = A(z). \end{aligned} \]

Let \(S_k(n)=\sum_{j=1}^n j^k\). Define the Bernoulli numbers by \(x/(e^x-1)=\sum_{m\ge0}B_mx^m/m!\), so \(B_0=1\) and \(B_1=-1/2\).

\[ \begin{aligned} F_n(x) := \sum_{k \ge 0} S_k(n) \frac{x^k}{k!}. \end{aligned} \]

\[ \begin{aligned} F_n(x) &= \sum_{k \ge 0} \left( \sum_{j=1}^n j^k \right) \frac{x^k}{k!} = \sum_{k \ge 0} \sum_{j=1}^n \frac{(jx)^k}{k!} = \sum_{j=1}^n \sum_{k \ge 0} \frac{(jx)^k}{k!} = \sum_{j=1}^n e^{jx}. \end{aligned} \]

Of course, we can rewrite \(F_n(x)\) as \[ \begin{aligned} F_n(x) = \frac{e^{nx} - 1}{x} \cdot \frac{xe^x}{e^x - 1}. \end{aligned} \]

Since \(\frac{xe^x}{e^x - 1} = \frac{x}{1 - e^{-x}}\), we can further rewrite \(F_n(x)\) as \[ \begin{aligned} F_n(x) = \frac{e^{nx} - 1}{x} \cdot \frac{x}{1 - e^{-x}}. \end{aligned} \]

The coefficients of the first term \(\frac{e^{nx} - 1}{x}\) are easy to extract: \[ \begin{aligned} \frac{e^{nx} - 1}{x} = \frac{1}{x} \sum_{k \ge 0} (n^k - \mathbb{1}_{[k=0]}) \frac{x^k}{k!} = \sum_{k \ge 0} \frac{n^{k+1}}{k+1} \frac{x^k}{k!}. \end{aligned} \]

\[ \begin{aligned} \hat{B}(x) = \frac{x}{e^x - 1}. \end{aligned} \]

It is easy to check that \[ \begin{aligned} \frac{x}{1 - e^{-x}} = \frac{-x}{e^{-x} - 1} = \hat{B}(-x). \end{aligned} \]

\[ \begin{aligned} \frac{x}{e^x - 1} = \sum_{m \ge 0} B_m \frac{x^m}{m!}. \end{aligned} \]

\[ \begin{aligned} F_n(x) &= \frac{e^{nx} - 1}{x} \cdot \hat{B}(-x) = \left( \sum_{k \ge 0} \frac{n^{k+1}}{k+1} \frac{x^k}{k!} \right) \left( \sum_{m \ge 0} (-1)^m B_m \frac{x^m}{m!} \right). \end{aligned} \]

Theorem 3.2 (Faulhaber’s formula) For all \(k \ge 0\) and \(n \ge 1\), \[ \begin{aligned} S_k(n) = \frac{1}{k+1} \sum_{j=0}^k (-1)^j \binom{k+1}{j} B_j n^{k+1-j}. \end{aligned} \]

3.2 Complex Analysis

A complex number is a number of the form \[ \begin{aligned} z = x + iy, \quad x, y \in \mathbb{R}, \end{aligned} \]

where \(i\) is the imaginary unit. The number \(x\) is called the real part of \(z\), and \(y\) is called the imaginary part. We write \[ \begin{aligned} \Re(z) = x, \quad \Im(z) = y. \end{aligned} \]

The set of all complex numbers is denoted by \(\mathbb{C}\).

If \(z = x + iy\), then its conjugate is \[ \begin{aligned} \bar{z} = x - iy, \end{aligned} \] and its absolute value or modulus is \[ \begin{aligned} |z| = (z\bar{z})^{1/2} = \sqrt{x^2 + y^2}. \end{aligned} \]

3.2.1 Complex Functions and Power Series

Let \(S \subseteq \mathbb{C}\) be a set of complex numbers. A complex function on \(S\) is a function \(f : S \to \mathbb{C}\).

A power series is an infinite sum of the form

\[ \sum_{n \geq 0} a_n z^n, \]

where \(a_n \in \mathbb{C}\) is the coefficient of the \(n\)-th term \(z^n\). More generally, a power series with respect to a center \(z_0 \in \mathbb{C}\) is an infinite sum of the form

\[ \sum_{n \geq 0} a_n (z - z_0)^n. \]

We say that a sequence \((z_n)_{n \geq 0}\) of complex numbers converges to \(A \in \mathbb{C}\) if for every \(\epsilon > 0\) there exists \(N\) such that

\[ |z_n - A| < \epsilon \quad \text{for all } n \geq N. \]

Theorem 3.3 (Cauchy–Hadamard theorem) Let \(\sum_{n \geq 0} a_n z^n\). Define

\[ R := \frac{1}{\limsup_{n \to \infty} |a_n|^{1/n}} \in [0, +\infty) \cup \{+\infty\}. \]

Then, for all \(z \in \mathbb{C}\),

  1. if \(|z| < R\), then the series converges absolutely;
  2. if \(|z| > R\), then the series does not converge.

This \(R\) is called the radius of convergence of the power series.

Theorem 3.4 (Euler’s formula) For every \(x \in \mathbb{R}\),

\[ e^{ix} = \cos x + i \sin x. \]

3.2.2 Continuous Functions

Let \(f : S \to \mathbb{C}\) be a complex function. We say that \(f\) is continuous at \(z_0 \in S\) if the limit of \(f(z)\) as \(z \in S\) approaches \(z_0\) exists and is equal to \(f(z_0)\). That is,

\[ \lim_{z \to z_0} f(z) = f(z_0). \]

We say that \(f\) is continuous on \(S\) if it is continuous at every point of \(S\).

3.2.3 Holomorphic Functions

Let \(S \subseteq \mathbb{C}\) be a set. We say that \(S\) is open if for every \(z_0 \in S\), there exists some \(\delta > 0\) such that for all \(z \in \mathbb{C}\) with \(|z - z_0| < \delta\), we have

\[ z \in S. \]

We say that \(S\) is closed if its complement \(\mathbb{C} \setminus S\) is open. An equivalent definition is that \(S\) is closed if for every convergent sequence \((z_n)_{n \geq 0}\) in \(S\), the limit \(\lim_{n \to \infty} z_n\) is also in \(S\).

Let \(f : S \to \mathbb{C}\) be a complex function defined on an open set \(S \subseteq \mathbb{C}\). We say that \(f\) is differentiable at \(z_0 \in S\) if the limit

\[ f'(z_0) := \lim_{z \to z_0} \frac{f(z) - f(z_0)}{z - z_0} \]

exists. Further, we say that \(f\) is differentiable on \(S\) if it is differentiable at every point of \(S\).

Let \(f : S \to \mathbb{C}\) be a complex function defined on an open set \(S \subseteq \mathbb{C}\). We say that \(f\) is infinitely differentiable at \(z_0 \in S\) if all the higher order derivatives of \(f\),

\[ f'(z_0), f''(z_0), f^{(3)}(z_0), f^{(4)}(z_0), \dots \]

exist at \(z_0\). Further, we say that \(f\) is infinitely differentiable on \(S\) if it is infinitely differentiable at every point of \(S\).

Let \(f : S \to \mathbb{C}\) be a complex function defined on an open set \(S \subseteq \mathbb{C}\). We say that \(f\) is analytic at \(z_0 \in S\) if there exists a sequence of complex numbers \((a_n)_{n \geq 0}\) such that for some \(\delta > 0\), for all \(z \in S\) with \(|z - z_0| < \delta\),

\[ f(z) = \sum_{n \geq 0} a_n (z - z_0)^n. \]

Further, we say that \(f\) is analytic on \(S\) if it is analytic at every point of \(S\).

Theorem 3.5 Let \(f : S \to \mathbb{C}\) be a complex function defined on an open set \(S \subseteq \mathbb{C}\). Then the following properties are equivalent:

  1. \(f\) is differentiable on \(S\);
  2. \(f\) is infinitely differentiable on \(S\);
  3. \(f\) is analytic on \(S\).

Let \(f : S \to \mathbb{C}\) be a complex function defined on an open set \(S \subseteq \mathbb{C}\). We say that \(f\) is holomorphic at \(z_0 \in S\) if it is differentiable in an open set containing \(z_0\). Further, we say that \(f\) is holomorphic on \(S\) if it is differentiable at every point of \(S\).

Theorem 3.6 (Cauchy–Riemann equations) Let \(f\) be differentiable at \(z_0 = x_0 + iy_0\), and write \[ \begin{aligned} f(x + iy) = u(x, y) + iv(x, y). \end{aligned} \]

Then the following four partial derivatives exist at \((x_0, y_0)\):

\[ \begin{aligned} \frac{\partial u}{\partial x}, \quad \frac{\partial u}{\partial y}, \quad \frac{\partial v}{\partial x}, \quad \frac{\partial v}{\partial y}. \end{aligned} \]

Furthermore, they satisfy the Cauchy–Riemann equations:

\[ \begin{aligned} \frac{\partial u}{\partial x}(x_0, y_0) = \frac{\partial v}{\partial y}(x_0, y_0), \quad \frac{\partial u}{\partial y}(x_0, y_0) = -\frac{\partial v}{\partial x}(x_0, y_0). \end{aligned} \]

A curve in \(\mathbb{C}\) is a continuous function \(\gamma : [a, b] \to \mathbb{C}\). Furthermore,

  • We say that \(\gamma\) is smooth if it is continuously differentiable and its derivative \(\gamma'\) is nowhere zero.
  • We say that \(\gamma\) is simple if it is injective. That is, \(\gamma\) does not cross itself.
  • We say that \(\gamma\) is closed if \(\gamma(a) = \gamma(b)\). That is, \(\gamma\) returns to its starting point at the very end.
  • We say that \(\gamma\) is a simple closed curve if it is closed and is injective on \([a, b)\). That is, \(\gamma\) does not cross itself except at the endpoints.

3.2.4 Complex Integrals

A contour is a sequence of smooth curves

\[ \gamma = \{\gamma_1, \gamma_2, \dots, \gamma_n\} \]

such that the end point of \(\gamma_i\) is the starting point of \(\gamma_{i+1}\) for \(i \in [n - 1]\).

Let \(f : S \to \mathbb{C}\) be a complex function defined on an open set \(S \subseteq \mathbb{C}\). If \(\gamma : [a, b] \to S\) is a smooth curve in \(S\), then the integral of \(f\) along \(\gamma\) is defined by

\[ \int_\gamma f(z) \, \mathrm{d}z := \int_a^b f(\gamma(t))\gamma'(t) \, \mathrm{d}t. \]

If \(\gamma = \gamma_1 + \dots + \gamma_n\) is a contour, then the contour integral of \(f\) along \(\gamma\) is defined as the sum of the integrals of \(f\) along the smooth curves that make up the contour:

\[ \int_\gamma f(z) \, \mathrm{d}z := \sum_{i=1}^n \int_{\gamma_i} f(z) \, \mathrm{d}z. \]

Theorem 3.7 (Reparameterization and reversal of direction) Let \(f : S \to \mathbb{C}\) be a complex function defined on an open set \(S \subseteq \mathbb{C}\). Let \(\gamma_1 : [a, b] \to S\) and \(\gamma_2 : [c, d] \to S\) be two smooth curves. If there exists an increasing continuously differentiable function \(\phi : [c, d] \to [a, b]\) such that \(\phi(c) = a\), \(\phi(d) = b\), and \(\gamma_2(t) = \gamma_1(\phi(t))\) for all \(t \in [c, d]\), then \[ \begin{aligned} \int_{\gamma_2} f(z) \mathrm{d}z = \int_{\gamma_1} f(z) \mathrm{d}z. \end{aligned} \]

Theorem 3.8 (ML Inequality) Let \(f : S \to \mathbb{C}\) be a complex function defined on an open set \(S \subseteq \mathbb{C}\). If \(\gamma : [a, b] \to S\) is a smooth curve in \(S\) and \(|f(\gamma(t))| \leq M\) for all \(t \in [a, b]\), then

\[ \left| \int_\gamma f(z) \, \mathrm{d}z \right| \leq M \cdot L(\gamma). \]

Theorem 3.9 (Cauchy–Goursat theorem) Let \(f : S \to \mathbb{C}\) be a holomorphic function defined on an open set \(S \subseteq \mathbb{C}\). Let \(\gamma\) be a simple closed contour such that the region enclosed by \(\gamma\) is contained in \(S\). Then the contour integral of \(f\) along \(\gamma\) is zero. That is,

\[ \int_\gamma f(z) \, \mathrm{d}z = 0. \]

3.2.5 Integrals Around Singularities

Let \(f : S \to \mathbb{C}\) be a complex function. We say that \(z_0\) is a singular point, or a singularity of \(f\) if \(f\) is either not defined at \(z_0\) or not holomorphic at \(z_0\), but for every \(\epsilon > 0\), there exists a complex number \(z \in S\) such that \(|z - z_0| < \epsilon\) and \(f\) is holomorphic at \(z\).

Let \(f : S \to \mathbb{C}\) be a complex function. We say that \(z_0\) is an isolated singularity of \(f\) if \(f\) is either not defined at \(z_0\) or not holomorphic at \(z_0\), but there exists an \(\epsilon > 0\) such that \(f\) is holomorphic on the punctured disk \(\{z \in \mathbb{C} : 0 < |z - z_0| < \epsilon\}\).

Theorem 3.10 (Cauchy’s integral formula) Let \(f : S \to \mathbb{C}\) be a holomorphic function on an open set \(S \subseteq \mathbb{C}\). Let \(\gamma\) be a simple closed counterclockwise contour such that the region enclosed by \(\gamma\) is contained in \(S\). Then for every \(z\) enclosed by \(\gamma\),

\[ f(z) = \frac{1}{2\pi i} \int_\gamma \frac{f(w)}{w - z} \, \mathrm{d}w. \]

Theorem 3.11 (Cauchy’s estimate) Let \(f : S \to \mathbb{C}\) be a holomorphic function on an open set \(S \subseteq \mathbb{C}\). Let \(z_0 \in S\) and \(r > 0\) be such that the closed disk \(\overline{D}(z_0, r) \subseteq S\). If \(|f(z)| \leq M\) for all \(z \in \overline{D}(z_0, r)\), then for all \(n \geq 0\),

\[ |f^{(n)}(z_0)| \leq \frac{n! M}{r^n}. \]

Theorem 3.12 Let \(f : S \to \mathbb{C}\) be a holomorphic function on an open set \(S \subseteq \mathbb{C}\). Fix \(z_0 \in S\) and \(r > 0\) such that the circle \(C_r\) centered at \(z_0\) and its interior \(D_r\) are both contained in \(S\). Then for every \(z \in D_r\),

\[ f(z) = \sum_{n \geq 0} a_n(z-z_0)^n, \quad \text{where } a_n = \frac{1}{2\pi i} \int_{C_r} \frac{f(w)}{(w - z_0)^{n+1}} \, \mathrm{d}w. \]

Theorem 3.13 (Cauchy integral formula for derivatives) Let \(f : S \to \mathbb{C}\) be a holomorphic function on an open set \(S \subseteq \mathbb{C}\). Let \(\gamma\) be a simple closed counterclockwise contour such that the region enclosed by \(\gamma\) is contained in \(S\). Then for every \(z\) enclosed by \(\gamma\) and every integer \(n \geq 0\),

\[ f^{(n)}(z) = \frac{n!}{2\pi i} \int_\gamma \frac{f(w)}{(w - z)^{n+1}} \, \mathrm{d}w. \]

Theorem 3.14 (Identity theorem) Let \(S \subseteq \mathbb{C}\) be a connected open set, and let \(f,g : S \rightarrow \mathbb{C}\) be holomorphic. If there exists a non-empty open set \(U \subseteq S\) such that \(f(z)=g(z)\) for every \(z\in U\), then \(f(z)=g(z)\) for every \(z\in S\).

Let \(f : S \to \mathbb{C}\) be a complex function with an isolated singularity at \(z_0\). We say that \(z_0\) is a removable singularity of \(f\) if there exists a complex number \(w \in \mathbb{C}\) such that assigning the value \(w\) to \(f(z_0)\) makes \(f\) holomorphic at \(z_0\). We say that \(z_0\) is a non-removable singularity of \(f\) if it is not removable.

Theorem 3.15 Let \(f : S \to \mathbb{C}\) be a holomorphic function on an open set \(S \subseteq \mathbb{C}\). Fix \(z_0 \in S\). If the following holds for some \(R > 0\):

  1. \(f\) is holomorphic on the open disk \(D_R\) centered at \(z_0\) with radius \(R\);
  2. \(f\) has a non-removable singularity at some point \(s\) with \(|s - z_0| = R\),

Then the radius of convergence of the Taylor series of \(f\) around \(z_0\),

\[ \sum_{n \geq 0} \frac{f^{(n)}(z_0)}{n!} (z - z_0)^n, \]

is exactly \(R\).

3.2.6 Expansion Around Isolated Singularities

Theorem 3.16 (Laurent’s theorem) Let \(f\) be holomorphic on a punctured disk \(D_r(z_0) \setminus \{z_0\}\) for some \(z_0 \in \mathbb{C}\) and some \(r > 0\). Then there exists a unique sequence \((a_n)_{n \geq 0}\) and a unique sequence \((b_n)_{n \geq 1}\) such that

\[ f(z) = \sum_{n=0}^\infty a_n (z - z_0)^n + \sum_{n=1}^\infty b_n (z - z_0)^{-n} \]

for every \(z \in D_r(z_0) \setminus \{z_0\}\).

Let \(z_0\) be an isolated singularity of \(f\) with Laurent series expansion

\[ f(z) = \sum_{n=-\infty}^\infty a_n (z - z_0)^n. \]

  • If \(a_j = 0\) for all \(j < 0\), then \(z_0\) is a removable singularity of \(f\).
  • If \(a_{-m} \neq 0\) for some positive integer \(m\) and \(a_j = 0\) for all \(j < -m\), then we say that \(z_0\) is a pole of order \(m\) of \(f\). A pole of order 1 is called a simple pole.
  • If \(a_j \neq 0\) for infinitely many negative integers \(j\), then we say that \(z_0\) is an essential singularity of \(f\).

Let \(z_0\) be an isolated singularity of \(f\) that admits a Laurent series expansion around \(z_0\):

\[ f(z) = \sum_{n=-\infty}^\infty a_n (z - z_0)^n \]

Then the coefficient \(a_{-1}\) of \((z - z_0)^{-1}\) is called the residue of \(f\) at \(z_0\), which is denoted by \(\operatorname{Res}(f, z_0)\).

Theorem 3.17 (Cauchy’s residue theorem) Let \(f\) be a holomorphic function on an open set \(S \subseteq \mathbb{C}\). Let \(\gamma\) be a simple closed counterclockwise contour such that the region enclosed by \(\gamma\) is contained in \(S\) except for \(m\) isolated singularities \(z_1, \dots, z_m\). Then

\[ \frac{1}{2\pi i} \int_\gamma f(z) \, \mathrm{d}z = \sum_{j=1}^m \operatorname{Res}(f, z_j). \]

Let \(z_0\) be an isolated singularity of \(f\).

  1. If \(\lim_{z \to z_0} (z - z_0)f(z)\) exists, then

    \[ \operatorname{Res}(f, z_0) = \lim_{z \to z_0} (z - z_0)f(z). \]

    Moreover, \(z_0\) is a simple pole if \(\operatorname{Res}(f, z_0) \neq 0\), or a removable singularity if \(\operatorname{Res}(f, z_0) = 0\).

  2. If \(f(z) = \frac{g(z)}{h(z)}\) for some holomorphic functions \(g\) and \(h\) near \(z_0\), with \(h(z_0) = 0\) and \(h'(z_0) \neq 0\), then

    \[ \operatorname{Res}(f, z_0) = \frac{g(z_0)}{h'(z_0)}, \]

    Moreover, \(z_0\) is a simple pole if \(\operatorname{Res}(f, z_0) \neq 0\), or a removable singularity if \(\operatorname{Res}(f, z_0) = 0\).

  3. If \(z_0\) is a pole of order at most \(m\), then

    \[ \operatorname{Res}(f, z_0) = \frac{1}{(m - 1)!} \lim_{z \to z_0} \frac{\mathrm{d}^{m-1}}{\mathrm{d}z^{m-1}} \left[ (z - z_0)^m f(z) \right]. \]

Theorem 3.18 If \(f\) is holomorphic at \(0\), then for every \(n \geq 0\),

\[ \frac{f^{(n)}(0)}{n!} = \operatorname{Res}\left( \frac{f(z)}{z^{n+1}}, 0 \right). \]

3.3 Generating Functions of Random Variables

3.3.1 Probability Generating Functions

Let \(X\) be a random variable taking values in non-negative integers. Its probability generating function (PGF) is defined as

\[ G_X(z) := \sum_{k \geq 0} \operatorname{Pr}[X = k] z^k. \]

Theorem 3.19 (Expectation and variance from the PGF) Let \(X\) be a random variable taking values in non-negative integers. Then

\[ \begin{aligned} \mathbb{E}[X] &= G_X'(1), \\ \mathbb{E}[X^2] &= G_X''(1) + G_X'(1), \\ \operatorname{Var}(X) &= G_X''(1) + G_X'(1) - \left(G_X'(1)\right)^2. \end{aligned} \]

Theorem 3.20 Let \(X\) and \(Y\) be independent random variables taking values in non-negative integers. Then

\[ G_{X+Y}(z) = G_X(z)G_Y(z). \]

3.3.2 Moment Generating Functions

The moment generating function (MGF) of a random variable \(X\) is defined as

\[ M_X(t) := \mathbb{E}[e^{tX}]. \]

Theorem 3.21 Let \(X_1, \dots, X_n\) be independent random variables, and let \(X\) be a weighted sum of these random variables:

\[ X := \sum_{k=1}^n c_k X_k, \]

where \(c_1, \dots, c_n \in \mathbb{R}\) are constants. Then

\[ M_X(t) = \prod_{k=1}^n M_{X_k}(c_k t). \]

3.3.3 Recovering Distributions from MGFs

Theorem 3.22 Let \(c > 0\). For every \(\delta \in \mathbb{R}\), we have

\[ \lim_{T \to +\infty} \frac{1}{2\pi i} \int_{c-iT}^{c+iT} \frac{e^{\delta z}}{z} \, \mathrm{d}z = \begin{cases} 0 & \text{if } \delta < 0, \\ 1/2 & \text{if } \delta = 0, \\ 1 & \text{if } \delta > 0, \end{cases} \]

where \(\int_{c-iT}^{c+iT}\) means integrating along the line segment from \(c - iT\) to \(c + iT\), i.e., \(\gamma_{c,T}(t) = c + it\) for \(t \in [-T, T]\).

Theorem 3.23 (Inversion formula for the MGF) Let \(X\) be a random variable with MGF \(M_X(t)\). For every \(x_1 < x_2\), define

\[ p_X(x_1, x_2) := \frac{1}{2} \operatorname{Pr}[X = x_1] + \operatorname{Pr}[x_1 < X < x_2] + \frac{1}{2} \operatorname{Pr}[X = x_2]. \]

Then for every \(c > 0\),

\[ p_X(x_1, x_2) = \frac{1}{2\pi i} \lim_{T \to +\infty} \int_{c-iT}^{c+iT} \frac{e^{-x_1 z} - e^{-x_2 z}}{z} M_X(z) \, \mathrm{d}z. \]

3.3.4 Cumulant Generating Functions

The cumulant generating function (CGF) of a random variable \(X\) is defined as

\[ K_X(t) := \log M_X(t) = \sum_{m \geq 1} \kappa_m(X) \frac{t^m}{m!}, \quad \kappa_m(X) = K_X^{(m)}(0). \]

Let \(X\) be a random variable with MGF \(M_X(t)\) and CGF \(K_X(t)\). The relationship between its moments (derived from \(M_X\)) and cumulants (derived from \(K_X\)) evaluated at \(t=0\) is given by the following table:

Statistic From MGF (\(M_X\)) From CGF (\(K_X\))
Expectation
\(\mathbb{E}[X]\)		 \(M_X'(0)\) \(K_X'(0)\)
Second Moment
\(\mathbb{E}[X^2]\)		 \(M_X''(0)\) \(K_X''(0) + K_X'(0)^2\)
Variance
\(\operatorname{Var}(X)\)		 \(M_X''(0) - M_X'(0)^2\) \(K_X''(0)\)

Theorem 3.24 Let \(X_1, \dots, X_n\) be independent random variables, and let \(X\) be a weighted sum of these random variables:

\[ X := \sum_{k=1}^n c_k X_k, \]

where \(c_1, \dots, c_n \in \mathbb{R}\) are constants. Then

\[ K_X(t) = \sum_{k=1}^n K_{X_k}(c_k t), \quad \kappa_m(X) = \sum_{k=1}^n \kappa_m(c_k X_k). \]

3.3.5 Exponential Tilting

Let \(X\) be a random variable with probability mass function \(p_X(x)\). The \(\lambda\)-tilted distribution of \(X\), denoted by \(\mathcal{T}_{X,\lambda}\), is defined by the distribution corresponding to the probability mass function

\[ q(x) = \frac{p_X(x)e^{\lambda x}}{M_X(\lambda)}, \quad \forall x \in \mathbb{R}. \]

Theorem 3.25 Let \(X\) be a random variable and \(Y \sim \mathcal{T}_{X,\lambda}\) be a random variable drawn from the \(\lambda\)-tilted distribution of \(X\). Then

\[ \begin{aligned} M_Y(t) &= \frac{M_X(\lambda + t)}{M_X(\lambda)}, \\ K_Y(t) &= K_X(\lambda + t) - K_X(\lambda), \\ K_Y^{(m)}(0) &= K_X^{(m)}(\lambda), \quad \forall m \geq 1. \end{aligned} \]

3.4 Appendix

Theorem 3.26 Lagrange inversion formula via residues

Let \(S\) and \(U\) be two open subsets of \(\mathbb{C}\) containing \(0\). Let \(f : S \to U\) and \(g : U \to S\) be holomorphic functions that are inverse to each other, meaning \(f(g(z)) = z\) for all \(z \in U\) and \(g(f(w)) = w\) for all \(w \in S\). Assume further that \(f(0) = 0\).

Then there exists a radius \(r > 0\) such that for all \(z \in D_r(0)\), the inverse function \(g(z)\) can be expanded as the power series

\[ g(z) = \sum_{n \geq 1} g_n z^n, \]

where the coefficients \(g_n\) are given by \(g_n := \frac{1}{n} \operatorname{Res}(h_n, 0)\) and \(h_n\) is the holomorphic function defined by

\[ h_n(w) = \left( \frac{1}{f(w)} \right)^n. \]

Theorem 3.27 (Laurent series coefficient representation and uniqueness) Let \(f(z)\) be a holomorphic function defined in an open annulus centered at \(z_0\). If \(f(z)\) can be represented as a Laurent series of the form

\[ f(z) = \sum_{n=-\infty}^{\infty} a_n (z - z_0)^n \]

for some sequence of complex coefficients \((a_n)_{n \in \mathbb{Z}}\), then for all \(n \in \mathbb{Z}\), these coefficients are uniquely determined and given by the contour integral

\[ a_n = \frac{1}{2\pi i} \int_{C_r(z_0)} \frac{f(w)}{(w - z_0)^{n+1}} \, \mathrm{d}w, \]

where \(C_r(z_0)\) is any positively oriented circle of radius \(r\) centered at \(z_0\) lying entirely within the domain of holomorphy. Consequently, this integral representation guarantees the uniqueness of the coefficients in the Laurent series.