Sum with many troubles

Question

I am currently considering a sum $$\sum_{r=0}^{n}{\binom{n}{r} (-1)^{r} (1-\frac{r}{n})^{n}}$$ but have no thoughtful ideas how to start.

Maybe it's worth noticing that $$\sum_{r=0}^{n}{\binom{n}{n-r}(-1)^{r}(1-\frac{r}{n})^{n}} = \sum_{r=0}^{n}{\binom{n}{r} (-1)^{r} (1-\frac{r}{n})^{n}}$$ and apply to the first one the convolution rule, but this doesn't seem productive enough.

Are there any hints that might help? Would be grateful to recieve any.

Answer 1

We'll prov it combinatorically.

First note that $$\sum_{r=0}^{n} {n\choose r} (-1)^r (1-\frac rn)^n = \frac1{n^n} \sum_{r=0}^{n} {n\choose r} (-1)^r (n-r)^n$$

Now consider the rhs. By Inclusion exclusion principle, we can see that the sum is exactly the number of words in length $n$ with the letters $\{1,...n\}$ such that each letter appears at least once:

if we consider $p_i = $the letter i doesnt appear, we have:

$W(p_{i_1},....,p_{i_r})= (n-r)^n$ (the letters $i_1,...,i_r$ doesnt appear, so we pick for each of the $n$ spots of the word a letter out of the $n-r$ letters remaining). Then $$W(r) = {n \choose r}(n-r)^n$$ And finally we want $$E(0) = \sum_{r=0}^{n} {n\choose r} (-1)^r W(r)$$

Which combinatorical meaning is that each letter appears at least once.

So the rhs sum is exactly the number of words of size $n$ that each letter appear exactly once, which means the permutations over $n$ different letters, which is $n!$

Therefore you get that the lhs is equal $$\frac{n!}{n^n}$$

Answer 2

The construction $$ \sum_{k=0}^n\binom{n}{k}(-1)^k f(x-kh) $$ is the $n$-th iterate of the difference operator $(\Delta_h f)(x)=f(x)-f(x-h)$. Applied to a polynomial $f(x)=a_nx^n+...+a_1x+a_0$ of degree $n$ all terms vanish except the leading one which contributes its coefficient times $n!\,h^n$, $(Δ_h^{\,n}f)(x)=n!\,a_nh^n$.

In the question, $f(x)=x^n$, $h=1/n$ and the final evaluation is at $x=1$.

Answer 3

This one can also be done using complex variables.

Suppose we are trying to evaluate $$\sum_{r=0}^n {n\choose r} (-1)^r \left(1-\frac{r}{n}\right)^n.$$

Introduce the integral representation $$\left(1-\frac{r}{n}\right)^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp\left(\left(1-\frac{r}{n}\right)z\right) \; dz.$$

This gives for the sum $$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{r=0}^n {n\choose r} (-1)^r \exp\left(\left(1-\frac{r}{n}\right)z\right) \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(z) \sum_{r=0}^n {n\choose r} (-1)^r \exp\left(-\frac{r}{n}z\right)\; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(z) \left(1-\exp(-z/n)\right)^n \; dz.$$

Therefore the sum is $$n! [z^n] \exp(z) \left(1-\exp(-z/n)\right)^n.$$ Now $1-\exp(-z/n)$ starts at $z/n$ so the only contribution is $1/n^n$ for a final answer of $$\frac{n!}{n^n}.$$