# Proof of the identity $\sum_{k=0}^{\min[p,q]}{p\choose k}{q\choose k}{n+k\choose p+q}={n\choose p}{n\choose q}$

Prove the identity: $$\sum_{k=0}^{\min[p,q]}{p\choose k}{q\choose k}{n+k\choose p+q}={n\choose p}{n\choose q}.$$

-
See George E Andrews, David M Bressoud, Identities in combinatorics III: Further aspects of ordered set sorting, Discrete Mathematics, Volume 49, Issue 3, May 1984, Pages 223--236 ( sciencedirect.com/science/article/pii/0012365X84901596 ) for combinatorial proofs. (Actually, see part I of this series.) – darij grinberg Jul 3 '15 at 13:16

\begin{align} \sum_k\binom{p}{k}\binom{q}{k}\binom{n+k}{p+q} &=\sum_{j,k}\binom{p}{k}\binom{q}{k}\binom{n}{p+q-j}\binom{k}{j}\tag{1}\\ &=\sum_{j,k}\binom{p}{k}\binom{n}{p+q-j}\binom{q}{j}\binom{q-j}{q-k}\tag{2}\\ &=\sum_{j}\binom{p+q-j}{q}\binom{n}{p+q-j}\binom{q}{j}\tag{3}\\ &=\sum_{j}\binom{n-q}{n-p-q+j}\binom{n}{q}\binom{q}{j}\tag{4}\\ &=\sum_{j}\binom{n-q}{p-j}\binom{n}{q}\binom{q}{j}\tag{5}\\ &=\binom{n}{p}\binom{n}{q}\tag{6} \end{align} Explanation

$(1)$ $\displaystyle\binom{n+k}{p+q}=\sum_j\binom{n}{p+q-j}\binom{k}{j}$

$(2)$ $\displaystyle\binom{q}{k}\binom{k}{j}=\binom{q}{j}\binom{q-j}{q-k}$

$(3)$ $\displaystyle\sum_k\binom{p}{k}\binom{q-j}{q-k}=\binom{p+q-j}{q}$

$(4)$ $\displaystyle\binom{p+q-j}{q}\binom{n}{p+q-j}=\binom{n-q}{n-p-q+j}\binom{n}{q}$

$(5)$ $\displaystyle\binom{n-q}{n-p-q+j}=\binom{n-q}{p-j}$

$(6)$ $\displaystyle\sum_j\binom{n-q}{p-j}\binom{q}{j}=\binom{n}{p}$

