TAOCP 1.2.9 Exercise 4
Equation (21) states that if $x^{t+1}=x^t+z$ and $x=1$ when $z=0$, then x^r=\sum_{k\ge0}\binom{r-kt}{k}\frac{r}{r-kt}z^k.
Section 1.2.9: Generating Functions
Exercise 4. [M01] Explain why Eq. (19) is a special case of Eq. (21).
Verified: no
Solve time: -
Equation (21) states that if $x^{t+1}=x^t+z$ and $x=1$ when $z=0$, then
$$ x^r=\sum_{k\ge0}\binom{r-kt}{k}\frac{r}{r-kt}z^k. $$
Take $t=-1$. Then the defining equation becomes
$$ x^{0}=x^{-1}+z, $$
hence
$$ 1=\frac1x+z, \qquad\text{so}\qquad x=\frac1{1-z}. $$
Therefore
$$ x^r=(1-z)^{-r}. $$
Substituting $t=-1$ into Eq. (21) gives
$$ (1-z)^{-r} =\sum_{k\ge0}\binom{r+k}{k}\frac{r}{r+k}z^k. $$
Since
$$ \binom{r+k}{k}\frac{r}{r+k} =\frac{(r+k)(r+k-1)\cdots(r+1)}{k!}\cdot\frac{r}{r+k} =\frac{r(r+1)\cdots(r+k-1)}{k!} =\binom{r+k-1}{k}, $$
we obtain
$$ (1-z)^{-r} =\sum_{k\ge0}\binom{r+k-1}{k}z^k. $$
Replacing $r$ by $-r$ yields
$$ (1+z)^r =\sum_{k\ge0}\binom{r}{k}z^k, $$
which is Eq. (19). ∎