Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 26 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
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.

share|cite|improve this answer

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

share|cite|improve this answer
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.)

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.