TAOCP 1.2.9 Exercise 24

Exercise 24. [M22] Prove that, if $G(z)$ is any generating function, we have

$$ \sum_k \binom{m}{k}[z^{,n-k}]G(z)^k = z^n^m. $$

Evaluate both sides of this identity when $G(z)$ is (a) $1/(1-z)$; (b) $(e^z-1)/z$.

Verified: yes
Solve time: 54s

Solution

We start from the right-hand side and extract the coefficient of $z^n$.

$$ (1+zG(z))^m = \sum_{k=0}^m \binom{m}{k} (zG(z))^k = \sum_{k=0}^m \binom{m}{k} z^k G(z)^k. $$

For fixed $k$, the term $z^k G(z)^k$ has coefficient of $z^n$ equal to the coefficient of $z^{n-k}$ in $G(z)^k$. Hence

$$ z^n^m = \sum_{k=0}^m \binom{m}{k} [z^{n-k}]G(z)^k. $$

This matches the left-hand side term-by-term, so the identity holds:

$$ \sum_k \binom{m}{k}[z^{n-k}]G(z)^k = z^n^m. $$

This completes the proof. ∎

Since

$$ G(z)^k = (1-z)^{-k} = \sum_{j\ge 0} \binom{k+j-1}{j} z^j, $$

we obtain

$$ [z^{n-k}]G(z)^k = \binom{k+(n-k)-1}{n-k} = \binom{n-1}{n-k}. $$

Hence the left-hand side becomes

$$ \sum_k \binom{m}{k}\binom{n-1}{n-k}. $$

On the right-hand side,

$$ (1+zG(z))^m = \left(1+\frac{z}{1-z}\right)^m = (1-z)^{-m}. $$

Therefore

$$ z^n^m = z^n^{-m} = \binom{m+n-1}{n}. $$

Thus

$$ \sum_k \binom{m}{k}\binom{n-1}{n-k} = \binom{m+n-1}{n}. $$

Write

$$ G(z)^k = \frac{(e^z-1)^k}{z^k}. $$

Using the shifting rule,

$$ [z^{n-k}]G(z)^k = [z^{n-k}]\frac{(e^z-1)^k}{z^k} = z^n^k. $$

Hence the left-hand side equals

$$ \sum_k \binom{m}{k}z^n^k = [z^n]\sum_k \binom{m}{k}(e^z-1)^k. $$

By the binomial theorem,

$$ \sum_k \binom{m}{k}(e^z-1)^k = (1+(e^z-1))^m = e^{mz}. $$

Thus the left-hand side is

$$ [z^n]e^{mz} = \frac{m^n}{n!}. $$

On the right-hand side,

$$ (1+zG(z))^m = \left(1+z\cdot\frac{e^z-1}{z}\right)^m = e^{mz}, $$

so the same coefficient is obtained:

$$ z^n^m = \frac{m^n}{n!}. $$

This completes the evaluation. ∎

(a)

$$ \sum_k \binom{m}{k}\binom{n-1}{n-k} = \binom{m+n-1}{n}. $$

(b)

$$ \sum_k \binom{m}{k}[z^{n-k}]G(z)^k = \frac{m^n}{n!}. $$