Sum of product of NB combinations

Question

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?

Answer 1

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}

Answer 2

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*}