6
$\begingroup$

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.

6 Answers 6

8

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.

  • 0
    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.2011-01-28
5

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

  • 0
    you meant {1,2,...,n} to {1,2,...,n} onto maps? correct, a good way to identify this!2011-01-24
5

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

2

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

  • 1
    @Moron: No apologies ne$c$essary! Trying to $c$onstruct an answer within those parameters gives me another fun challenge to think about. :)2011-01-28
1

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$

  • 0
    It seems that Moron answered my last question while I was editing2011-01-24
0

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.

  • 1
    Did you read David Speyer's answer?2011-01-27