TAOCP 1.2.9 Exercise 5

For fixed $n$, define F_n(z) = (e^z-1)^n.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.9: Generating Functions

Exercise 5. [M20] Prove Eq. (23) by induction on $n$.

Verified: no
Solve time: -

Solution

For fixed $n$, define

$$ F_n(z) = (e^z-1)^n. $$

We must prove that

$$ F_n(z) = n!\sum_{k \ge 0} \left{ {k \atop n} \right}\frac{z^k}{k!}. \tag{23} $$

The proof proceeds by induction on $n$.

When $n=0$,

$$ F_0(z)=1. $$

Since

$$ \left{ {0 \atop 0} \right}=1, \qquad \left{ {k \atop 0} \right}=0 \quad (k>0), $$

the right-hand side of (23) becomes

$$ 0!\sum_{k\ge0}\left{ {k \atop 0} \right}\frac{z^k}{k!} =1. $$

Hence (23) holds for $n=0$.

Assume now that

$$ (e^z-1)^n = n!\sum_{k\ge0}\left{ {k \atop n} \right}\frac{z^k}{k!}. \tag{1} $$

We prove the formula for $n+1$.

Multiply both sides of (1) by $(e^z-1)$:

$$ (e^z-1)^{n+1} = \left( n!\sum_{k\ge0}\left{ {k \atop n} \right}\frac{z^k}{k!} \right) \left( \sum_{m\ge1}\frac{z^m}{m!} \right), $$

using Eq. (22). By Eq. (11), the coefficient of $z^r/r!$ in this product equals

$$ n!\sum_{k=0}^{r}\binom{r}{k} \left{ {k \atop n} \right}b_{r-k}, $$

where

$$ b_j= \begin{cases} 1,&j\ge1,\ 0,&j=0. \end{cases} $$

Therefore

$$ (e^z-1)^{n+1} = n!\sum_{r\ge0} \left( \sum_{k=0}^{r-1} \binom{r}{k} \left{ {k \atop n} \right} \right) \frac{z^r}{r!}. \tag{2} $$

The Stirling numbers of the second kind satisfy

$$ \left{ {r \atop n+1} \right} = \frac{1}{(n+1)!} \sum_{k=0}^{r-1} \binom{r}{k} n!\left{ {k \atop n} \right}. \tag{3} $$

Equation (3) follows from the combinatorial interpretation of Stirling numbers. To partition an $r$-element set into $n+1$ nonempty blocks, first choose the $k$ elements not belonging to the block containing a distinguished element; this can be done in $\binom{r}{k}$ ways. Then partition those $k$ elements into $n$ nonempty blocks, in $\left{ {k \atop n} \right}$ ways. The remaining $r-k$ elements form the distinguished block. Since any of the $n+1$ blocks could be distinguished, each partition is counted exactly $n+1$ times. Hence

$$ (n+1)\left{ {r \atop n+1} \right} = \sum_{k=0}^{r-1} \binom{r}{k} \left{ {k \atop n} \right}, $$

which is equivalent to (3).

Substituting (3) into (2) gives

$$ (e^z-1)^{n+1} = (n+1)! \sum_{r\ge0} \left{ {r \atop n+1} \right} \frac{z^r}{r!}. $$

Hence (23) holds for $n+1$.

Therefore, by induction on $n$, Eq. (23) is valid for all $n\ge0$. This completes the proof.

∎