Beautiful identity: $\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$ Let $m,n\ge 0$ be two integers. Prove that
$$\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$$
where $\delta_{mn}$ stands for the Kronecker's delta (defined by $\delta_{mn} = \begin{cases} 1, & \text{if } m=n; \\ 0, & \text{if } m\neq n \end{cases}$).
Note: I put the tag "linear algebra" because i think there is an elegant way to attack the problem using a certain type of matrices.
I hope you will enjoy. :)
 A: I will try to give an answer using basic complex variables here.
Suppose we are trying to show that
$$\sum_k {n\choose k} (-1)^{k-m} {k\choose m} = \delta_{mn}.$$

Introduce the integral representation
$${k\choose m}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^{k}}{z^{m+1}} \; dz.$$

This gives  for the sum  the integral (the second  binomial coefficent
enforces the range)
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+1}} (-1)^m
\sum_{k=0}^n {n\choose k} (-1)^k
(1+z)^k \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+1}} (-1)^m
(1-1-z)^n \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{z^n}{z^{m+1}} (-1)^{m+n} \; dz.$$
This integral evaluates to $\delta_{mn}$ by inspection.

We have  not made use of  the properties of complex  integrals here so
this  computation  can  also   be  presented  using  just  algebra  of
generating functions.

Apparently  this method is  due to  Egorychev although  some of  it is
probably folklore.
A: This follows easily from the Multinomial Theorem, I believe.
$$ 1 = 1^n = (1 - x + x)^n$$
$$ = \sum_{a+b+c=n} {n \choose a,b,c} 1^a \cdot (-x)^b \cdot x^c$$
 $$ = \sum_{m=0}^{n} \sum_{k=m}^{n} {n \choose m,k-m,n-k} 1^{m}  \cdot (-x)^{k-m} \cdot x^{n-k} $$
  $$ = \sum_{m=0}^{n} \left[ \sum_{k=m}^{n} (-1)^{k-m} {k \choose m}{n \choose k} \right] x^{n-m}$$
Comparing coefficients now gives the result immediately.
A: The given quantity is the constant term in $ (-1)^m  \times { \sum_{ k \geq 0 } (-1)^{k} \binom{n}{k} (\frac{1}{x})^k } \times \sum_{k \geq 0} \binom{k}{m} x^k $
or the constant term in $(-1)^m \times (1-\frac{1}{x})^n \times x^{m} \times (1-x)^{-(m+1)}$ =  $(-1)^{m+n} x^{m-n} \times (1-x)^{n-m-1} $
If $m >n$ clearly the constant term is 0, if $m < n$ then writing the above as $(-1)^{m+n} \frac{(1-x)^{n-m-1}}{x^{n-m}}$ and noting the maximum exponent of $x$ in numerator is $n-m-1$ we again see the constant term is 0. If $n=m$ then the constant term is clearly 1.
A: You can also use the following finite calculus formula for alternating binomial transforms.  Let $B(f(k),n)$ denote the alternating binomial transform; i.e., $$B(f(k),n) = \sum_{k=0}^n (-1)^k \binom{n}{k} f(k).$$ 
Then (the formula)
$$B(f(k),n) = -B(\Delta f(k),n-1) + f(0)[n=0].$$
(Here, $\Delta f(k)$ is the finite difference $f(k+1) - f(k)$, and the expression $[n=0]$ evaluates to $1$ if $n = 0$ and $0$ otherwise.  Also, note that the first argument to $B$ is a function, while the second is a number.)  
Starting with $f(k) = 1$, we have $\Delta f(k) = 0$.  Since $B(0,n-1)$ is clearly $0$, $B(1,n) = [n=0]$.  The latter is just the known formula 
$$\sum_{k=0}^n (-1)^k \binom{n}{k} = [n=0].$$
Then, continuing to take antidifferences, and using the notation $k^{\underline{m}}$ for the falling factorial $k(k-1)\cdots (k-m+1)$ as well as the power rule for finite differences $\Delta k^{\underline{m}} = m k^{\underline{m-1}}$, we have
$$\sum_{k=0}^n (-1)^k \binom{n}{k}k = -B(1,n-1) = - [n-1=0] = -[n=1],$$
$$\sum_{k=0}^n (-1)^k \binom{n}{k} k^{\underline{2}} = -2B(k,n-1) = 2[n-1 = 1] = 2[n=2],$$
$$\sum_{k=0}^n (-1)^k \binom{n}{k} k^{\underline{3}} = -3B(k^{\underline{2}},n-1) = -6[n-1 = 2] = -6[n=3],$$
and so forth, until we get to 
$$\sum_{k=0}^n (-1)^k \binom{n}{k} k^{\underline{m}} = -mB(k^{\underline{m-1}},n-1) = (-1)^m m![n=m].$$ 
Since $k(k-1)\cdots (k-m+1) = \frac{k!}{(k-m)!}$, dividing both sides of this last identity by $(-1)^m m!$ proves the OP's identity.  
(The finite calculus formula for alternating binomial transforms and this argument are excerpted from my paper "Combinatorial sums and finite differences," Discrete Mathematics 307 (24): 3130-3146, 2007.) 
A: The vector space of polynomials in one variable has two bases $\{1, x, x^2, ... \}$ and $\{1, (x+1), (x+1)^2, ... \}$ and I believe what you've written down is equivalent to the statement that the change-of-basis matrices between these two bases multiply to the identity.
I am still thinking about an inclusion-exclusion argument.
A: Here's another way to look at Aryabhata's proof: the sum counts all the partitions of $[n]$ into three sets $A,B,C$ satisfying $|C|=m$, weighted according to $(-1)^{|A|}$. The identity just says that if $n \neq m$, the number of partitions with $|A|$ even is the same as those with $|A|$ odd.
The latter fact is proved by the following sign-changing involution: pick the first element which is not in $C$ (there must be one since $n \neq m$), and flip it from $A$ to $B$ or vice versa.
A: This also follows directly from the trinomial revision formula $\binom{r}{m} \binom{m}{k} = \binom{r}{k} \binom{r-k}{m-k}$, which is easily proved by writing the binomial coefficients in factorial form and regrouping.  (See, for example, Concrete Mathematics, 2nd ed., p. 168.)
We have $$\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \sum_{k=m}^n (-1)^{k-m} \binom{n}{m} \binom{n-m}{k-m} = \binom{n}{m} \sum_{k=0}^{n-m} (-1)^k \binom{n-m}{k}$$
$$= \binom{n}{m} (1 - 1)^{n-m} [n \ge m] = \binom{n}{m} \delta_{mn} = \delta_{mn}.$$
