A binomial identity

Here's a proof using generating functions.

We'll use the following repeatedly: $\displaystyle \sum_{k \ge 0} \binom{n}{k} x^k = (1+x)^n, \sum_{k \ge 0} \binom{k}{n} x^k = \frac{x^n}{(1-x)^{n+1}}$

We want to prove the following:

$$ {p\choose n}{q\choose n} = \sum_{k=0}^n (-1)^k {1+p+q\choose k}{p+n-k\choose n-k}{q+n-k\choose n-k}. $$

Let's attack the gullible left hand side first. Multiply by $x^n y^q$ and sum over all $n, q \ge 0$, and rearrange the summations to get $$\sum_{n \ge 0} {p\choose n} x^n \sum_{q \ge 0} {q\choose n} y^q = \sum_{n \ge 0} {p\choose n} x^n \frac{y^n}{(1-y)^{n+1}} = \frac{1}{1-y} \left(1 + \frac{xy}{1-y} \right)^p = \frac{(1-y +xy)^p}{(1-y)^{p+1}}$$

So much for the left hand side. Now to the right hand side.

Firstly, change $k \rightarrow n-k$ in the summation, so that our right hand side becomes:

$$\sum_{k=0}^n (-1)^{n-k} {1+p+q\choose n-k}{p+k\choose k}{q+k\choose k} = \sum_{k=0}^n (-1)^{n-k} {1+p+q\choose n-k}{p+k\choose p}{q+k\choose k}$$

