TAOCP 1.2.6 Exercise 23
Equation (26) is the identity \sum_k \binom{r}{m+k}\binom{s}{n-k}\binom{k}{t} = \binom{r+s-t}{m+n-t}\binom{r}{m+t},
Section 1.2.6: Binomial Coefficients
Exercise 23. [M13] Assuming that Eq. (26) holds for $(r,s,t,n)$ and $(r,s-t,t,n-1)$, prove it for $(r,s+1,t,n)$.
Verified: yes
Solve time: 33s
Solution
Equation (26) is the identity
$$ \sum_k \binom{r}{m+k}\binom{s}{n-k}\binom{k}{t} = \binom{r+s-t}{m+n-t}\binom{r}{m+t}, $$
where the summation extends over all integers $k$.
Assume that Eq. (26) holds for $(r,s,t,n)$ and also for $(r,s-t,t,n-1)$. We must prove it for $(r,s+1,t,n)$.
Consider
$$ \sum_k \binom{r}{m+k}\binom{s+1}{n-k}\binom{k}{t}. $$
By the addition formula (9),
$$ \binom{s+1}{n-k} = \binom{s}{n-k} + \binom{s}{n-k-1}. $$
Hence
$$ \sum_k \binom{r}{m+k}\binom{s+1}{n-k}\binom{k}{t} = \sum_k \binom{r}{m+k}\binom{s}{n-k}\binom{k}{t} + \sum_k \binom{r}{m+k}\binom{s}{n-k-1}\binom{k}{t}. $$
The first sum is evaluated by the hypothesis for $(r,s,t,n)$:
$$ \sum_k \binom{r}{m+k}\binom{s}{n-k}\binom{k}{t} = \binom{r+s-t}{m+n-t}\binom{r}{m+t}. $$
In the second sum, replace $n$ by $n-1$ in Eq. (26). This gives
$$ \sum_k \binom{r}{m+k}\binom{s}{n-k-1}\binom{k}{t} = \binom{r+s-t}{m+n-1-t}\binom{r}{m+t}. $$
Therefore
$$ \sum_k \binom{r}{m+k}\binom{s+1}{n-k}\binom{k}{t} = \left( \binom{r+s-t}{m+n-t} + \binom{r+s-t}{m+n-1-t} \right)\binom{r}{m+t}. $$
Applying the addition formula (9) once more,
$$ \binom{r+s-t}{m+n-t} + \binom{r+s-t}{m+n-1-t} = \binom{r+s+1-t}{m+n-t}. $$
Hence
$$ \sum_k \binom{r}{m+k}\binom{s+1}{n-k}\binom{k}{t} = \binom{r+s+1-t}{m+n-t}\binom{r}{m+t}, $$
which is Eq. (26) for $(r,s+1,t,n)$.
This completes the proof.
∎