# A binomial identity

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.

-
$$\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. –  Frank Science Jul 23 '12 at 2:47
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}$$ –  Ｊ. Ｍ. 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.

-