TAOCP 1.2.6 Exercise 31

Exercise 31. [M20] Evaluate

$$ \sum_k \binom{m-r+s}{k}\binom{n+r-s}{n-k}\binom{r+k}{m+n} $$

in terms of $r$, $s$, $m$, and $n$, given that $m$ and $n$ are integers. Begin by replacing

$$ \binom{r+k}{m+n} $$

by $\sum_j \binom{r}{m+n-j}\binom{k}{j}$.

Verified: no
Solve time: -

Solution

Let

$$ S=\sum_k \binom{m-r+s}{k}\binom{n+r-s}{n-k}\binom{r+k}{m+n}. $$

The exercise directs us to expand the last factor by Vandermonde's convolution:

$$ \binom{r+k}{m+n} = \sum_j \binom{r}{m+n-j}\binom{k}{j}. $$

Hence

$$ S = \sum_k \binom{m-r+s}{k} \binom{n+r-s}{n-k} \sum_j \binom{r}{m+n-j}\binom{k}{j}. $$

Interchanging the order of summation gives

$$ S = \sum_j \binom{r}{m+n-j} \sum_k \binom{m-r+s}{k} \binom{k}{j} \binom{n+r-s}{n-k}. $$

Now use the identity

$$ \binom{a}{k}\binom{k}{j} = \binom{a}{j}\binom{a-j}{k-j}, $$

which follows immediately from Eq. (5):

$$ \binom{a}{k}\binom{k}{j} = \frac{a!}{k!(a-k)!}\frac{k!}{j!(k-j)!} = \frac{a!}{j!(a-j)!}\frac{(a-j)!}{(k-j)!(a-k)!}. $$

With $a=m-r+s$, we obtain

$$ \binom{m-r+s}{k}\binom{k}{j} = \binom{m-r+s}{j} \binom{m-r+s-j}{k-j}. $$

Therefore

$$ S = \sum_j \binom{r}{m+n-j} \binom{m-r+s}{j} \sum_k \binom{m-r+s-j}{k-j} \binom{n+r-s}{n-k}. $$

Put $i=k-j$. Then

$$ \sum_k \binom{m-r+s-j}{k-j} \binom{n+r-s}{n-k} = \sum_i \binom{m-r+s-j}{i} \binom{n+r-s}{n-j-i}. $$

By Vandermonde's convolution,

$$ \sum_i \binom{a}{i}\binom{b}{c-i} = \binom{a+b}{c}, $$

so here

$$ \sum_i \binom{m-r+s-j}{i} \binom{n+r-s}{n-j-i} = \binom{m+n-j}{n-j}. $$

Hence

$$ S = \sum_j \binom{r}{m+n-j} \binom{m-r+s}{j} \binom{m+n-j}{n-j}. $$

Now apply Eq. (5):

$$ \binom{r}{m+n-j}\binom{m+n-j}{n-j} = \frac{r!}{(m+n-j)!(r-m-n+j)!} \frac{(m+n-j)!}{(n-j)!m!} $$

$$= \frac{r!}{m!(n-j)!(r-m-n+j)!}.$$

But

$$ \binom{r}{m} \binom{r-m}{n-j} = \frac{r!}{m!(r-m)!} \frac{(r-m)!}{(n-j)!(r-m-n+j)!}, $$

therefore

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

Substituting,

$$ S = \binom{r}{m} \sum_j \binom{m-r+s}{j} \binom{r-m}{n-j}. $$

A second application of Vandermonde's convolution yields

$$ \sum_j \binom{m-r+s}{j} \binom{r-m}{n-j} = \binom{s}{n}. $$

Consequently,

$$ S = \binom{r}{m}\binom{s}{n}. $$

Therefore the value of the sum is

$$ \boxed{\binom{r}{m}\binom{s}{n}}. $$

∎