# Proof of a combination identity: ∑_(j=0)^n (−1)^j (n j)(1−j/n)^n=(n!)/(n^n)

Proof of a combination identity: $\sum _{j=0}^{n}\left(-1{\right)}^{j}\left(\genfrac{}{}{0}{}{n}{j}\right){\left(1-\frac{j}{n}\right)}^{n}=\frac{n!}{{n}^{n}}$
You can still ask an expert for help

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Kaiden Stevens
$\sum _{j=0}^{n}\left(-1{\right)}^{j}\left(\genfrac{}{}{0}{}{n}{j}\right)\left(1+x{\right)}^{n-j}={x}^{n}$
which follows readily from the binomial theorem.
Now differentiate, and multiply by $\left(1+x\right)$. Repeat this $n$ times and set $x=0$.
Notice that the constant term of the resulting polynomial on the right side is $n!$.
You can prove by induction that the lowest degree of $x$ that appears on the right side after $k$ steps $0 is ${x}^{n-k}$ and has the coefficient $n\left(n-1\right)\dots \left(n-k+1\right)$.
This gives us the set of identities

$\sum _{j=0}^{n}\left(-1{\right)}^{j}\left(\genfrac{}{}{0}{}{n}{j}\right)\left(n-j{\right)}^{n}=n!$
###### Did you like this example?
furajat4h
Lemma: Let $f\left(j\right)=\sum _{k=0}^{n}{f}_{k}{j}^{k}$ be a degree $n$ polynomial. Claim that $\sum _{j=0}^{n}\left(-1{\right)}^{j}\left(\genfrac{}{}{0}{}{n}{j}\right)f\left(j\right)=n!{f}_{n}$.
Proof: For any polynomial $g$, define $\mathrm{\Delta }\left(g\right)$ to be the polynomial $\mathrm{\Delta }\left(g\right)$$\mathrm{\Delta }\left(g\right)\left(j\right)=g\left(j\right)-g\left(j+1\right)$. Observe that, if $g$ is a polynomial with leading term $a{x}^{d}+\cdots$, then $\mathrm{\Delta }\left(g\right)$ is a polynomial with leading term $-da{x}^{d-1}+\cdots$. In particular, if $f$ is as in the statement of the lemma, then ${\mathrm{\Delta }}^{n}\left(f\right)$ is the constant $\left(-1{\right)}^{n}n!{f}_{n}$. The sum in question is ${\mathrm{\Delta }}^{n}\left(f\right)$ evaluated at $0$. QED
Now, apply the lemma to $f\left(j\right)=\left(1-j/n{\right)}^{n}$.