Using inclusion-exclusion prove that $\sum_{k=0}^{m}(-1)^{k}\binom{m}{k}\binom{n-k}{r} = \binom{n-m}{r-m}$ Using an inclusion-exclusion argument prove that 
$\sum_{k=0}^{m}(-1)^{k}\binom{m}{k}\binom{n-k}{r} = \binom{n-m}{r-m}$ 
Assuming $m \leq r \leq n$.
I'm not sure how to begin this, can anyone help me get started?
 A: I’ll get you started by explaining how I attacked it; I’ll leave the finish to you, but feel free to ask questions if you get completely stuck. As usual $[s]$ denotes the set $\{1,\ldots,s\}$. 
On the lefthand side the factors $(-1)^k$ and $\binom{m}k$ look like part of the machinery of an inclusion-exclusion calculation, leaving $\binom{n-k}r$ as the meat of the term. It’s the number of $r$-element subsets of a set of $n-k$ elements. On the righthand side we have the number of $(r-m)$-element subsets of something; is there any way to interpret $\binom{n-m}{r-m}$ in terms of $r$-element subsets of something, to make it match the lefthand side better?
Yes: $\binom{n-m}{r-m}$ is the number of $r$-element subsets of $[n]$ that contain $[m]$ as a subset. Thus, we’d like to interpret the lefthand side as an inclusion-exclusion calculation of the number of $r$-element subsets $S$ of $[n]$ such that $[m]\subseteq S$.
Write out the first few terms of the summation:
$$\binom{n}r-\binom{m}1\binom{n-1}r+\binom{m}2\binom{n-2}r-\ldots$$
That first term is just the total number of $r$-element subsets of $[n]$. We want to throw out the ones that don’t contain $[m]$ as a subset. How many of these ‘bad’ $r$-element subsets of $[n]$ are there?
For each $i\in[m]$ let $\mathscr{A}_i$ be the set of $r$-element subsets of $[n]$ that do not contain $i$; then
$$\bigcup_{i\in[m]}\mathscr{A}_i$$
is the set of ‘bad’ $r$-element subsets of $[n]$, and there are therefore
$$\binom{n}r-\left|\bigcup_{i\in[m]}\mathscr{A}_i\right|$$
$r$-subsets of $[n]$ that do contain $[m]$ as a subset. The inclusion-exclusion principle says that
$$\left|\bigcup_{i\in[m]}\mathscr{A}_i\right|=\sum_{\varnothing\ne I\subseteq[m]}(-1)^{|I|-1}\left|\bigcap_{i\in I}\mathscr{A}_i\right|\;,$$
so there are
$$\binom{n}r-\sum_{\varnothing\ne I\subseteq[m]}(-1)^{|I|-1}\left|\bigcap_{i\in I}\mathscr{A}_i\right|=\binom{n}r+\sum_{\varnothing\ne I\subseteq[m]}(-1)^{|I|}\left|\bigcap_{i\in I}\mathscr{A}_i\right|$$
$r$-element subsets of $[n]$ that contain $[m]$ as a subset. To finish the argument, you need to show that
$$\binom{n}r+\sum_{\varnothing\ne I\subseteq[m]}(-1)^{|I|}\left|\bigcap_{i\in I}\mathscr{A}_i\right|=\sum_{k=0}^m(-1)^k\binom{m}k\binom{n-k}r\;.$$
A couple questions that may help:


*

*For a given $k$, how many $k$-element subsets of $[m]$ are there?  

*Can you express $\left|\bigcap_{i\in I}\mathscr{A}_i\right|$ in terms of $|I|$?

