I was wandering if someone knows an elementary proof of the following identity:

$$ \frac{(a)_n (b)_n}{(n!)^2} = \sum_{k=0}^n (-1)^k {1-a-b \choose k} \frac{(1-a)_{n-k}(1-b)_{n-k}}{((n-k)!)^2}\ , $$ where $a,b$ are arbitrary real numbers, $$(x)_0=1,\quad (x)_n:=x(x+1)\cdots(x+n-1) \quad \mbox{for $n\geq 1$} $$ is the Pochhammer's symbol, and $$ {x\choose 0}=1,\quad {x\choose k} = \frac{x(x-1)\cdots (x-k+1)}{k!} \quad \mbox{for $k\geq 1$}$$ is a binomial coefficient.

The proof that I know uses the Hypergeometric differential equation. One has to continue analytically the solutions along a path connecting two singular points. This could be done by some well known integral representation of the Hypergeometric function.

I think that there should be a combinatorial proof. Since this is an identity between polynomials in $a$ and $b$, it is enough to prove it for $a$ and $b$ negative integers, i.e., we may assume that $a=-p$ and $b=-q$ where $p,q\in \mathbb{Z}_{\geq 0}$. The identity then turns into $$ {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}. $$ I did not try very hard to proof the above identity and I did not search the literature that much, but since it comes from an interesting subject I think that it is worth finding an alternative proof.

  • 4
    $\begingroup$ $$\sum_k\binom{m-r+s}k\binom{n+r-s}{n-k}\binom{r+k}{m+n}=\binom rm\binom sn$$, Graham, Knuth, Patashnik: Concrete Mathematics, second edition, section 5.1, page 171. $\endgroup$ – Yai0Phah Jul 23 '12 at 2:47
  • 1
    $\begingroup$ Put another way, we want to prove that $$\binom{a+b+n-2}{n}{}_3 F_2\left({{-n,1-a,1-b}\atop{1,2-a-b-n}}\mid 1\right)=\binom{a+n-1}{n}\binom{b+n-1}{n}$$ $\endgroup$ – J. M. ain't a mathematician Jul 23 '12 at 3:12

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.


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.