Proof of product summation of binomial coefficients

Question

when I try to proof the sum of two independent negative binomial distribution to be negative binomial, I end up with how to proof the following identity. I try the induction but after I rearrange the terms and use C(n, m)=C(n-1,m-1)+C(n-1,m), it still not completely finish the proof. could you please give me some hint? Thank you.

Proof

$$\sum_{j=0}^k\binom{j+r-1}{j}\cdot\binom{k-j+s-1}{k-j} = \binom{k+r+s-1}{k}$$

Source.

Answer 1

Here we have a Chu-Vandermonde identity in disguise.

We obtain \begin{align*} \color{blue}{\sum_{j=0}^k}&\color{blue}{\binom{j+r-1}{j}\binom{k-j+s-1}{k-j}}\\ &=\sum_{j=0}^{k}\binom{-r}{j}(-1)^j\binom{-s}{k-j}(-1)^{k-j}\tag{1}\\ &=\binom{-(r+s)}{k}(-1)^k\tag{2}\\ &\,\,\color{blue}{= \binom{r+s+k-1}{k}}\tag{3} \end{align*} and the claim follows.

Comment:

• In (1) we use the binomial identity $\binom{-n}{k}(-1)^k=\binom{n+k-1}{k}$ twice.

• In (2) we apply the Chu-Vandermonde identity .

• In (3) we apply the binomial identity from (1) again.