TAOCP 1.2.6 Exercise 61

Section 1.2.6: Binomial Coefficients

Exercise 61. [M25] Evaluate the sum

$$ \sum_k \left[{n+1 \atop k+1}\right]\left{{k \atop m}\right}(-1)^{k-m}, $$

thereby obtaining a companion formula for Eq. (55).

Verified: no
Solve time: -

---

Solution

Let

$$ S=\sum_k \left[{n+1 \atop k+1}\right]\left{{k \atop m}\right}(-1)^{k-m}. $$

We seek a closed form for $S$.

The Stirling numbers of the first kind and second kind satisfy the inverse relations of Eq. (55):

$$ x^{\underline{n}} = \sum_k \left[{n \atop k}\right] (-1)^{,n-k}x^k, \qquad x^n = \sum_k \left{{n \atop k}\right} x^{\underline{k}}. $$

Apply the second formula with $n=k$:

$$ x^k = \sum_j \left{{k \atop j}\right} x^{\underline{j}}. $$

Multiply by $\left{n+1 \atop k+1}\right^k$ and sum over $k$:

$$ \sum_k \left[{n+1 \atop k+1}\right] (-1)^k x^k = \sum_k \left[{n+1 \atop k+1}\right] (-1)^k \sum_j \left{{k \atop j}\right} x^{\underline{j}}. $$

Interchanging the order of summation gives

$$ \sum_k \left[{n+1 \atop k+1}\right] (-1)^k x^k = \sum_j \left( \sum_k \left[{n+1 \atop k+1}\right] \left{{k \atop j}\right} (-1)^k \right) x^{\underline{j}}. $$

The coefficient of $x^{\underline{m}}$ is therefore

$$ \sum_k \left[{n+1 \atop k+1}\right] \left{{k \atop m}\right} (-1)^k. \tag{1} $$

Now evaluate the left-hand side. By the first inversion formula with $n+1$ in place of $n$,

$$ x^{\underline{n+1}} = \sum_r \left[{n+1 \atop r}\right] (-1)^{,n+1-r}x^r. $$

Replace $r$ by $k+1$:

$$ x^{\underline{n+1}} = \sum_k \left[{n+1 \atop k+1}\right] (-1)^{,n-k}x^{k+1}. $$

Divide by $x$:

$$ (x-1)^{\underline{n}} = \frac{x^{\underline{n+1}}}{x} = \sum_k \left[{n+1 \atop k+1}\right] (-1)^{,n-k}x^k. $$

Hence

$$ \sum_k \left[{n+1 \atop k+1}\right] (-1)^k x^k = (-1)^n(x-1)^{\underline{n}}. $$

Since

$$ (x-1)^{\underline{n}} = x^{\underline{n}}-n,x^{\underline{n-1}} $$

(the factorization

$,(x-1)^{\underline{n}}

=(x-1)(x-2)\cdots(x-n),$ differs from

$,x^{\underline{n}}

=x(x-1)\cdots(x-n+1),$ by replacing the factor $x$ with $x-n$), we obtain

$$ (-1)^n(x-1)^{\underline{n}} = (-1)^n x^{\underline{n}} + (-1)^{n+1}n,x^{\underline{n-1}}. $$

Therefore the coefficient of $x^{\underline{m}}$ equals

$$ (-1)^n\delta_{mn} + (-1)^{n+1}n,\delta_{m,n-1}. \tag{2} $$

Comparing (1) and (2),

$$ \sum_k \left[{n+1 \atop k+1}\right] \left{{k \atop m}\right} (-1)^k = (-1)^n\delta_{mn} + (-1)^{n+1}n,\delta_{m,n-1}. $$

Multiply by $(-1)^m$ to obtain the desired sum:

$$ S = \sum_k \left[{n+1 \atop k+1}\right] \left{{k \atop m}\right} (-1)^{k-m} = (-1)^{n-m}\delta_{mn} + (-1)^{n+1-m}n,\delta_{m,n-1}. $$

Since only the cases $m=n$ and $m=n-1$ contribute,

$$ S= \delta_{mn}-n,\delta_{m,n-1}. $$

Thus the companion formula to Eq. (55) is

$$ \boxed{ \sum_k \left[{n+1 \atop k+1}\right] \left{{k \atop m}\right} (-1)^{k-m} = \delta_{mn}-n,\delta_{m,n-1} }. $$

This completes the proof.

∎