# Proving the binomial identity $\sum_{j=0}^k {n \choose j}\cdot {m \choose k-j}={n+m \choose k}$ when $n,m$ are negative integers

What I'm really interested in is the identity: $$\displaystyle \sum_{j=0}^k {j+r-1 \choose j}\cdot {k-j +s-1 \choose k-j}={k+r+s-1 \choose k}$$

It arises in the proof of the convolution formula of two negative binomial Random Variables, for example.

What I know is the identity:$\displaystyle { j+r-1 \choose j} = {-r \choose j} (-1)^j$

Hence what I need to show is $$\displaystyle \sum_{j=0}^k {-r \choose j} \cdot {-s \choose k-j}={-r-s \choose k}$$ aka the binomial convolution formula for $m = -r, n = -s$ when $s$ and $r$ are positive intergers.

How do I do that?

Here is an answer based upon generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

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_{=0}^k\binom{-r}{j}(-1)^j\binom{-s}{k-j}(-1)^{k-j}\\ &=(-1)^k\sum_{j=0}^\infty[z^j](1+z)^{-r}[u^{k-j}](1+u)^{-s}\tag{1}\\ &=(-1)^k[u^k](1+u)^{-s}\sum_{j=0}^\infty u^j[z^j](1+z)^{-r}\tag{2}\\ &=(-1)^k[u^k](1+u)^{-s}(1+u)^{-r}\tag{3}\\ &=(-1)^k[u^k](1+u)^{-r-s}\\ &=(-1)^k\binom{-r-s}{k}\\ &\color{blue}{=\binom{k+r+s-1}{k}} \end{align*} and the Chu-Vandermonde identity follows.

Comment:

• In (1) we apply the coefficient of operator twice and set the upper limit of the series to $\infty$ without changing anything since we are adding zeros only.

• In (2) we use the linearity of the coefficient of operator and apply the rule $[z^{p}]z^qA(z)=[z^{p-q}]A(z)$.

• In (3) we apply the substitution rule of the coefficient of operator with $u=z$
\begin{align*} A(u)=\sum_{j=0}^\infty a_j u^j=\sum_{j=0}^\infty u^j [z^j]A(z) \end{align*}

For instance, you can use induction on $n$ to show that if $p_{n}(x)$ is the polynomial: $$p_{0}(x)=1$$ $$p_{n}(x)=(x)_n=x(x-1)\cdots(x-n+1),\ \text{for each}\ n\geq 1$$

then

$$p_{n}(x+y)=\sum_{k=0}^{n}{n\choose k}p_{k}(x)p_{n-k}(y)$$

Your identity is equivalent to the one above.

Recall that if $n\in\mathbb{N}$ and $x$ is a variable you can write:

$${x\choose n}=\frac{(x)_{n}}{n!}$$

The falling factorial is a family of polynomials of binomial type like the fmailies $f_{n}(x)=x^n$, $g_{n}(x)=x(x+1)\cdots(x+n-1)$, Abel polynomials, Touchard polynomials.