How to prove this identity

Question

I would like to prove the following identity without using induction:

$$\sum _{ k=1 }^{ n }{ { (-1) }^{ k } {n\choose k} }\cdot k^n=(-1)^n\cdot n!. $$

Answer 1

Consider the polynomial $p(x)=(x-1)^n$. By the binomial theorem: $$ p(x) = (-1)^n \sum_{k=0}^{n}\binom{n}{k}x^k (-1)^k.\tag{1}$$ Let $\delta$ be the differential operator that sends $f(x)$ into $x\cdot f'(x)$. We have: $$ (\delta p)(x) = (-1)^n \sum_{k=0}^{n}\binom{n}{k}k\cdot x^k (-1)^k,\tag{2}$$ hence: $$ (\delta^n p)(1) = (-1)^n \sum_{k=0}^{n}\binom{n}{k}(-1)^k k^n.\tag{3}$$ $(\delta^n p)(x)$ is a sum of terms of the form $A_m\cdot x^m(x-1)^{n-m}$, and the evaluation in $x=1$ kills every term, except the one where $m=n$. Clearly $A_n=n!$, so the claim is proved.

Another standard way to prove your identity is to count all the bijective function between two sets with $n$ elements through the inclusion-exclusion principle.

Answer 2

HINT : $$\exp(kx)^{(n)}_{x=0}=k^n$$

Details:

$$\sum _{ k=1 }^{ n }{ { (-1) }^{ k+1 } {n\choose k} }k^n=-\lim_{x\rightarrow 0}\frac{d^n}{dx^n}\sum _{ k=1 }^{ n }{ { (-1) }^{ k+1 } {n\choose k} }e^{kx}$$ $$ =-\lim_{x\rightarrow 0}\frac{d^n}{dx^n}(1-e^x)^n $$ Using the binomial theorem $$ =-\lim_{x\rightarrow 0}\frac{d^n}{dx^n}\bigl(-x-\frac{x^2}{2!}-\frac{x^3}{3!}-\cdots \bigr)^n $$ Using Taylor series $$ =(-1)^{n+1}\lim_{x\rightarrow 0}\frac{d^n}{dx^n}\bigl(x^n+n\frac{x^{n+1}}{2}+\cdots\bigr) $$ $$ =(-1)^{n+1} n! $$