MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Your first sum should go up to n instead of k. – Konrad Swanepoel Dec 10 '09 at 9:59
I don't think so, the second binomial wouldn't make sense. The identity is true as it is. – Gjergji Zaimi Dec 10 '09 at 10:12
up vote 5 down vote accepted

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?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.