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

  • 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
    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
    @$c$vr: 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.