8
$\begingroup$

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}$?

  • 2
    Maybe the coefficient of $x^n$ in $(1-x)^r(1+x)^s$?2011-12-27
  • 0
    @DilipSarwate I have been thinking along these lines without any luck2011-12-27
  • 0
    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.2011-12-27

3 Answers 3

8

$$(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}.$$

  • 0
    Thanks. The case $r=s$ is well-known, and I was hoping for some insight into the case $r\not= s$.2011-12-27
  • 0
    As OP has stated, there should be the factor $(-1)^{n/2}$ for the case when $n$ is even.2016-08-21
3

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).

  • 0
    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...2011-12-27
  • 0
    @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.2011-12-28
3

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.