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

  • 1
    $\begingroup$ 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.) $\endgroup$ – 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}$

  • $\begingroup$ +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. $\endgroup$ – Mike Spivey Jan 17 '13 at 17:46
  • 1
    $\begingroup$ Very nice. (This one word "Explanation" sort of spoils the fun of an answer containing "only" a calculation. Wouldn't a horizontal line do?) $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – 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}.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.