TAOCP 1.2.6 Exercise 22

Let S=\sum_{i=0}^{s}\binom{r+i}{r}\binom{t+s-i}{t}, \qquad s=(n-1)r+nt.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.6: Binomial Coefficients

Exercise 22. [M20] Prove Eq. (26) for the special case $s=(n-1)r+nt$.

Verified: yes
Solve time: 4m15s

Let

$$ S=\sum_{i=0}^{s}\binom{r+i}{r}\binom{t+s-i}{t}, \qquad s=(n-1)r+nt. $$

We shall prove, using only identity (11),

$$ \sum_{m=0}^{M}\binom{p+m}{p} =\binom{p+M+1}{p+1}, \tag{11} $$

that

$$ S=\binom{r+t+s+1}{r+t+1}. $$

Substituting $s=(n-1)r+nt$ will then give the required special case of Eq. (26).

From (11),

$$ \binom{r+i}{r} =\sum_{k=0}^{i}\binom{r-1+k}{r-1}. $$

Substituting into $S$ and reversing the order of summation,

$$ \begin{aligned} S &=\sum_{i=0}^{s} \left(\sum_{k=0}^{i}\binom{r-1+k}{r-1}\right) \binom{t+s-i}{t} \ &=\sum_{k=0}^{s}\binom{r-1+k}{r-1} \sum_{i=k}^{s}\binom{t+s-i}{t}. \end{aligned} $$

Let $j=s-i$. Then $j$ runs from $0$ to $s-k$, so by (11),

$$ \sum_{i=k}^{s}\binom{t+s-i}{t} = \sum_{j=0}^{s-k}\binom{t+j}{t} = \binom{t+s-k+1}{t+1}. $$

Hence

$$ S = \sum_{k=0}^{s} \binom{r-1+k}{r-1} \binom{t+s-k+1}{t+1}. \tag{1} $$

Now define, for $m=0,1,\dots,r$,

$$ S_m = \sum_{k=0}^{s} \binom{r-m+k}{,r-m,} \binom{t+s-k+m}{,t+m,}. $$

Equation (1) states that $S=S_1$, while the original sum is $S_0$.

We claim that

$$ S_m=S_{m+1} \qquad (0\le m<r). $$

Indeed, using

$$ \binom{r-m+k}{r-m} = \sum_{j=0}^{k} \binom{r-m-1+j}{r-m-1}, $$

which is another instance of (11), we obtain

$$ \begin{aligned} S_m &= \sum_{k=0}^{s} \left( \sum_{j=0}^{k} \binom{r-m-1+j}{r-m-1} \right) \binom{t+s-k+m}{t+m} \ &= \sum_{j=0}^{s} \binom{r-m-1+j}{r-m-1} \sum_{k=j}^{s} \binom{t+s-k+m}{t+m}. \end{aligned} $$

Applying (11) to the inner sum,

$$ \sum_{k=j}^{s} \binom{t+s-k+m}{t+m} = \sum_{\ell=0}^{s-j} \binom{t+\ell+m}{t+m} = \binom{t+s-j+m+1}{t+m+1}. $$

Therefore

$$ S_m = \sum_{j=0}^{s} \binom{r-m-1+j}{r-m-1} \binom{t+s-j+m+1}{t+m+1} = S_{m+1}. $$

Thus

$$ S=S_0=S_1=\cdots=S_r. $$

For $m=r$,

$$ S_r = \sum_{k=0}^{s} \binom{k}{0} \binom{t+s-k+r}{t+r} = \sum_{k=0}^{s} \binom{t+s-k+r}{t+r}. $$

Replacing $k$ by $s-k$,

$$ S_r = \sum_{k=0}^{s} \binom{t+r+k}{t+r}. $$

A final application of (11) gives

$$ S_r = \binom{t+r+s+1}{t+r+1}. $$

Hence

$$ S = \binom{r+t+s+1}{r+t+1}. \tag{2} $$

Now substitute

$$ s=(n-1)r+nt. $$

Then

$$ r+t+s+1 = r+t+(n-1)r+nt+1 = nr+(n+1)t+1. $$

Therefore (2) becomes

$$ \boxed{ \sum_{i=0}^{(n-1)r+nt} \binom{r+i}{r} \binom{t+(n-1)r+nt-i}{t} = \binom{nr+(n+1)t+1}{r+t+1} }. $$

This is exactly Eq. (26) specialized to the case $s=(n-1)r+nt$. ∎