Question

Using Vandermonde's identity we know:

$\sum_{i=0}^k \binom{k}{i}\binom{n-k}{n/2-i} = \binom{n}{n/2}$.

I'm interested in how close the alternating sum is to 0 when k << n. I.e., $\sum_{i=0}^k (-1)^i\binom{k}{i}\binom{n-k}{n/2-i}$.

Answer 1

So, you are interested in $f(n,k)=\sum_{i=0}^k (-1)^i\binom{k}{i}\binom{2n-k}{n-i}$. Simple manipulations show $f(n,k)=\frac{k!(2n-k)!}{(n!)^2}\left[\sum_{i=0}^n (-1)^i \binom{n}{i}\binom{n}{k-i}\right]$ Now the second factor counts the coefficient of $x^k$ in $(1-x^2)^n$ and therefore if $k$ is odd $f=0$ otherwise $f=(-1)^{\frac{k}{2}}\frac{k!(2n-k)!}{n!(k/2)!(n-k/2)!}$ which is far from zero...

EDIT: On a different note I see the result is a signed generalized Catalan number of degree 2 (I was not aware they satisfied such simple identities). Since usually providing combinatorial interpretations for generalized Catalan numbers is not easy, may I ask in what combinatorial context did you face the above calculation?