# Proof of a combination identity:$\sum \limits_{j=0}^n{(-1)^j{{n}\choose{j}}\left(1-\frac{j}{n}\right)^n}=\frac{n!}{n^n}$

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.

-

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

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

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

-

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

-
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
@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$

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

-
Did you read David Speyer's answer? –  Aryabhata Jan 27 '11 at 3:45