Beautiful identity: $\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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.

Answer 7

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