Use the Inclusion-Exclusion Principle to show that for any non-negative integers $m, r, n$ such that $m≤r≤n$... Use the Inclusion-Exclusion Principle to show that for any non-negative integers
$m, r, n$ such that $m≤r≤n$,
$${n-m\choose{r-m}} = \sum_{i=0}^m(-1)^i {m\choose{i}} {n-i\choose{r}} $$


*

*We have had one lecture on the Inclusion-Exclusion Principle and I am really unsure as how to approach this problem.We have done several permutation related exercises from this section but none that have been presented as a proof. Any help is appreciated.

 A: Start by deciding on an interpretation of the lefthand side. One that is suggested by the way it’s written is that $\binom{n-m}{r-m}$ is the number of $(r-m)$-element subsets of the set $[n]=\{1,\ldots,n\}$ that do not contain any element of $[m]$, i.e., the number of $(r-m)$-element subsets of $[n]\setminus[m]$. We’ll try to interpret the righthand side as an inclusion-exclusion calculation of the same thing.
At this point I often find it helpful to write out the first few terms of the sum:
$$\sum_{i=0}^m(-1)^i\binom{m}i\binom{n-i}{r}=\binom{m}0\binom{n}r-\binom{m}1\binom{n-1}r+\binom{m}2\binom{n-2}r-+\ldots\;.$$
It appears that we’re starting with $\binom{n}r$ as a first approximation to $\binom{n-m}{r-m}$. The first correction term seems to be subtracting $\binom{n-1}r$ for each of the $\binom{m}1=m$ elements of $[m]$. Similarly, the second correction term could be adding $\binom{n-2}r$ for each of the $\binom{m}2$ pairs of elements of $[m]$. Let’s see whether this interpretation makes sense in terms of an inclusion-exclusion argument.
Clearly $\binom{n}r$ is the number of $r$-element subsets of $[n]$. For each $k\in[m]$, $\binom{n-1}r$ is the number of $r$-element subsets of $[n]\setminus\{k\}$, i.e., the number of $r$-element subsets of $[n]$ that do not contain $k$. In fact, for any $F\subseteq[m]$, $\binom{n-|F|}r$ is the number of $r$-element subsets of $[n]\setminus F$, i.e., that are disjoint from $F$. 
And now we’re in business. We start by counting all of the $r$-element subsets of $[n]$. Then we throw out each $r$-element subset of $[n]$ that does not contain $1$, each $r$-element subset of $[n]$ that does not contain $2$, and so on through the $r$-element subsets of $[n]$ that do not contain $m$; at this point we’re counting $\binom{n}r-m\binom{n-1}r$ subsets. But of course any $r$-element subset of $[n]$ that omits two elements of $[m]$ has been thrown out twice and must be added back in. There are $\binom{n}2$ $2$-element subsets of $[m]$, so we must add in $\binom{n}2\binom{n-2}r$. Continuing in this way, we end up with $\sum_{i=0}^m(-1)^i\binom{m}i\binom{n-i}r$, but what, exactly, have we counted?
The first correction tells you this: it’s pretty clearly an attempt to get rid of the $r$-subsets of $[n]$ that don’t contain every single $k\in[m]$. The remaining terms just adjust for over- and undercounting. Thus, we’ve counted the $r$-subsets of $[n]$ that contain $[m]$. Remove $[m]$ from one of those, and you have an $(r-m)$-subset of $[n]\setminus[m]$. Conversely, if you start with an $(r-m)$-subset of $[n]\setminus[m]$ and take its union with $[m]$, you get an $r$-subset of $[n]$ that contains $[m]$. These two operations are inverses of each other, so they establish a bijection between the $(r-m)$-subsets of $[n]\setminus[m]$ and the $r$-subsets of $[n]$ that contain $[m]$. It follows that
$$\sum_{i=0}^m(-1)^i\binom{m}i\binom{n-i}{r}=\binom{n-m}{r-m}\;.$$
We can recast this in more formal terms. For $k\in[m]$ let $\mathscr{A}_k$ be the set of all $r$-subsets of $[n]\setminus\{k\}$, the set of all $r$-subsets of $[n]$ that do not contain $k$. Then one standard form of the inclusion-exclusion principle says that
$$\left|\bigcup_{k=1}^m\mathscr{A}_k\right|=\sum_{\varnothing\ne F\subseteq[m]}(-1)^{|F|-1}\left|\bigcap_{k\in F}\mathscr{A}_k\right|\;.$$
In our case we saw above that
$$\left|\bigcap_{k\in F}\mathscr{A}_k\right|=\binom{n-|F|}r\;.$$
Moreover, for $i\in[m]$ there are $\binom{m}i$ subsets $F$ of $[m]$ of cardinality $i$, so
$$\left|\bigcup_{k=1}^m\mathscr{A}_k\right|=\sum_{\varnothing\ne F\subseteq[m]}(-1)^{|F|-1}\left|\bigcap_{k\in F}\mathscr{A}_k\right|=\sum_{i=1}^m(-1)^{i-1}\binom{m}i\binom{n-i}r\;.\tag{1}$$
The lefthand side of $(1)$ is the number of $r$-subsets of $[n]$ that omit at least one element of $[m]$; we want the number of $r$-subsets of $[n]$ that have $[m]$ as a subset. In other words, we want the cardinality of the complement of $\bigcup_{k=1}^m\mathscr{A}_k$. Since $[n]$ has altogether $\binom{n}r$ subsets of size $r$, the cardinality of that complement must be
$$\begin{align*}
\binom{n}r-\left|\bigcup_{k=1}^m\mathscr{A}_k\right|&=\binom{n}r-\sum_{i=1}^m(-1)^{i-1}\binom{m}i\binom{n-i}r\\
&=\binom{m}0\binom{n-0}r+\sum_{i=1}^m(-1)^i\binom{m}i\binom{n-i}r\\
&=\sum_{i=0}^m(-1)^i\binom{m}i\binom{n-i}r\;.\end{align*}$$
