Take the 2-minute tour ×
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.

Let $m,n\ge 1$ 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.

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|improve this question
add comment

6 Answers 6

up vote 20 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|improve this answer
add comment

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|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
add comment

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|improve this answer
add comment

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-k}{m-k} = \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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.