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. :)
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.
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.
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.
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}.$$