How to calculate a combinatorial sum 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
$$
?

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