TAOCP 1.2.6 Exercise 29

Exercise 29. [M20] Show that Eq. (34) is just a special case of the general identity proved in exercise 1.2.3--33.

Verified: no
Solve time: -

Solution

Equation (34) states that for integers $r \ge 0$ and $m$,

$$ \sum_k \binom{r}{k}(-1)^{r-k}k^m = \begin{cases} 0, & 0 \le m < r,\ r!, & m=r. \end{cases} \tag{34} $$

The general identity proved in exercise 1.2.3, 33 is

$$ \sum_{j=1}^{n} \frac{x_j^m} {\prod_{\substack{1\le k\le n\k\ne j}} (x_j-x_k)} = \begin{cases} 0, & 0\le m<n-1,\ 1, & m=n-1. \end{cases} $$

Take

$$ n=r+1, \qquad x_j=j-1 \qquad (1\le j\le r+1). $$

Thus the numbers are

$$ x_1=0,\ x_2=1,\ \ldots,\ x_{r+1}=r. $$

For $x_j=k$, where $0\le k\le r$, the denominator becomes

$$ \prod_{\substack{0\le i\le r\ i\ne k}}(k-i). $$

Separating the factors with $i<k$ and $i>k$ gives

$$ \prod_{0\le i<k}(k-i) \prod_{k<i\le r}(k-i) = k!, (-1)^{r-k}(r-k)!. $$

Hence

$$ \frac{k^m} {\prod_{i\ne k}(k-i)} = \frac{k^m} {k!(-1)^{r-k}(r-k)!}. $$

Substituting into the identity of exercise 1.2.3, 33 yields

$$ \sum_{k=0}^{r} \frac{k^m} {k!(-1)^{r-k}(r-k)!} = \begin{cases} 0, & 0\le m<r,\ 1, & m=r. \end{cases} $$

Multiplying both sides by $r!$ and using equation (5),

$$ \frac{r!}{k!(r-k)!} = \binom{r}{k}, $$

we obtain

$$ \sum_{k=0}^{r} \binom{r}{k} (-1)^{r-k} k^m = \begin{cases} 0, & 0\le m<r,\ r!, & m=r. \end{cases} $$

This is exactly Eq. (34). Therefore Eq. (34) is a special case of the identity proved in exercise 1.2.3, 33.

This completes the proof.

∎