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