Now, multiply first by $x^n$, sum over $n \ge 0$, and rearrange to get : (We'll multiply $y^q$ later)

$$\sum_{k \ge 0} {p+k\choose p}{q+k\choose k} \sum_{n \ge 0} (-1)^{n-k} {1+p+q\choose n-k} x^n = \sum_{k \ge 0} {p+k\choose p}{q+k\choose k} x^k (1-x)^{1+p+q}$$

Now comes $y$. Multiply by $y^q$, sum over $q \ge 0$, and rearrange to get :

$$(1-x)^{1+p} \sum_{k \ge 0} {p+k\choose p} x^k \sum_{q \ge 0} {q+k\choose k} y^q (1-x)^{q} = (1-x)^{1+p} \sum_{k \ge 0} {p+k\choose p} \frac{x^k}{(1-y+xy)^{k+1}}$$

Now, this is equal to $\displaystyle \frac{(1-x)^{1+p}}{(1-y+xy)} \frac{1}{(1-t)^{1+p}}$, where $\displaystyle t = \frac{x}{(1-y+xy)} \implies 1-t = \frac{(1-x)(1-y)}{(1-y+xy)}$, giving us that $\displaystyle \frac{(1-x)^{1+p}}{(1-y+xy)} \frac{1}{(1-t)^{1+p}} = \frac{(1-y +xy)^p}{(1-y)^{p+1}}$, which was exactly what was needed.

Suppose we seek to evaluate

$$\sum_{k=0}^n (-1)^k {1+p+q\choose k} {p+n-k\choose n-k} {q+n-k\choose n-k}$$ which is claimed to be $${p\choose n}{q\choose n}.$$

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

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

Observe that these integrals vanish when $k\gt n$ and we may extend $k$ to infinity.

We thus obtain for the sum $$\frac{1}{2\pi i} \int_{|z_1|=\epsilon} \frac{(1+z_1)^{p+n}}{z_1^{n+1}} \frac{1}{2\pi i} \int_{|z_2|=\epsilon} \frac{(1+z_2)^{q+n}}{z_2^{n+1}} \\ \times \sum_{k\ge 0} {1+p+q\choose k} (-1)^k \frac{z_1^k z_2^k}{(1+z_1)^k (1+z_2)^k} \; dz_2\; dz_1.$$

This is $$\frac{1}{2\pi i} \int_{|z_1|=\epsilon} \frac{(1+z_1)^{p+n}}{z_1^{n+1}} \frac{1}{2\pi i} \int_{|z_2|=\epsilon} \frac{(1+z_2)^{q+n}}{z_2^{n+1}} \\ \times \left(1-\frac{z_1 z_2}{(1+z_1)(1+z_2)}\right)^{p+q+1} \; dz_2\; dz_1$$

or $$\frac{1}{2\pi i} \int_{|z_1|=\epsilon} \frac{(1+z_1)^{n-q-1}}{z_1^{n+1}} \frac{1}{2\pi i} \int_{|z_2|=\epsilon} \frac{(1+z_2)^{n-p-1}}{z_2^{n+1}} (1+ z_1 + z_2)^{p+q+1} \; dz_2\; dz_1$$

Supposing that $p\ge n$ and $q\ge n$ this may be re-written as $$\frac{1}{2\pi i} \int_{|z_1|=\epsilon} \frac{1}{z_1^{n+1} (1+z_1)^{q+1-n}} \frac{1}{2\pi i} \int_{|z_2|=\epsilon} \frac{1}{z_2^{n+1} (1+z_2)^{p+1-n}} \\ \times (1+ z_1 + z_2)^{p+q+1} \; dz_2\; dz_1$$

Put $z_2 = (1+z_1) z_3$ so that $dz_2 = (1+z_1) \; dz_3$ to get $$\frac{1}{2\pi i} \int_{|z_1|=\epsilon} \frac{1}{z_1^{n+1} (1+z_1)^{q+1-n}} \frac{1}{2\pi i} \int_{|z_2|=\epsilon} \frac{1}{(1+z_1)^{n+1} z_3^{n+1} (1+(1+z_1)z_3)^{p+1-n}} \\ \times (1+ z_1)^{p+q+1} (1+z_3)^{p+q+1} \; (1+z_1) \; dz_3\; dz_1$$

which is $$\frac{1}{2\pi i} \int_{|z_1|=\epsilon} \frac{(1+z_1)^p}{z_1^{n+1}} \frac{1}{2\pi i} \int_{|z_2|=\epsilon} \frac{1}{z_3^{n+1} (1+ z_3 + z_1 z_3)^{p+1-n}} \\ \times (1+z_3)^{p+q+1} \; dz_3\; dz_1 \\ = \frac{1}{2\pi i} \int_{|z_1|=\epsilon} \frac{(1+z_1)^p}{z_1^{n+1}} \frac{1}{2\pi i} \int_{|z_2|=\epsilon} \frac{(1+z_3)^{n+q}}{z_3^{n+1} (1 + z_1 z_3 /(1+z_3))^{p+1-n}} \; dz_3\; dz_1$$

Extracting the residue for $z_1$ first we obtain $$\sum_{k=0}^n {p\choose n-k} \frac{(1+z_3)^{n+q}}{z_3^{n+1}} {k+p-n\choose k} (-1)^k \frac{z_3^k}{(1+z_3)^k}.$$

The residue for $z_3$ then yields $$\sum_{k=0}^n (-1)^k {p\choose n-k} {k+p-n\choose k} {n-k+q\choose n-k}.$$

The sum term here is $$\frac{p!\times (p+k-n)!\times (q+n-k)!} {(n-k)! (p+k-n)! \times k! (p-n)! \times (n-k)! q!}$$ which simplifies to $$\frac{p!\times n! \times (q+n-k)!} {(n-k)! \times n!\times k! (p-n)! \times (n-k)! q!}$$ which is $${n\choose k} {p\choose n}{q+n-k\choose q}$$ so we have for the sum $${p\choose n} \sum_{k=0}^n {n\choose k} (-1)^k {q+n-k\choose q}.$$

To evaluae the remaining sum we introduce $${q+n-k\choose q} = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{q+n-k}}{v^{q+1}} \; dv$$

getting for the sum $${p\choose n} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{q+n}}{v^{q+1}} \sum_{k=0}^n {n\choose k} (-1)^k \frac{1}{(1+v)^k} \; dv \\ = {p\choose n} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{q+n}}{v^{q+1}} \left(1-\frac{1}{1+v}\right)^n \; dv \\ = {p\choose n} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{q}}{v^{q-n+1}} \; dv = {p\choose n} {q\choose q-n}$$

which is $${p\choose n} {q\choose n}.$$

This concludes the argument.