How to calculate a combinatorial sum

Question

I have a combinatorial sum in hand which I suspect equals zero. But I do not know how to prove it. Can you guys help me? (I am even not sure if this is a hard question or not)

Is $$ \sum_{k=0}^n (-1)^k k^{n-1} \left(\begin{array}{l} n \\ k \end{array}\right) = 0 $$ ?

Answer 1

We have

$$\sum_{k=0}^n (-1)^k k^{n-1} {n\choose k} = (n-1)! [z^{n-1}] \sum_{k=0}^n (-1)^k \exp(kz) {n\choose k} \\ = (n-1)! [z^{n-1}] (1-\exp(z))^n.$$

Now $$1-\exp(z) = -z - z^2/2 - \cdots$$ and hence $(1-\exp(z))^n = (-1)^n z^n + \cdots$ so that

$$(n-1)! [z^{n-1}] (1-\exp(z))^n = 0.$$

Answer 2

HINT: Start with $$f(x)=(1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k.$$ Differentiate to show that $f'(-1)=0$. Differentiate again to show that $f''(-1)=0$. Keep going (inductively) until the $(n-1)$-th derivative.

Answer 3

For a combinatorial proof, note that both sides count the number of surjections of an $(n-1)$-set onto an $n$-set. The RHS is obvious, and the LHS is the inclusion-exclusion formula, where the $n$ properties to be avoided are that $i$ is not in the image of the function. More generally, this proof shows that the identity holds if you replace the power $n-1$ with any number $<n$.