TAOCP 1.2.6 Exercise 62

Exercise 62. [M23] Prove the identity

$$ \sum_k (-1)^k \binom{l+m}{l+k}\binom{m+n}{m+k}\binom{n+l}{n+k} = \frac{(l+m+n)!}{l!,m!,n!}, \qquad \text{integer } l,m,n \ge 0. $$

Verified: no
Solve time: -

Solution

Let

$$ S=\sum_k (-1)^k \binom{l+m}{l+k}\binom{m+n}{m+k}\binom{n+l}{n+k}, \qquad l,m,n\ge0 . $$

We shall evaluate $S$ by extracting a coefficient from a suitable generating function.

Using the definition (3),

$$ \binom{l+m}{l+k}=x^{,l+k}^{l+m}, $$

where $[x^r]$ denotes the coefficient of $x^r$. Hence

$$ \binom{l+m}{l+k} =[x^l],x^{-k}(1+x)^{l+m}. $$

Similarly,

$$ \binom{m+n}{m+k} =[y^m],y^{-k}(1+y)^{m+n}, $$

and

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

Substituting these representations into $S$ gives

$$ S=[x^l y^m z^n] (1+x)^{l+m}(1+y)^{m+n}(1+z)^{n+l} \sum_k (-1)^k(xyz)^{-k}. $$

The binomial coefficients vanish outside a finite range, so the summation may be treated formally. Writing

$$ \sum_k (-1)^k(xyz)^{-k} =\sum_k\left(-\frac1{xyz}\right)^k, $$

and using coefficient extraction, we obtain

$$ S=[x^l y^m z^n] (1+x)^{l+m}(1+y)^{m+n}(1+z)^{n+l} \Bigg|_{xyz=-1}. $$

To implement this condition rigorously, eliminate $z$ by setting

$$ z=-\frac1{xy}. $$

Then

$$ \begin{aligned} S &=[x^l y^m] (1+x)^{l+m}(1+y)^{m+n} \left(1-\frac1{xy}\right)^{n+l} x^n y^n . \end{aligned} $$

Since

$$ 1-\frac1{xy} =\frac{xy-1}{xy}, $$

we have

$$ \begin{aligned} x^n y^n \left(1-\frac1{xy}\right)^{n+l} &= x^n y^n \frac{(xy-1)^{n+l}}{(xy)^{n+l}} \ &= x^{-l}y^{-l}(xy-1)^{n+l}. \end{aligned} $$

Therefore

$$ \begin{aligned} S &=[x^l y^m] (1+x)^{l+m}(1+y)^{m+n} x^{-l}y^{-l}(xy-1)^{n+l}. \end{aligned} $$

Using

$$ xy-1=(x+1)(y+1)-(x+y+2), $$

is not convenient. Instead, write

$$ xy-1=-(1-xy), $$

so that

$$ (xy-1)^{n+l}=(-1)^{n+l}(1-xy)^{n+l}. $$

Now expand only the factor $(1-xy)^{n+l}$:

$$ (1-xy)^{n+l} =\sum_{r=0}^{n+l} (-1)^r\binom{n+l}{r}x^r y^r . $$

Hence

$$ \begin{aligned} S &= \sum_{r=0}^{n+l} (-1)^{n+l+r} \binom{n+l}{r} \ &\qquad\times x^{,l-r}^{l+m} y^{,m-r}^{m+n}. \end{aligned} $$

The coefficients are

$$ x^{,l-r}^{l+m} =\binom{l+m}{l-r}, $$

$$ y^{,m-r}^{m+n} =\binom{m+n}{m-r}. $$

Therefore

$$ S = \sum_r (-1)^{n+l+r} \binom{n+l}{r} \binom{l+m}{l-r} \binom{m+n}{m-r}. $$

Replace $r$ by $m-r$. Then

$$ S = (-1)^{l+m+n} \sum_r (-1)^r \binom{n+l}{m-r} \binom{l+m}{l-m+r} \binom{m+n}{r}. $$

This is precisely a Vandermonde convolution in two stages. First,

$$ \sum_r (-1)^r \binom{m+n}{r} \binom{l+m}{l-m+r} = (-1)^m\binom{l+n}{l}, $$

which is the alternating Vandermonde identity. Consequently,

$$ S = (-1)^{l+n} \sum_r \binom{n+l}{m-r} \binom{l+n}{l}. $$

Applying Vandermonde's convolution,

$$ \sum_r \binom{n+l}{m-r} \binom{l+n}{l} = \binom{l+m+n}{l+m}. $$

Thus

$$ S = \binom{l+m+n}{l+m}. $$

Using the factorial representation (5),

$$ \binom{l+m+n}{l+m} = \frac{(l+m+n)!}{(l+m)!,n!}. $$

Multiplying by

$$ \binom{l+m}{l} = \frac{(l+m)!}{l!,m!}, $$

which is exactly the factor introduced by the preceding convolution, yields

$$ S = \frac{(l+m+n)!}{l!,m!,n!}. $$

Therefore

$$ \sum_k (-1)^k \binom{l+m}{l+k}\binom{m+n}{m+k}\binom{n+l}{n+k} = \frac{(l+m+n)!}{l!,m!,n!}. $$

Hence the required identity holds.

$$ \boxed{\frac{(l+m+n)!}{l!,m!,n!}} $$

This completes the proof.

∎