Prove an identity in a Combinatorics method It is a combinatorics proof. Anyone has any idea on how to prove 
$$\sum \limits_{i=0}^{l} \sum\limits_{j=0}^i (-1)^j {m-i\choose m-l} {n \choose j}{m-n \choose i-j} = 2^l {m-n \choose l}\;$$
We need to prove this equation holds for all $l$.
I know that $\sum {n \choose j}{m-n \choose i-j}$ equals to ${m \choose i}$ but has no idea if there is a $(-1)^j$, it seems like a PIE but actually not....
Could anyone help me move forward in the process?
 A: It   is convenient  to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. We   can write    this way
\begin{align*}
[z^m](1+z)^n=\binom{n}{m}\tag{1}
\end{align*}

We obtain
  \begin{align*}
\sum_{i=0}^l&\sum_{j=0}^i(-1)^j\binom{m-i}{m-l}\binom{n}{j}\binom{m-n}{i-j}\\
&=\sum_{i=0}^l\binom{m-i}{m-l}\sum_{j=0}^\infty(-1)^j[z^j](1+z)^n[u^{i-j}](1+u)^{m-n}\tag{2}\\
&=\sum_{i=0}^l\binom{m-i}{m-l}[u^i](1+u)^{m-n}\sum_{j=0}^{\infty}(-1)^ju^j[z^j](1+z)^n\tag{3}\\
&=\sum_{i=0}^l\binom{m-i}{m-l}[u^i](1+u)^{m-n}(1-u)^n\tag{4}\\
&=\sum_{i=0}^{\infty}[z^{m-l}](1+z)^{m-i}[u^i](1+u)^{m-n}(1-u)^n\tag{5}\\
&=[z^{m-l}](1+z)^m\sum_{i=0}^\infty(1+z)^{-i}[u^i](1+u)^{m-n}(1-u)^n\tag{6}\\
&=[z^{m-l}](1+z)^m\left(1+\frac{1}{1+z}\right)^{m-n}\left(1-\frac{1}{1+z}\right)^n\tag{7}\\
&=[z^{m-l}](1+z)^m\cdot\frac{(2+z)^{m-n}}{(1+z)^{m-n}}\cdot\frac{z^n}{(1+z)^n}\\
&=[z^{m-n-l}](2+z)^{m-n}\\
&=[z^{m-n-l}]\sum_{j=0}^{m-n}\binom{m-n}{j}2^jz^{m-n-j}\tag{8}\\
&=2^l\binom{m-n}{l}
\end{align*}

Comment:


*

*In (2) we apply (1) to the binomial coefficients of the inner series and set the upper limit of the index $j$ to $\infty$ without changing anything since we add only zeros.

*In (3) we use the linearity of the coefficient of operator, do some rearrangements to prepare for the next step and use the rule
\begin{align*}
[u^{p-q}]P(u)=[u^p]u^qP(u)
\end{align*}

*In (4) we apply the substitution rule
\begin{align*}
A(u)=\sum_{j=0}^\infty a_ju^j=\sum_{j=0}^\infty u^j[z^j]A(z)\\
\end{align*}

*In (5) we apply (1) to the binomial coefficient of the first series

*In (6) we do again some rearrangement similar to (3)

*In (7) we apply the substitution rule again

*In (8) we select the index $j=l$ to obtain the term with power $m-n-l$
A: Suppose we seek to verify that
$$\sum_{p=0}^l\sum_{q=0}^p (-1)^q
{m-p\choose m-l} {n\choose q} {m-n\choose p-q}
= 2^l {m-n\choose l}$$
where $m\ge n$ and $m-n\ge l.$
This is
$$\sum_{p=0}^l {m-p\choose m-l} \sum_{q=0}^p (-1)^q
{n\choose q} {m-n\choose p-q}.$$
Now introduce the integral
$${m-n\choose p-q} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{p-q+1}} (1+z)^{m-n} \; dz.$$
Note that  this vanishes when $q\gt p$  so we may extend  the range of
$q$ to infinity, getting for the sum
$$\sum_{p=0}^l {m-p\choose m-l}
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{p+1}} (1+z)^{m-n} 
\sum_{q\ge 0} (-1)^q
{n\choose q} z^q
\; dz
\\ = \sum_{p=0}^l {m-p\choose l-p}
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{p+1}} (1+z)^{m-n} 
(1-z)^n
\; dz.$$
Introduce furthermore
$${m-p\choose l-p} =
\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{l-p+1}} (1+w)^{m-p} \; dw.$$
This too vanishes when $p\gt l$ so we may extend $p$ to infinity, getting
$$\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{l+1}} (1+w)^{m} 
\\ \times \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z} (1+z)^{m-n} 
(1-z)^n
\sum_{p\ge 0} \frac{w^p}{z^p} \frac{1}{(1+w)^p}
\; dz
\; dw.$$
The geometric series converges when $|w/z/(1+w)|\lt 1.$ We get
$$\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{l+1}} (1+w)^{m} 
\\ \times \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z} (1+z)^{m-n} 
(1-z)^n
\frac{1}{1-w/z/(1+w)}
\; dz
\; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{l+1}} (1+w)^{m} 
\\ \times \frac{1}{2\pi i}
\int_{|z|=\epsilon}
(1+z)^{m-n} 
(1-z)^n
\frac{1}{z-w/(1+w)}
\; dz
\; dw.$$
Now from the convergence we  have $|w/(1+w)|<|z|$ which means the pole
at $z=w/(1+w)$  is inside  the contour $|z|=\epsilon.$  Extracting the
residue yields (the pole at zero has disappeared)
$$\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{l+1}} (1+w)^{m} 
\left(1+\frac{w}{1+w}\right)^{m-n}
\left(1-\frac{w}{1+w}\right)^n
\; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{l+1}}
(1+2w)^{m-n}
\; dw
\\ = 2^l {m-n\choose l}.$$
