This question already has an answer here:

Show that $\sum\limits_{k = 0}^{n} (-1)^k C_n^k C_{3n-k-1}^{2n-k} = 0$ for any $n > 0$.

I've tried to prove it by induction, but it turns out to be not so easy.

I bet there is some natural solution without induction here. I tried to come up with some polynomials such that the coefficient of $x^{2n}$ in their product equals to the given sum and then to prove that actually it is zero, but didn't manage to do it.

Also I tried to apply Inclusion–exclusion principle here, but didn't find the way to do it in our problem.

Any help would be greatly appreciated.


marked as duplicate by Lucian, Empty, Micah, Harish Chandra Rajpoot, David Oct 21 '15 at 6:29

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Let’s count the number of subsets of $[3n-1]$ that have cardinality $2n$ and are disjoint from $[n]$. On the one hand there clearly are no such sets, since $|[3n-1]\setminus[n]|=2n-1$. On the other hand,


is an inclusion-exclusion calculation of the number of such subsets of $[3n-1]$.

To see this, for $k\in[n]$ let $A_k$ be the family of $2n$-subsets of $[3n-1]$ that contain $k$. Then for any $F\subseteq[n]$ we have

$$\left|\bigcap_{k\in F}A_k\right|=\binom{3n-1-|F|}{2n-|F|}\;,$$

and for $1\le k\le n$ there are $\binom{n}k$ subsets $F$ of $[n]$ such that $|F|=k$, so


There are altogether $\binom{3n-1}{2n}$ subsets of $[3n-1]$ of cardinality $2k$, so the number of such sets that are disjoint from $[n]$ is


as desired.

  • $\begingroup$ (+1). The other link is missing the inclusion-exclusion argument. $\endgroup$ – Marko Riedel Oct 20 '15 at 23:08

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