TAOCP 1.2.9 Exercise 20
We are asked to express the generating function \sum_{n \ge 0} n^m z^n in the form
Section 1.2.9: Generating Functions
Exercise 20. [M21] For what coefficients $c_{mk}$ is
$$ \sum_{n \ge 0} n^m z^n = \sum_{k=0}^{m} c_{mk}\frac{z^k}{(1-z)^{k+1}} , ? $$
Verified: yes
Solve time: 1m
Solution
We are asked to express the generating function
$$ \sum_{n \ge 0} n^m z^n $$
in the form
$$ \sum_{k=0}^{m} c_{mk}\frac{z^k}{(1-z)^{k+1}}. $$
Let $G_m(z) = \sum_{n \ge 0} n^m z^n$. By Eq. (5), we have
$$ \sum_{n \ge 0} z^n = \frac{1}{1-z}. $$
Differentiating both sides with respect to $z$ gives, by Eq. (14),
$$ \sum_{n \ge 0} n z^{n-1} = \frac{1}{(1-z)^2}. $$
Multiplying through by $z$ yields
$$ \sum_{n \ge 0} n z^n = \frac{z}{(1-z)^2}. $$
Hence the formula holds for $m=1$ with $c_{11}=1$ and $c_{10}=0$.
We now proceed by induction on $m$. Assume that for some $m \ge 1$ there exist constants $c_{mk}$ such that
$$ G_m(z) = \sum_{n \ge 0} n^m z^n = \sum_{k=0}^{m} c_{mk}\frac{z^k}{(1-z)^{k+1}}. \tag{1} $$
Consider $G_{m+1}(z) = \sum_{n \ge 0} n^{m+1} z^n$. We write
$$ n^{m+1} z^n = z \frac{d}{dz}(n^m z^n), $$
because $z \frac{d}{dz} (z^n n^m) = n^{m+1} z^n$. Hence
$$ G_{m+1}(z) = z \frac{d}{dz} \sum_{n \ge 0} n^m z^n = z \frac{d}{dz} G_m(z). \tag{2} $$
By the induction hypothesis (1),
$$ G_m(z) = \sum_{k=0}^{m} c_{mk} \frac{z^k}{(1-z)^{k+1}}. $$
Applying $z \frac{d}{dz}$ to each term gives
$$ z \frac{d}{dz} \frac{z^k}{(1-z)^{k+1}} = z \cdot \frac{k z^{k-1} (1-z)^{k+1} + z^k (k+1)(1-z)^k}{(1-z)^{2k+2}}. $$
Simplifying the numerator:
$$
\begin{aligned}
k z^{k-1} (1-z)^{k+1} + (k+1) z^k (1-z)^k &= z^{k-1} (1-z)^k \left( k (1-z) + (k+1) z \right) \
&= z^{k-1} (1-z)^k \left( k - k z + k z + z \right) \
&= z^{k-1} (1-z)^k (k + z).
\end{aligned}
$$
Multiplying by $z$ gives
$$ z \cdot z^{k-1} (1-z)^k (k+z) = z^k (1-z)^k (k+z). $$
Dividing by $(1-z)^{2k+2}$ yields
$$ z \frac{d}{dz} \frac{z^k}{(1-z)^{k+1}} = \frac{z^k (k+z)}{(1-z)^{k+2}} = \frac{k z^k}{(1-z)^{k+2}} + \frac{z^{k+1}}{(1-z)^{k+2}}. \tag{3} $$
Hence
$$ G_{m+1}(z) = \sum_{k=0}^{m} c_{mk} \left( \frac{k z^k}{(1-z)^{k+2}} + \frac{z^{k+1}}{(1-z)^{k+2}} \right). $$
We can reindex the second sum by setting $k' = k+1$ to get
$$ \sum_{k=0}^{m} c_{mk} \frac{z^{k+1}}{(1-z)^{k+2}} = \sum_{k=1}^{m+1} c_{m,k-1} \frac{z^k}{(1-z)^{k+1}}. $$
Similarly, the first sum can be written as
$$ \sum_{k=0}^{m} c_{mk} \frac{k z^k}{(1-z)^{k+2}} = \sum_{k=0}^{m} k c_{mk} \frac{z^k}{(1-z)^{k+2}} = \sum_{k=0}^{m} k c_{mk} \frac{z^k}{(1-z)^{k+1}} \cdot \frac{1}{1-z}. $$
Combining these observations shows that $G_{m+1}(z)$ is a linear combination of terms $z^k/(1-z)^{k+1}$ with $k = 0,1,\dots,m+1$. Hence the formula holds for $m+1$. By induction, the representation
$$ G_m(z) = \sum_{k=0}^{m} c_{mk} \frac{z^k}{(1-z)^{k+1}} $$
exists for all $m \ge 0$.
The coefficients $c_{mk}$ satisfy the recurrence
$$ c_{m+1,0} = 0, \quad c_{m+1,k} = k c_{mk} + c_{m,k-1} \quad (1 \le k \le m+1), \tag{4} $$
with $c_{00}=1$ and $c_{m,-1}=0$ for convenience. This can be verified directly from the calculation above.
Explicit values for small $m$ follow:
- $m=0$: $G_0(z) = \sum z^n = 1/(1-z)$, so $c_{00}=1$.
- $m=1$: $G_1(z) = z/(1-z)^2$, so $c_{11}=1$, $c_{10}=0$.
- $m=2$: applying (4): $c_{22}=1$, $c_{21}=1$, $c_{20}=0$, giving $G_2(z) = z/(1-z)^2 + z^2/(1-z)^3$.
This completes the proof.
∎
Notes
The coefficients $c_{mk}$ are known as Stirling numbers of the second kind times factorials in combinatorial interpretations:
$$ c_{mk} = k! \left{ {m \atop k} \right}, $$
where $\left{ {m \atop k} \right}$ denotes the number of ways to partition a set of $m$ objects into $k$ nonempty subsets. This explains the combinatorial origin of the recurrence (4).