Curious Binomial Coefficient Identity

Solution 1:

Here's an approach via generating functions (it is possible to make the proof shorter by avoiding them, but this was the straightforward approach without much cleverness).

If you have $$A(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \dots$$ and $$B(x) = b_0 + b_1x + b_2 x^2 + b_3x^3 + \dots$$ (the objects $A(x)$ and $B(x)$ are called generating functions of the two sequences) then their product $$A(x)B(x) = C(x) = c_0 + c_1x + c_2x^2 + c_3x^3+\dots$$ satisfies $$c_n = \sum_{r = 0}^{n} a_r b_{n-r}.$$

When, for some fixed $k$, the sequences are $a_n = (-1)^n\binom{k}{n}$ and $b_n = \binom{n}{k}$, we have $$A(x) = \sum_{n=0}^{\infty}(-1)^n\binom{k}{n}x^n = (1 - x)^k $$

and $$B(x) = \sum_{n=0}^{\infty}\binom{n}{k}x^n = \frac{x^k}{(1-x)^{k+1}} $$ (see here; this is a good exercise) so that their product is $$C(x) = A(x)B(x) = (1-x)^k \frac{x^k}{(1-x)^{k+1}} = \frac{x^k}{1-x} = x^k(1 + x + x^2 + \dots)$$

for which we have, for $n \ge k$, $$1 = c_n = \sum_{r=0}^{n}a_{r} b_{n-r} = \sum_{r=0}^n (-1)^r \binom{k}{r}\binom{n-r}{k} = \sum_{i=0}^k (-1)^i \binom{k}{i}\binom{n-i}{k} $$ (as $\binom{k}{r} = 0$ for $r > k$) which is what you wanted to prove.

Solution 2:

As usual let $[m]=\{1,\ldots,m\}$; we’ll count the $k$-sized subsets of $[m]$ that are contained in $[k]$. On the one hand there is obviously exactly one such set, namely, $[k]$ itself. On the other hand, for each $i\in[k]$ let $A_i$ be the family of $k$-sized subsets of $[m]$ that do not contain $i$. For any $I\subseteq[k]$ we have

$$\left|\bigcap_{i\in I}A_i\right|=\binom{m-|I|}k\;,$$

so a straightforward inclusion-exclusion argument shows that

$$\left|\bigcup_{i=1}^kA_i\right|=\sum_{i=1}^k(-1)^{i+1}\binom{k}i\binom{m-i}k$$

and hence that

$$1=\binom{m}k-\left|\bigcup_{i=1}^kA_i\right|=\sum_{i=0}^k(-1)^i\binom{k}i\binom{m-i}k\;.$$