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)$

Question

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?

Answer 1

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{??}$$

Answer 2

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