Sum of products of binomial coefficients: $ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} = \binom{n}{j} $

Question

In a proof I've come across the following identity:

$$ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} = \binom{n}{j} $$

I see that it's right, when plugging in numbers, but I don't see the algebraic or combinatorial proof behind it. Can anyone help me with that?

Answer 1

Of course one only needs to consider only $M\le j$. Rewrite the identity as

$$\sum^{n-j}_{l=0}\binom{M-1+l}{M-1}\binom{n-M-l}{j-M}=\binom{n}{j}.$$

The RHS suggests that one should look at how many sequence $a_1<a_2<\cdots <a_j$ can be chosen from $\{1,2,\cdots,n\}$ differently.

$a_M$ can only be in $\{M,M+1,\cdots, n-j+M\}$. For each value $l+M$ of $a_M$, there are $\binom{M-1+l}{M-1}$ choices of $a_1<\cdots<a_{M-1}$ and $\binom{n-M-l}{j-M}$ choices of $a_{M+1}<\cdots<a_{j}$.

Answer 2

This is an algebraic proof of the identity above. First, recall that $$\frac{1}{(1-x)^r}=\sum_{n \ge 0}\binom{n+r-1}{r-1}x^n$$ Let $N=n-j$ to simplify matters. The generating function of this sum is \begin{align} \sum_{N \ge 0}\sum^{N}_{k=0}\binom{k+m-1}{m-1}\binom{N+j-m-k}{j-m}x^N &=\sum_{k \ge 0}\binom{k+m-1}{m-1}x^k\sum_{N \ge 0}\binom{N+j-m}{j-m}x^N\\ &=\frac{1}{(1-x)^m(1-x)^{j-m+1}}\\ &=\frac{1}{(1-x)^{j+1}} \end{align} Extract the coefficient. \begin{align} \sum^{N}_{k=0}\binom{k+m-1}{m-1}\binom{n+j-m-k}{j-m} &=[x^N]\frac{1}{(1-x)^{j+1}}\\ &=\binom{N+j}{j}\\ &=\binom{n}{j}\\ \end{align}

Answer 3

A similar technique to what has already been presented uses basic complex variables.

Suppose we seek to evaluate $$\sum_{q=0}^{n-j} {q+M-1\choose M-1} {n-M-q\choose n-j-q}$$ where $M\le j.$

Start from $${n-M-q\choose n-j-q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-j-q+1}} (1+z)^{n-M-q} \; dz.$$

This yields the following integral for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{q=0}^{n-j} {q+M-1\choose M-1} \frac{1}{z^{n-j-q+1}} (1+z)^{n-M-q} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-M}}{z^{n-j+1}} \sum_{q=0}^{n-j} {q+M-1\choose M-1} \frac{z^q}{(1+z)^q} \; dz.$$

Now when $q> n-j$ we have $n-j-q+1 < 1$ so the pole at zero of the defining integral disappears. There may or may not be a pole at minus one but it is not inside the contour. This means we can extend the summation to infinity, getting

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-M}}{z^{n-j+1}} \sum_{q=0}^\infty {q+M-1\choose M-1} \frac{z^q}{(1+z)^q} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-M}}{z^{n-j+1}} \frac{1}{(1-z/(1+z))^M} \;dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n-j+1}} \frac{1}{(1+z-z)^M} \;dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n-j+1}} \; dz.$$

This integral can be evaluated by inspection and we get $$[z^{n-j}] (1+z)^n = {n\choose n-j} = {n\choose j},$$ which proves the claim.

A trace as to when this method appeared on MSE and by whom starts at this MSE link.

Answer 4

Just for seeing an elementary one:

$$ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} =\sum_{l=0}^{n-j}\left(-1\right)^{l} \binom{-M}{l} \left(-1\right)^{n-j-l} \binom{-j+M-1}{n-j-l} $$ $$=\left(-1\right)^{n-j} \sum_{l=0}^{n-j}\binom{-M}{l} \binom{-j+M-1}{n-j-l}$$ $$=\left(-1\right)^{n-j}\binom{-j-1}{n-j}=\binom{n}{n-j}=\binom{n}{j}$$

Hence we showed that:

$$\bbox[5px,border:2px solid #00A000]{ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} =\binom{n}{j}}$$

As desired.