TAOCP 1.2.9 Exercise 17
We seek the coefficients of \frac{1}{(1-z)^w} when expanded as a double power series in $z$ and $w$.
Section 1.2.9: Generating Functions
Exercise 17. [M25] What are the coefficients of $1/(1-z)^w$ if this function is expanded into a double power series in terms of both $z$ and $w$?
Verified: yes
Solve time: 50s
Solution
We seek the coefficients of
$$ \frac{1}{(1-z)^w} $$
when expanded as a double power series in $z$ and $w$. By the binomial theorem for general exponents (see Eq. (19)), we have
$$ (1+u)^r = \sum_{k \ge 0} \binom{r}{k} u^k. $$
Setting $u = -z$ and $r = -w$, we obtain
$$ (1-z)^{-w} = (1 + (-z))^{-w} = \sum_{k \ge 0} \binom{-w}{k} (-z)^k. $$
We now simplify the binomial coefficient. By definition,
$$ \binom{-w}{k} = \frac{(-w)(-w-1)\cdots(-w-k+1)}{k!} = \frac{(-1)^k w(w+1)\cdots(w+k-1)}{k!}. $$
Substituting back, we have
$$ (1-z)^{-w} = \sum_{k \ge 0} \frac{(-1)^k w(w+1)\cdots(w+k-1)}{k!}(-z)^k = \sum_{k \ge 0} \frac{w(w+1)\cdots(w+k-1)}{k!} z^k. $$
Hence the coefficient of $z^k$ is
$$ \frac{w(w+1)\cdots(w+k-1)}{k!}. $$
We now expand the numerator as a polynomial in $w$. Observe that
$$ w(w+1)\cdots(w+k-1) = \sum_{j=0}^{k} \left[{k \atop j}\right] w^j, $$
where $\left[{k \atop j}\right]$ denotes the Stirling numbers of the first kind (see Eq. (27)). Dividing by $k!$, we obtain
$$ \frac{w(w+1)\cdots(w+k-1)}{k!} = \sum_{j=0}^{k} \frac{\left[{k \atop j}\right]}{k!} w^j. $$
Combining these results, the double power series expansion of $(1-z)^{-w}$ is
$$ \frac{1}{(1-z)^w} = \sum_{k \ge 0} \sum_{j=0}^{k} \frac{\left[{k \atop j}\right]}{k!} w^j z^k. $$
Thus the coefficient of $w^j z^k$ is
$$ \frac{\left[{k \atop j}\right]}{k!}. $$
This completes the proof.
∎