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}.$$
Tell me more
×
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.
|
|
|||||||||||||
|
|
$$ \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}$ |
|||||||
|
|
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. |
||||
|
