Sum of product of NB combinations While trying to solve the PMF of two independent NB random variables, I end up with a summation of the product of two combinations:
$$\sum_{j=0}^{k} {j+r-1 \choose j} {k-j+s-1 \choose k-j} $$
According to the textbook, it should be equal to
$$ {k+r+s-1 \choose k} $$
But how can the above summation be reduced to the single combination?
 A: There are two keys here. First of all, the binomaial coefficient $\binom{n}k$ can be extended to allow negative $n$ (or even complex $n$) by setting
$$
\binom{n}k\stackrel{\text{def}}{=}\frac{n(n-1)\cdots(n-k+1)}{k!}
$$
Importanly, with this generalization, the relation $(1+x)^n=\sum_{k=0}^\infty \binom{n}kx^k$ is still true even when $n$ is complex. 
When $n$ is negative, we can write this expression in terms of a regular binomial coefficient. If $n>0$, then
$$
\binom{-n}k=\frac{(-n)(-n-1)\cdots(-n-k+1)}{k!}=(-1)^k\frac{(n+k-1)\cdots(n+1)n}{k!}=(-1)^k\binom{n+k-1}{k}
$$
Therefore, your summation can be rewriten as
$$
\sum_{j=0}^k\binom{r+j-1}j\binom{s+k-j-1}{k-j}=\sum_{j=0}^k\binom{-r}j(-1)^j\binom{-s}{k-j}(-1)^{k-j}=(-1)^k\sum_{j=0}^k\binom{-r}j\binom{-s}{k-j}
$$
Note that this summation (without the $(-1)^k$) looks a lot like one side of Vandemonde's idenity, the only problem being that the upper indices are negative. Indeed, Vandemonde's identity is still true in this context: for any complex numbers $a$ and $b$, it is true that
$$
\binom{a+b}{k}
=\sum_{j=0}^k \binom{a}j\binom{b}{k-j}
$$
which can be proven by examing the coefficient of $x^k$ in both sides of the equation
$$
(1+x)^{a+b}=(1+x)^a(1+x)^b
$$
Therefore, you get
\begin{align}
\sum_{j=0}^k\binom{r+j-1}j\binom{s+k-j-1}{k-j}
&=(-1)^k\sum_{j=0}^k\binom{-r}j\binom{-s}{k-j}\\
&=(-1)^k\binom{-r-s}{k}\\
&=\binom{r+s+k-1}{k}
\end{align}
A: The number of solutions in non negative integers to the equation $$x_1+x_2+ \cdots + x_n = m$$ is $\binom{n+m-1}{m}$. This is easily seen as follows: any such solution is obtained by arranging $m$ $1s$ and $n-1$ $+$ signs in a row.
For any $j$, $0 \leq j \leq k$, consider the number of solutions in non negative integers to the equations
\begin{align*}
x_1+x_2 + \cdots + x_r &= j\\
y_1+y_2 + \cdots + y_s &= k-j
\end{align*}
We can get a solution of the equation
\begin{align*}
x_1 + x_2 + \cdots + x_r + y_1 + y_2 + \cdots + y_s = k
\end{align*}
from those solutions. Conversely from any solution to the above equation we can get a pair of solutions to the two equations for some $j$, $0 \leq j \leq k$. Hence 
\begin{align*}
\sum_{j=0}^k \binom{j+r-1}{j}\binom{k-j+s-1}{k-j} = \binom{k+r+s-1}{k}
\end{align*}
