Prove an identity in a Combinatorics method

Question

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?

Answer 1

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$

Answer 2

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