-
+1: This was the same approach I was trying to use, but I made an error when applying Identity (2) and got myself into a mess that didn't simplify. – Mike Spivey Jan 17 '13 at 17:46
Very nice. (This one word "Explanation" sort of spoils the fun of an answer containing "only" a calculation. Wouldn't a horizontal line do?) – Martin Jan 17 '13 at 19:20

Since $$[x^i] (1-x)^{-(r+1)} =\binom{r+i}{i}=\binom{r+i}{r},\qquad (*)$$ we can write $$\binom{n}{p} \binom{n}{q} = [x^{n-p}y^{n-q}] (1-x)^{-(p+1)} (1-y)^{-(q+1)}.$$ This can be rewritten as a complex integral $$\frac{1}{(2\pi i)^2} \int x^{p-n-1} y^{q-n-1} (1-x)^{-(p+1)} (1-y)^{-(q+1)} dx dy,$$ where $x$ and $y$ both traverse small counterclockwise circles around the origin. Now, make the substitution $$x = z\frac{1+w}{1+z}, \qquad y=w\frac{1+z}{1+w}.$$ Since $$dx \wedge dy = \frac{1-zw}{(1+z)(1+w)} dz \wedge dw$$ this changes the integral to $$\frac{1}{(2\pi i)^2} \int z^{p-n-1} w^{q-n-1} (1+w)^p (1+z)^q (1-zw)^{-(p+q+1)} dz\, dw.$$ On the surface of integration, $z$ and $w$ will now remain in small annuli around the origin. Remaining inside the region where the integrand is holomorphic, we can deform the surface of integration until $z$ and $w$ move counterclockwise around small circles around the origin. This does not change the value of the integral, so it will equal $$[z^{n-p} w^{n-q}] (1+w)^p (1+z)^q (1-zw)^{-(p+q+1)}.$$ Using (*) and the binomial theorem, this is equal to $$\sum_{\ell\in{\Bbb Z}} \binom{p}{n-q-\ell} \binom{q}{n-p-\ell} \binom{p+q+\ell}{p+q},$$ where the binomial coefficient $\binom{i}{j}$ is taken to vanish if $j$ is not in $\{0,1,\dots,i\}$. Substituting $\ell:=n-p-q+k$ now gives the desired result.

-
Nice contour integration (+1). I've rarely, if ever, used contour integration to prove a binomial identity. I tried multiplying both sides by $x^py^q$, summing, and comparing the coefficients in $(1+x)^n(1+y)^n=(1+x+y+xy)^n$, but couldn't get it to work. – robjohn Jan 17 '13 at 15:51

Here is a slightly different complex variable proof.

Suppose we seek to evaluate $$\sum_{k\ge 0} {p\choose k} {q\choose k} {n+k\choose p+q}$$

which is claimed to be $${n\choose p} {n\choose q}.$$

We use the integrals $${p\choose k} = \frac{1}{2\pi i}\int_{|z_1|=\epsilon} \frac{1}{z_1^{p-k+1}} \frac{1}{(1-z_1)^{k+1}} \; dz_1$$

and $${q\choose k} = \frac{1}{2\pi i}\int_{|z_2|=\epsilon} \frac{1}{z_2^{q-k+1}} \frac{1}{(1-z_2)^{k+1}} \; dz_2.$$

These two effectively control the range their product being zero when $k\gt \min(p,q)$ so that we may extend the sum to infinity.

We also use $${n+k\choose p+q} = \frac{1}{2\pi i}\int_{|w|=\epsilon} \frac{1}{w^{p+q+1}} (1+w)^{n+k} \; dw$$

This yields for the sum $$\frac{1}{2\pi i}\int_{|w|=\epsilon} \frac{1}{w^{p+q+1}} (1+w)^{n} \frac{1}{2\pi i}\int_{|z_1|=\epsilon} \frac{1}{z_1^{1+p}} \frac{1}{1-z_1} \frac{1}{2\pi i}\int_{|z_2|=\epsilon} \frac{1}{z_2^{1+q}} \frac{1}{1-z_2} \\ \times \sum_{k\ge 0} \frac{(1+w)^k z_1^k z_2^k}{(1-z_1)^k (1-z_2)^k} \; dz_2 \; dz_1 \; dw \\ = \frac{1}{2\pi i}\int_{|w|=\epsilon} \frac{1}{w^{p+q+1}} (1+w)^{n} \frac{1}{2\pi i}\int_{|z_1|=\epsilon} \frac{1}{z_1^{1+p}} \frac{1}{1-z_1} \frac{1}{2\pi i}\int_{|z_2|=\epsilon} \frac{1}{z_2^{1+q}} \frac{1}{1-z_2} \\ \times \frac{1}{1-(1+w) z_1 z_2 / (1-z_1) / (1-z_2)} \; dz_2 \; dz_1 \; dw \\ = \frac{1}{2\pi i}\int_{|w|=\epsilon} \frac{1}{w^{p+q+1}} (1+w)^{n} \frac{1}{2\pi i}\int_{|z_1|=\epsilon} \frac{1}{z_1^{1+p}} \frac{1}{2\pi i}\int_{|z_2|=\epsilon} \frac{1}{z_2^{1+q}} \\ \times \frac{1}{(1-z_1)(1-z_2)-(1+w) z_1 z_2} \; dz_2 \; dz_1 \; dw.$$

The inner term here is $$\frac{1}{1-z_1-z_2 + z_1 z_2 - z_1 z_2 - w z_1 z_2} \\ = \frac{1}{1-z_1-z_2 - w z_1 z_2} = \frac{1}{1-z_1} \frac{1}{1-(1+wz_1) z_2 /(1-z_1)}.$$

Extracting the residue in $z_2$ then yields $$\frac{1}{2\pi i}\int_{|w|=\epsilon} \frac{1}{w^{p+q+1}} (1+w)^{n} \frac{1}{2\pi i}\int_{|z_1|=\epsilon} \frac{1}{z_1^{1+p}} \frac{1}{1-z_1} \frac{(1+wz_1)^q}{(1-z_1)^q} \; dz_1 \; dw \\ = \frac{1}{2\pi i}\int_{|w|=\epsilon} \frac{1}{w^{p+q+1}} (1+w)^{n} \frac{1}{2\pi i}\int_{|z_1|=\epsilon} \frac{1}{z_1^{1+p}} \frac{(1+wz_1)^q}{(1-z_1)^{q+1}} \; dz_1 \; dw.$$

By symmetry of the initial sum we may suppose that $p\le q,$ getting for the inner integral $$\sum_{m=0}^p {q\choose m} w^m {p+q-m\choose q}.$$

The outer integral now yields $$\sum_{m=0}^p {q\choose m} {p+q-m\choose q} {n\choose p+q-m}.$$

The sum term here is $$\frac{n!}{(q-m)! \times m! \times (p-m)! \times (n+m-p-q)!} \\ = {n\choose p} \frac{p! \times (n-p)!}{(q-m)! \times m! \times (p-m)! \times (n+m-p-q)!} \\ = {n\choose p} {p\choose m} {n-p\choose q-m}.$$

It thus remains to show that $$\sum_{m=0}^p {p\choose m} {n-p\choose q-m} = {n\choose q}$$

which may be done combinatorially or by inspecting the integral $$\frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{q+1}} (1+v)^{n-p} \sum_{m=0}^p {p\choose m} v^m \; dv \\ = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{q+1}} (1+v)^{n-p} (1+v)^p \; dv \\ = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{q+1}} (1+v)^{n} \; dv = {n\choose q}.$$

-