Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
@Euler....IS_ALIVE I believe OP is talking about the error message one receives for posting a very short question. –  Austin Mohr Jan 17 '13 at 3:46
It does fail to meet our following quality suggestions: You seem to be new to math.stackexchange. Welcome! (1) Please refrain from adding extraneous tags. This question has nothing to do with multinomial coefficients. If this is a homework problem, then you should also add the [homework] tag. (2) It would be nice of you to put questions in full sentence form, and to avoid using the imperative mood when asking questions. (3) It is proper stackexchange etiquette to describe what serious attempts you have made to answer your question. Please read the faq (upper right corner) for details. –  Gyu Eun Lee Jan 17 '13 at 3:51
@JavaMan: Definitely. Or $q \leq p$. –  gnometorule Jan 17 '13 at 4:27
@JavaMan: I only just now see the $p$ as a summation index too, and am looking for a brown bag. –  gnometorule Jan 17 '13 at 4:30
$p\le q$ or $q\le p$ wasn't important! –  hxthanh Jan 17 '13 at 4:45

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer
+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.

share|improve this answer
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}.$$

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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