4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Your first sum should go up to n instead of k. $\endgroup$ Dec 10, 2009 at 9:59
  • $\begingroup$ I don't think so, the second binomial wouldn't make sense. The identity is true as it is. $\endgroup$ Dec 10, 2009 at 10:12

1 Answer 1

6
$\begingroup$

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?

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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