Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The well-known Vandermonde convolution gives us the closed form $\sum_{k=0}^n {r\choose k}{s\choose n-k} = {r+s \choose n}$. For the case $r=s$, it is also known that $\sum_{k=0}^n (-1)^k {r \choose k} {r \choose n-k} = (-1)^{n/2} {r \choose n/2} [n \mathrm{\ is\ even}]$.

When $r\not= s$, is there a known closed form for the alternating Vandermonde sum $\sum_{k=0}^n (-1)^k {r \choose k} {s \choose n-k}$?

share|cite|improve this question
Maybe the coefficient of $x^n$ in $(1-x)^r(1+x)^s$? – Dilip Sarwate Dec 27 '11 at 19:29
@DilipSarwate I have been thinking along these lines without any luck – user21436 Dec 27 '11 at 19:31
Thanks. In fact, the convolution arises since I need to compute $\sum_{i=0}^N a^i (1-x^i)^r(1+x^i)^s$ for very large values of $N$. Expanding the product converts it into the sum of $O(rs)$ geometric series, which is nice since $rs \ll N$. It would be nice to write (and evaluate) the resulting convolutions in closed form. – cvr Dec 27 '11 at 20:50

$$(1-x)^r(1+x)^s=\left(\sum_{g=0}^r (-x)^g{r\choose g}\right)\left(\sum_{h=0}^sx^h{s\choose h}\right)$$

$$\implies \sum_{k=0}^n(-1)^k{r\choose k}{s\choose n-k}=[x^n](1-x)^r(1+x)^s.$$

How closed would you consider this? I'm not sure if it gets simpler, but obviously it tells us

$$\sum_{k=0}^n(-1)^k{r\choose k}{r\choose n-k}=\begin{cases}0& n\text{ odd}\\ \\ {r\choose n/2}& n\text{ even}\end{cases}.$$

share|cite|improve this answer
Thanks. The case $r=s$ is well-known, and I was hoping for some insight into the case $r\not= s$. – cvr Dec 27 '11 at 20:58

According to Maple, the answer is ${s\choose n}{{}_2F_1(-r,-n;\,s-n+1;\,-1)}$ (of course we must assume $s \ge n$ for this to make sense).

share|cite|improve this answer
Thanks very much. The Hypergeometric is a convenient closed form in a formal sense, but I was looking for a simple closed form since I need to actually evaluate the convolution. It's not clear to me that the Hypergeometric would help me in that regard... – cvr Dec 27 '11 at 20:56
@cvr: One should remember that the Chu-Vandermonde identity can itself be repackaged as a hypergeometric function identity. For this specific case, you might be able to use three-term recurrences satisfied by the Gaussian hypergeometric function instead of the convolution sum; you'll have to do the derivation/testing yourself, though. – J. M. Dec 28 '11 at 3:17

You can use the Zeilberger algorithm to find a recurrence for the sum and then use Petkovsek's algorithm to verify that there are no hypergeometric (i.e. essentially products of factorials) closed formulas for the general case.

So, you cannot expect to do better than the expressions proposed in the other answers.

share|cite|improve this answer

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.