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} $ 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?
 A: 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}
A: 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}$.
A: 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.
A: 
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.
