There is a well known identity (the so called "Hockey-stick identity") asserting that:
$$\sum_{j=0}^m \binom{r+j}{j} = \binom{m+r+1}{r+1}$$
For some proofs see this.
I need to prove a kind of generalization, namely:
$$\sum_{j=0}^m \binom{r+j}{j}\binom{s+j}{j} = \sum_{j=0}^s \binom{r}{j}\binom{s}{j} \binom{m+r+s+1-j}{r+s+1}$$
For every $r\geq s\geq 0$.
Of course, setting $s=0$ in the latter gives the original identity. The problem is that I'm not being able to prove the second using the same ideas as those that work for the first one.
Any kind of help would be very appreciated.
Best Answer
$$ \begin{align} \sum_{j=0}^m\binom{r+j}{j}\binom{s+j}{j} &=\sum_{j=0}^m\sum_{k=0}^r\binom{r}{k}\color{#C00}{\binom{j}{k}\binom{s+j}{j}}\tag1\\ &=\sum_{j=0}^m\sum_{k=0}^r\binom{r}{k}\color{#C00}{\binom{s+k}{k}\binom{s+j}{s+k}}\tag2\\ &=\sum_{k=0}^r\binom{r}{k}\binom{s+k}{k}\binom{s+m+1}{s+k+1}\tag3\\ &=\sum_{k=0}^r\sum_{j=0}^s\color{#C00}{\binom{r}{k}}\binom{s}{j}\color{#C00}{\binom{k}{j}}\binom{s+m+1}{s+k+1}\tag4\\ &=\sum_{k=0}^r\sum_{j=0}^s\color{#C00}{\binom{r}{j}}\binom{s}{j}\color{#C00}{\binom{r-j}{k-j}}\binom{s+m+1}{s+k+1}\tag5\\ &=\sum_{j=0}^s\binom{r}{j}\binom{s}{j}\binom{m+r+s+1-j}{r+s+1}\tag6\\ \end{align} $$ Explanation:
$(1)$: Vandermonde's Identity: $\binom{r+j}{j}=\sum_k\binom{r}{k}\binom{j}{j-k}$
$(2)$: expand red binomial coefficients as ratios of factorials
$(3)$: sum in $j$ using the Hockey-Stick Identity
$(4)$: Vandermonde's Identity: $\binom{s+k}{k}=\sum_j\binom{s}{j}\binom{k}{k-j}$
$(5)$: expand red binomial coefficients as ratios of factorials
$(6)$: $\binom{r-j}{k-j}=\binom{r-j}{r-k}$, then Vandermonde's Identity