Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.