4

The following (conjectured) identity has come up in a research problem that I am working on:

for even $a$ $$\sum_{i=0}^{a-1} (-1)^{a-i}\binom{a}{i} \binom{2m-i-2}{m-i-1}=0;$$ and for odd $a$ $$\sum_{i=0}^{a-1} (-1)^{a-i}\binom{a}{i} \binom{2m-i-2}{m-i-1}=-2\binom{2m-a-2}{m-a-1},$$

where $a,m$ are positive integers with $1\le a\le m-2$.

I've verified the identity holds for small values of $a,m$.

The closest problem I have found is Help with a Binomial Coefficient Identity. Any suggestion how to apply that identity or to find another proof?

Alex
  • 51

2 Answers2

10

If you extend the sum to $a$, you can combine the even and odd cases into

$$ \sum_{i=0}^a(-1)^i\binom ai\binom{2n-i}{n-i}=\binom{2n-a}n\;, $$

with $n=m-1$. This is a double count using inclusion–exclusion of the number of ways of selecting $n$ from $2n$ elements such that $a$ particular elements are not included in the selection.

joriki
  • 238,052
3

For an algebraic proof of the re-formulated identity by @joriki we write

$$\sum_{q=0}^a (-1)^q {a\choose q} {2n-q\choose n-q} = \sum_{q=0}^a (-1)^q {a\choose q} [z^{n-q}] (1+z)^{2n-q} \\ = [z^n] (1+z)^{2n} \sum_{q=0}^a (-1)^q {a\choose q} z^q (1+z)^{-q} \\ = [z^n] (1+z)^{2n} \left(1-\frac{z}{1+z}\right)^a = [z^n] (1+z)^{2n-a} = {2n-a\choose n}.$$

Marko Riedel
  • 61,317