A proof of a combinatorial identity

Question

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?

Answer 1

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}]$.

Answer 2

$$ \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}$