How to prove that $\sum_{k=0}^m(-1)^k\binom{m}{k}\binom{n-k}{r}=\binom{n-m}{r-m} \qquad (n\ge r\ge m\ge 0)$ How to prove that
$$\sum_{k=0}^m(-1)^k\binom{m}{k}\binom{n-k}{r}=\binom{n-m}{r-m} \qquad (n\ge r\ge m\ge 0)$$
by using inclusion-exclusion principle?
With inclusion–exclusion principle, it's not hard to prove that
$$
\sum_{k=0}^m(-1)^k\binom{m}{k}\binom{n+m-k-1}{n}=\binom{n-1}{m-1}
$$
by counting multiset combinations, however this trick does not work in the new problem.
Any ideas for the solution?
 A: Hint: Say you want to choose $r$ elements out of $n$ elements, where the last $m$ elements are marked. In how many ways can you choose all the marked elements among the $r$ chosen ones?
Consider then the problem in which you do not pick say the $i-$th marked number. Call $A_i=\text{ ways to not pick the marked element }i$. Notice that there are $|A_i|=\binom{n-1}{r}$. $$\text{What is then }\left |\text{All ways }\setminus \bigcup _{i=1}^mA_i\right |\text{??}$$
A: Here is a proof which doesn't use inclusion-exclusion. I will try to adapt it to use inclusion-exclusion.
$$
\begin{align}
\sum_{k=0}^m(-1)^k\binom{m}{k}\binom{n-k}{r}
&=\sum_{k=0}^m(-1)^k\binom{m}{k}\binom{n-k}{n-k-r}\tag1\\
&=\sum_{k=0}^m(-1)^{n-r}\binom{m}{k}\binom{-r-1}{n-k-r}\tag2\\
&=(-1)^{n-r}\binom{m-r-1}{n-r}\tag3\\[3pt]
&=\binom{n-m}{n-r}\tag4\\[3pt]
&=\binom{n-m}{r-m}\tag5
\end{align}
$$
Explanation:
$(1)$: symmetry of Pascal's Triangle: $\binom{n}{k}=\binom{n}{n-k}$
$(2)$: negative binomial coefficients: $\binom{-n}{k}=(-1)^k\binom{n+k-1}{k}$
$(3)$: Vandermonde's Identity
$(4)$: negative binomial coefficients
$(5)$: symmetry of Pascal's Triangle
