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

-
@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. –  kigen 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

\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