A proof of a combinatorial identity Suppose $k \leq m \leq n$. Show that
\begin{align*}
{{n-k}\choose{n-m}}=\displaystyle\sum_{i=0}^{\min(k,\text{ n-m})} (-1)^{i}{{k}\choose{i}}{{n-i}\choose{m}}
\end{align*}
I'm having troubles with this one. Any (elegant) solutions?
 A: Here is an answer based upon generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write e.g.
\begin{align*}
[z^k](1+z)^n=\binom{n}{k}
\end{align*}

We obtain
  \begin{align*}
\color{blue}{\sum_{i= 0}^{\min\{k,\text{ n-m}\}}}&\color{blue}{ (-1)^{i}\binom{k}{i}\binom{n-i}{m}}\\
&=\sum_{i=0}^\infty(-1)^i[z^i](1+z)^k[u^m](1+u)^{n-i}\tag{1}\\
&=[u^m](1+u)^n\sum_{i=0}^\infty\left(-\frac{1}{1+u}\right)^i[z^i](1+z)^k\tag{2}\\
&=[u^m](1+u)^n\left(1-\frac{1}{1+u}\right)^k\tag{3}\\
&=[u^{m-k}](1+u)^{n-k}\tag{4}\\
&\color{blue}{=\binom{n-k}{m-k}}\tag{5}
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we apply the coefficient of operator twice. We also set the upper limit to $\infty$ without changing anything since we are adding zeros only.

*In (2) we use the linearity of the coefficient of operator. We also do some rearrangements as preparation for the next step.

*In (3) we apply the substitution rule of the coefficient of operator with $z:=-\frac{1}{(1+u)}$
\begin{align*}
A(u)=\sum_{k=0}^\infty a_k u^k=\sum_{k=0}^\infty u^k [z^k]A(z)
\end{align*}

*In (4) we do some simplifications and apply  the rule 
$$
[u^{m-k}]A(u)=[u^m]u^kA(u)
$$

*In (5) we select the coefficient of $[u^{m-k}]$.
A: $$
\begin{align}
\sum_{i=0}^{\min(k,n-m)}(-1)^i\binom{k}{i}\binom{n-i}{m}
&=\sum_{i=0}^{n-m}(-1)^i\binom{k}{i}\binom{n-i}{n-m-i}\tag1\\
&=\sum_{i=0}^{n-m}(-1)^{n-m}\binom{k}{i}\binom{-m-1}{n-m-i}\tag2\\
&=(-1)^{n-m}\binom{k-m-1}{n-m}\tag3\\[3pt]
&=\binom{n-k}{n-m}\tag4
\end{align}
$$
Explanation:
$(1)$: $\binom{n}{k}=\binom{n}{n-k}$
$(2)$: $\binom{-n}{k}=(-1)^k\binom{k+n-1}{k}$
$(3)$: Vandermonde's Identity
$(4)$: $\binom{-n}{k}=(-1)^k\binom{k+n-1}{k}$
