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.

-
The matrices here are infinite upper triangular so this would be the transpose of the given identity. The composition of the identifications of those polynomial bases, will act on the degree n elements according to the binomial expansion of ((x + 1) - 1)^n and ((y - 1) + 1)^n, where y=x+1. Comparing to the solution above that expands (1 - z + z)^n you can see that this must be the same but with a transposing of the matrices. – T.. Sep 8 '10 at 20:51

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

-
Where the summation disappears you need to insert the Iverson bracket $[n\geq m]$. After all $0^k=\delta_{0,k}$ is only valid for $k\geq0$. – Marc van Leeuwen May 29 '13 at 9:15
@Marc: Done! And thanks for bringing this post back to my attention. There was an index error in it. – Mike Spivey May 29 '13 at 21:56

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.)

-

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.

-

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.

-