How do I prove this combinatorial identity using inclusion and exclusion principle? $$\binom{n}{m}-\binom{n}{m+1}+\binom{n}{m+2}-\cdots+(-1)^{n-m}\binom{n}{n}=\binom{n-1}{m-1}$$
Note that we can show this with out using inclusion and exclusion principle by using Pascal's Identity i.e. $C(n,k)=C(n-1,k)+C(n-1,k-1)$.  
 A: Let's begin by rewriting the formula with a shift from $n$ and $m$ to $n+1$ and $m+1$, so that the expression to prove is
$${n\choose m} = {n+1\choose m+1}-{n+1\choose m+2}+{n+1\choose m+3}-\cdots+(-1)^{n-m}{n+1\choose n+1}$$
Now picture a class with $n$ students and a teacher.  Each term on the right is of the form ${n+1\choose k}$, which counts the number of ways you can choose a group of size $k$ from among the $n+1$ people in the class.  Among these groups are some that include the teacher and some that don't.  Each group of size $k$ that doesn't include the teacher can be identified with a group of size $k+1$ that does include the teacher.
The expression ${n\choose m}$ can be interpreted as counting the number of ways you can choose a group of size $m$ from among the $n$ students only -- and then, if you like, adding the teacher to get a group of size $m+1$.  The inclusion-exclusion is now clear:  Start with all the ways you can form a group of size $m+1$, then try to eliminate the overcount, which consists of the all-student groups.
A: This is too long for a comment, that's why I'm putting it here.
The first observation is that your formula already implies Pascal's identity. Replacing $m$ by $m+1$ we have
$$\binom{n}{m+1}-\binom{n}{m+2}+\cdots+(-1)^{n-m-1}\binom{n}{n}=\binom{n-1}{m}.$$
Adding to the original formula gives (after cancelling) $\binom{n-1}{m}+\binom{n-1}{m-1}=\binom{n}{m}$. So, in some sense, any proof of this identity must include some idea proving Pascal's.
Now there is a way to putting the LHS as an application of Inclusion-Exclusion principle. Take the following sets:
$$
\begin{align}
A_1 &:= \left\{1,2,\dots,\textstyle\binom{n-1}{m-1}\right\}\\
A_2 &:= \left\{1,2,\dots,\textstyle\binom{n-2}{m-1}\right\}\\
 &\dots \\
A_{n-m+1} &:= \left\{\textstyle\binom{m-1}{m-1}\right\} =\{1\}.
\end{align}
$$
So we have $A_1\supset A_2 \supset \dots \supset A_{n-m+1}$. If you apply In-Ex to prove that 
$$
|A_1\cup \dots \cup A_{n-m+1}| = |A_1|=\textstyle\binom{n-1}{m-1},
$$
you may obtain (through extensive use of Pascal's and perhaps also induction) the summation on the LHS of your equation.
A: Note: This answer is inspired by the deleted answer of @diracpaul.
We  analyze lattice paths generated from $(1,0)$ steps in $x$-direction  and $(0,1)$ steps in $y$-direction. The number of paths from $(0,0)$ to $(m,n-m)$  is $\binom{n}{m}$. This is valid since for paths of length $n$ we can select $m$ steps in $x$-direction leaving $n-m$ steps in $y$-direction.
Let's write $\binom{n}{m}$ in the more symmetrical version using multinomial coefficients $\binom{n}{m,n-m}$. Using this notation OPs equation becomes
\begin{align*}
\binom{n-1}{m-1,n-m}&=\binom{n}{m,n-m}-\binom{n}{m+1,n-m-1}\\
&\qquad+\binom{n}{m+2,n-m-2}-\cdots+(-1)^{n-m}\binom{n}{n,0}\tag{1}
\end{align*}

For convenience only we change the representation by setting $x=m$ and $y=n-m$. Then OPs equation (1) becomes
\begin{align*}
\binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y}{x+1,y-1}\\
&\qquad+\binom{x+y}{x+2,y-2}-\cdots+(-1)^{y}\binom{x+y}{x+y,0}\tag{2}
\end{align*}

Before we interpret the identity (2) one additional aspect. We can use only $(1,0)$ steps or $(0,1)$ steps. So, when we go from $(0,0)$ to a point $(x,y)$ with $x,y>0$, we have to pass either $(x-1,y)$ or $(x,y-1)$. This gives the well known identity
\begin{align*}
\binom{x+y}{x,y}=\binom{x+y-1}{x-1,y}+\binom{x+y-1}{x,y-1}\tag{3}
\end{align*}

Now we claim the following:
  
  
*
  
*The LHS of (2) gives the number of paths of length $x+y-1$ from $(0,0)$ to $(x-1,y)$.
  
*The RHS of (2) gives the number of paths of length $x+y$ from $(0,0)$ to $(x,y)$ which pass $(x-1,y)$.
Since there is only one possibility to go from $(0,0)$ to $(x,y)$ via $(x-1,y)$, namely by adding a $(1,0)$ step from $(x-1,y)$ to $(x,y)$ it's obvious that both parts give the same number. According to (3) we conclude
\begin{align*}
\binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y-1}{x,y-1}\tag{4}
\end{align*}
The RHS of expression (4) is correct, but not the same as the RHS of (3).
The idea is to approach the representation (3) step by step. We note that $\binom{x+y-1}{x,y-1}$ is the number of paths of length $x+y-1$ from $(0,0)$ to $(x,y-1)$.  We argue now similar as above and say that this is the same as the number of paths of length $x+y$ from $(0,0)$ to $(x+1,y-1)$ passing through $(x,y-1)$.
This is realised according to (3) via
\begin{align*}
\binom{x+y-1}{x,y-1}&=\binom{x+y}{x+1,y-1}-\binom{x+y-1}{x+1,y-2}\tag{5}
\end{align*}
Combining this with (4) gives
\begin{align*}
\binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y-1}{x,y-1}\\
&=\binom{x+y}{x,y}-\binom{x+y}{x+1,y-1}+\binom{x+y-1}{x+1,y-2}
\end{align*}
And again we substitute the surplus $\binom{x+y-1}{x+1,y-2}$ by the number of pathes of length $x+y$ from $(0,0)$ to $(x+2,y-2)$ passing through $(x+1,y-2)$. This results in
\begin{align*}
\binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y-1}{x,y-1}\\
&=\binom{x+y}{x,y}-\binom{x+y}{x+1,y-1}+\binom{x+y}{x+2,y-2}-\binom{x+y-1}{x+2,y-3}
\end{align*}

Proceeding in this way we finally reach step by step the RHS of (2). Observe that the amounts of surplus are compensated according to the inclusion-exclusion principle.

We conclude: The binomial identity 
\begin{align*}
\binom{x+y-1}{x-1,y}&=\binom{x+y}{x,y}-\binom{x+y}{x+1,y-1}\\
&\qquad+\binom{x+y}{x+2,y-2}-\cdots+(-1)^{y}\binom{x+y}{x+y,0}=\tag{2}
\end{align*}
shows that the number of paths of length $x+y-1$ from $(0,0)$ to $(x-1,y)$ is the same as the number of paths of length $x+y$ from $(0,0)$ to $(x,y)$ passing through $(x-1,y)$, whereby the surplus can be compensated by successively adding and subtracting paths of length $x+y$ according to the inclusion-exclusion principle.

