Proof that $ \sum_k (-1)^k \binom{n-k}{n-m} \binom{m}{k} = \binom{n-m}{m}$ 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..
 A: 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.
A: 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.$
A: 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.
