TAOCP 1.2.9 Exercise 12

Section 1.2.9: Generating Functions

Exercise 12. [M20] Suppose we have a doubly subscripted sequence $\langle a_{mn} \rangle$ for $m,n=0,1,\ldots$; show how this double sequence can be represented by a single generating function of two variables, and determine the generating function for $\left\langle \binom{n}{m} \right\rangle$.

Verified: yes
Solve time: 6m41s

Solution

A doubly subscripted sequence $\langle a_{mn} \rangle$ with $m,n \ge 0$ is represented by introducing two independent parameters $z$ and $w$ and forming the double power series

$$ G(z,w) = \sum_{m \ge 0}\sum_{n \ge 0} a_{mn} z^m w^n. \tag{1} $$

The coefficient of $z^m w^n$ in $G(z,w)$ is $a_{mn}$, since the right-hand side is defined termwise as a formal series in two variables.

For fixed $n$, the inner sum

$$ \sum_{m \ge 0} a_{mn} z^m $$

is the generating function in $z$ of the sequence $\langle a_{mn} \rangle_{m \ge 0}$. Thus $G(z,w)$ may be viewed as a generating function in $w$ whose coefficients are generating functions in $z$, or symmetrically in the opposite order.

For the sequence $\left\langle \binom{n}{m} \right\rangle$, define

$$ G(z,w) = \sum_{n \ge 0}\sum_{m \ge 0} \binom{n}{m} z^m w^n. \tag{2} $$

For each fixed $n$, the inner sum satisfies

$$ \sum_{m \ge 0} \binom{n}{m} z^m = \sum_{m=0}^{n} \binom{n}{m} z^m, $$

since $\binom{n}{m} = 0$ when $m>n$. By the binomial theorem in Eq. (19),

$$ \sum_{m=0}^{n} \binom{n}{m} z^m = (1+z)^n. \tag{3} $$

Substituting (3) into (2) gives

$$ G(z,w) = \sum_{n \ge 0} (1+z)^n w^n. \tag{4} $$

This is a geometric series in the quantity $w(1+z)$. Using Eq. (5),

$$ \sum_{n \ge 0} (w(1+z))^n = \frac{1}{1-w(1+z)}. \tag{5} $$

Hence

$$ G(z,w) = \frac{1}{1-w-wz}. $$

The coefficient of $z^m w^n$ in this expansion equals $\binom{n}{m}$ by construction, so this rational function is the generating function for the double sequence.

This completes the proof. ∎