0
$\begingroup$

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.

$\endgroup$

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.

1
$\begingroup$

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,

$$\sum_{k=0}^n(-1)^k\binom{n}k\binom{3n-k-1}{2n-k}$$

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

$$\left|\bigcup_{k\in[n]}A_k\right|=\sum_{k=1}^n(-1)^{k+1}\binom{n}k\binom{3n-1-k}{2n-k}\;.$$

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

$$\binom{3n-1}{2n}-\left|\bigcup_{k\in[n]}A_k\right|=\sum_{k=0}^n(-1)^k\binom{n}k\binom{3n-1-k}{2n-k}\;,$$

as desired.

$\endgroup$
  • $\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.