Proving an binomial identity with elementary means

82 Views Asked by At

For $k<2n$:

$$\sum_{i=0}^k(-1)^{k-i}{2n-k+i\choose n}{k\choose i}={2n-k\choose n}$$

I can prove this is true by relating both sides to certain number-theoretic objects, but I think a proof relying solely on combinatorial methods should be possible. Any hints/tips?

1

There are 1 best solutions below

2
On BEST ANSWER

It’s an inclusion-exclusion calculation, counting the number of $n$-element subsets of $[2n-k]$ in two different ways. The righthand side is clearly that number.

For $i\in[k]$ let $\mathscr{A}_i$ be the set of $n$-element subsets of $[2n]$ that include $i$. If $\varnothing\ne I\subseteq[k]$,

$$\left|\,\bigcap_{i\in I}\mathscr{A}_i\,\right|=\binom{2n-|I|}n\;.$$

Thus,

$$\begin{align*} \left|\,\bigcup_{i\in[k]}\mathscr{A}_i\,\right|&=\sum_{\varnothing\ne I\subseteq[k]}(-1)^{|I|+1}\left|\,\bigcap_{i\in I}\mathscr{A}_i\,\right|\\ &=\sum_{i=1}^k(-1)^{i+1}\binom{k}i\binom{2n-i}n\;, \end{align*}$$

since there are $\binom{k}i$ subsets of $[k]$ of cardinality $i$. The $n$-element subsets of $[2n-k]$ are the $n$-element subsets of $[2n]$ that are not in $\bigcup_{i\in[k]}\mathscr{A}_i$, so there are

$$\begin{align*} \binom{2n}n-\sum_{i=1}^k(-1)^{i+1}\binom{k}i\binom{2n-i}n&=\binom{2n}n+\sum_{i=1}^k(-1)^i\binom{k}i\binom{2n-i}n\\ &=\sum_{i=0}^k(-1)^i\binom{k}i\binom{2n-i}n\\ &=\sum_{i=0}^k(-1)^{k-i}\binom{k}{k-i}\binom{2n-(k-i)}n\\ &=\sum_{i=0}^k(-1)^{k-i}\binom{k}i\binom{2n-k+i}n\;. \end{align*}$$