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.


  • 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$$


$$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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.