Proof that $ \sum_k (-1)^k \binom{n-k}{n-m} \binom{m}{k} = \binom{n-m}{m}$

Question

Proof that $$ \sum_k (-1)^k \binom{n-k}{n-m} \binom{m}{k} = \binom{n-m}{m}$$

I tried to solved that in two approaches (in both failed):
1. Algebraically:
Use negation theorem: $$ \sum_k (-1)^k \binom{n-k}{n-m} \binom{m}{k} = \sum_k \binom{n-k}{n-m} \binom{k-m-1}{k} $$ and after than I can:
$$ \sum_k \binom{n-k}{n-m} \binom{k-m-1}{k} = \sum_k \binom{n-k}{n-m} \binom{k-m-1}{-m-1} $$ but stucked...
Another approach was trying to proof that via combinatoric's interpretation. Because lack of result I don't have anything to show there in that way..

Answer 1

Algebraic proof

\begin{align} \sum_k (-1)^k\binom{n-k}{n-m}\binom{m}{k} &=(-1)^m\sum_k (-1)^{m-k}\binom{n-k}{m-k}\binom{m}{k} \\&\stackrel{\text{n}}=(-1)^m\sum_k \binom{m-n-1}{m-k}\binom{m}{k} \\&\stackrel{\text{V}}=(-1)^m\binom{2m-n-1}{m} \\&\stackrel{\text{n}}=\binom{n-m}m \end{align} $\stackrel{\text{n}}=$ is the negation theorem.
$\stackrel{\text{V}}=$ is the (Chu)-Vandermonde identity.

Combinatorial proof sketch

Both sides answer the question

How many subsets of $\{1,2,\dots,n\}$ have size $m$, no two consecutive elements, and do not contain $n$?

The RHS is true because $$ (i_1,i_2,\dots,i_m)\implies (i_1,i_2+1,i_3+2,\dots,i_m+{m-1}) $$ is a bijection from increasing sequences of length $m$ whose entries are between $1$ and $n-m$, to subsets of $\{1,2,\dots,n-1\}$ with no adjacent elements (written in increasing order).

We count such subsets using the principle of inclusion exclusion. Namely, for $1\le i\le n-1$ let $E_i$ be the set of subsets where the $i^{th}$ smallest element is adjacent to the $(i+1)^{st}$ smallest element, and let $E_n$ be the set of subsets which include $n$. These are the bad subsets, so we want $|E_1^c\cap E_2^c\cap \dots \cap E_n^c|$, which is $$ \sum_{S\subseteq \{1,2,\dots,m\}} (-1)^{|S|}\left|\bigcap_{i\in S}E_i\right| $$ It turns out that $\left|\bigcap_{i\in S}E_i\right|=\binom{n-k}{m-k}$ whenever $|S|=k$. Roughly, when $k$ of the elements of the subset are constrained to be adjacent, we can group these elements together into a single block, so there are only $m-k$ elements to be chosen in a smaller space of $n-k$. I leave the messy details to you.

Answer 2

With $n\ge m$ where $m\ge 0$ we seek to show that

$$\sum_{k=0}^m {m\choose k} (-1)^k {n-k\choose n-m} = {n-m\choose m}.$$

The sum is

$$\sum_{k=0}^m {m\choose k} (-1)^k [z^{n-m}] (1+z)^{n-k} \\ = [z^{n-m}] (1+z)^n \sum_{k=0}^m {m\choose k} (-1)^k (1+z)^{-k} \\ = [z^{n-m}] (1+z)^n \left(1-\frac{1}{1+z}\right)^m \\ = [z^{n-m}] (1+z)^{n-m} z^m = [z^{n-2m}] (1+z)^{n-m} \\ = {n-m\choose n-2m} = {n-m\choose m}.$$

Remark. We may want to prove that this holds even when $n\lt m$ where again $m\ge 0.$ We are using formal power series and there is no principal part as in a Laurent series, hence the coefficient extractor $[z^{n-m}]$ is defined to return zero when $n\lt m.$ This is also the behaviour when the Cauchy Coefficient Formula is used, where we have

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-m+1}} (1+z)^{n-k} \; dz$$

and with $n\lt m$ no pole at zero will ever appear. In these circumstances some authors and computer algebra systems like Maple define the value to be

$${n-k\choose (n-k)-(n-m)} = {n-k\choose m-k} = \frac{(n-k)^{\underline{m-k}}}{(m-k)!}$$

supposing that $m\ge k.$ With this setting we in fact get non-zero values when $n\lt k \le m.$ We also have agreement with the values from the first case ($n\ge m$).

We then obtain for our sum

$$\sum_{k=0}^m {m\choose k} (-1)^k [z^{m-k}] (1+z)^{n-k} \\ = [z^m] (1+z)^n \sum_{k=0}^m {m\choose k} (-1)^k z^k \frac{1}{(1+z)^k} \\ = [z^m] (1+z)^n \left(1-\frac{z}{1+z}\right)^m = [z^m] (1+z)^{n-m} = {n-m\choose m}.$$

This proof goes through for all integer $n$ and $m\ge 0.$

Answer 3

Here's a semi-combinatorial proof. We'll consider a term on the left hand side. First, we know that $\binom{m}{k}$ counts size-$k$ subsets of $[m]$. Then consider $\binom{n-k}{n-m}=\binom{n-k}{m-k}$; since we have a size-$k$ subset $A$ of $[m]$, we can think of this as counting size-$(m-k)$ subsets of $[n]-A$. Hence, the left hand side counts pairs of sets $(A,B)$ such that $A\subseteq [m]$ with $|A|=k$ and $B\subseteq [n]-A$ with $|B|=m-k$. However, there's the caveat that such a pair $(A,B)$ has a positive contribution if $|A|$ is even, and a negative contribution if $|A|$ is odd.

Since $A$ and $B$ are disjoint, the union $A\cup B=C$ has size $m$. By looking instead at all such $C=A\cup B$, this is equivalent to looking at all $C\subseteq [n]$ such that $|C|=m$, and for each such $C$, considering all subsets $A\subseteq C\cap [m]$; each such $(C,A)$ pair gives a positive contribution if $|A|$ is even, and a negative contribution if $|A|$ is odd.

Now I make the following claim: for each such $C$, the sum of contributions of all $(C,A)$ pairs is $0$ if $C\cap [m]$ is nonempty, and $1$ if $C\cap[m]=\varnothing$. You can show this using the same argument that a size-$n$ set has exactly as many odd subsets as it does even subsets when $n\geq 1$, and only one even subset (itself) and no odd subsets when $n=0$. It then follows that we're really just counting size-$m$ sets $C$ with $C\subseteq [n]-[m]$, which are counted by $\binom{n-m}{m}$. There are some details you can fill in to understand why this works.