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.

I want to ask if there is a slick way to prove:

$$\sum_{j=0}^n{(-1)^j{{n}\choose{j}}\left(1-\frac{j}{n}\right)^n}=\frac{n!}{n^n}$$

Edit:

I know Yuval has given a proof, but that one is not direct. I am requesting for a direct algebraic proof of this identity.

Thanks.

share|improve this question

6 Answers 6

up vote 7 down vote accepted

Start with

$$\sum_{j=0}^{n} (-1)^j \binom{n}{j} (1+x)^{n-j} = x^n$$

which follows readily from the binomial theorem.

Now differentiate, and multiply by $\displaystyle (1+x)$. Repeat this $\displaystyle n$ times and set $\displaystyle x = 0$.

Notice that the constant term of the resulting polynomial on the right side is $\displaystyle n!$.

You can prove by induction that the lowest degree of $\displaystyle x$ that appears on the right side after $\displaystyle k$ steps ($0 \lt \displaystyle k \le n$) is $\displaystyle x^{n-k}$ and has the coefficient $\displaystyle n(n-1)\dots(n-k+1)$.

This gives us the set of identities

$$\sum_{j=0}^{n} (-1)^j \binom{n}{j} (n-j)^{k} = 0, \ \ 0 \le k \lt n$$

$$\sum_{j=0}^{n} (-1)^j \binom{n}{j} (n-j)^{n} = n!$$

I also seem to recollect there was a proof involving $\displaystyle \log x$, I will update this answer later if I remember it.

share|improve this answer
    
have you found the $log x$ proof, maybe it is even easier and more direct? –  Qiang Li Jan 25 '11 at 20:25
    
@Qiang: I believe it involves stirling numbers. See the first few lines of this answer here: math.stackexchange.com/questions/4317/… and start with $\log x$ and apply $D_x$ to it $n$ times. –  Aryabhata Jan 25 '11 at 20:32
    
@Qiang: I don't think what I said in the earlier comments works, though, but using $D_x$ on the right function was the idea. I still don't remember though. Sorry. –  Aryabhata Jan 26 '11 at 17:33
    
See my answer. Was this the function you were thinking of? It is the exponential generating function for the Stirling numbers of the second kind. –  Mike Spivey Jan 28 '11 at 6:12

This is inclusion-exclusion for counting the number of onto maps from $n$ to $n$.

share|improve this answer
    
you meant {1,2,...,n} to {1,2,...,n} onto maps? correct, a good way to identify this! –  Qiang Li Jan 24 '11 at 4:29

Lemma: Let $f(j) = \sum_{k=0}^n f_k j^k$ be a degree $n$ polynomial. I claim that $\sum_{j=0}^{n} (-1)^j \binom{n}{j} f(j) = n! f_n$.

Proof: For any polynomial $g$, define $\Delta(g)$ to be the polynomial $\Delta(g)(j) = g(j) - g(j+1)$. Observe that, if $g$ is a polynomial with leading term $a x^d + \cdots$, then $\Delta(g)$ is a polynomial with leading term $-d a x^{d-1} + \cdots$. In particular, if $f$ is as in the statement of the lemma, then $\Delta^n(f)$ is the constant $(-1)^n n! f_n$. The sum in question is $\Delta^n(f)$ evaluated at $0$. QED

Now, apply the lemma to $f(j) = (1-j/n)^n$.

share|improve this answer

This answer is similar to Moron's but I think is somewhat simpler. Expand $(e^x-1)^n$ using the binomial theorem to obtain $$(e^x-1)^n = \sum_{j=0}^n (-1)^{n-j} \binom{n}{j} e^{jx}.$$ Differentiate both sides $n$ times. Every term on the left-hand side will contain an $e^x-1$ factor except for an $n!e^{nx}$ term, and the right side will be $$\sum_{j=0}^n (-1)^{n-j} \binom{n}{j} j^n e^{jx}.$$ Then substitute $x = 0$ to obtain $$n! = \sum_{j=0}^n (-1)^{n-j} \binom{n}{j} j^n.$$ Reindex the sum and divide by $n^n$.

share|improve this answer
    
No. This wasn't it. +1, though :-) –  Aryabhata Jan 28 '11 at 7:03
    
@Moron: Now I'm really curious what it was! Something involving derivatives, Stirling numbers, and the $\log$ function, huh? –  Mike Spivey Jan 28 '11 at 19:29
    
Yes, something like that. I wish I remembered. It could have been similar to your answer though. Sorry, for leaving this hanging... –  Aryabhata Jan 28 '11 at 20:07
1  
@Moron: No apologies necessary! Trying to construct an answer within those parameters gives me another fun challenge to think about. :) –  Mike Spivey Jan 28 '11 at 21:14

The result follows immediately if you know the Stirling Numbers of the second kind, and it's combinatoric meaning. Not an algebraic proof, though.

Update:

In table 4 of these Combinatorial Identities it is stated an identity that -I believe- is equivalent to yours:

$ \displaystyle \sum_{k=0}^n (-1)^k {n \choose k} k^j = (-1)^n n!$

if $j=n$, (zero otherwise). And it just say that this is a "Statement of Euler's finite difference theorem". I don't know what this means, and I would like to know.

Update 2:

Indeed, the identity follows from the formula of the n-th finite difference, taking the function $f(x)=x^j$

share|improve this answer
    
It seems that Moron answered my last question while I was editing –  leonbloy Jan 24 '11 at 18:46

Let n be fixed , and

f(x) = (x-n)^n

The standard result in finite difference state that if f is a polynomial of degree n , then

Δ^n(f) = n!

Now , the lhs of the given identity is exactly (1/n^n)Δ^n(f)(0) , and the result follows. Q.E.D.

share|improve this answer
1  
Did you read David Speyer's answer? –  Aryabhata Jan 27 '11 at 3:45

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.