Take the 2-minute tour ×
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.

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.

share|improve this question
$$\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}$$ –  J. M. Jul 23 '12 at 3:12
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.