Show $S_n=-nS_{n-1}+n\sum_{k=0}^n (-1)^k\binom{n}{k}k^{n-1},\quad n\ge1$ I'm stuck in this question. It seems so easy, but I can't see it and at this point I spent too many time on it to be able to look at it with fresh eyes.
For each $n\in N$, consider:
$$S_n=\sum_{k=0}^n (-1)^k\binom{n}{k}k^n$$
Show:
$$S_n=-nS_{n-1}+n\sum_{k=0}^n (-1)^k\binom{n}{k}k^{n-1},\quad   n\ge1$$
Please help me get out of this misery. Appreciate any help.
edit: I've tried Pascal Rule but that didn't get me anywhere. I can't really understand what to do about the "$k^{n-1}$" part. I had a prior exercise where I had to prove a simpler version of this sum by mathematical induction, and it was fairly easy so I'm pretty sure this one is too. I just think I'm not being able to grasp it or probably I'm completely unaware of the principle to apply in this question.
 A: We have for
$$S_n = \sum_{k=0}^n (-1)^k {n\choose k} k^n$$
that it is
$$n! [z^n] \sum_{k=0}^n (-1)^k {n\choose k} \exp(kz)
= n! [z^n] (1-\exp(z))^n.$$
Observe that with $1-\exp(z) = - z - \cdots$ we have $(1-\exp(z))^n =
(-1)^n z^n + \cdots$ so that $S_n = n! \times (-1)^n.$
We also have for
$$T_n = \sum_{k=0}^n (-1)^k {n\choose k} k^{n-1}
\\ = (n-1)! [z^{n-1}]
\sum_{k=0}^n (-1)^k {n\choose k} \exp(kz)
= (n-1)! [z^{n-1}] (1-\exp(z))^n.$$
Again using
$(1-\exp(z))^n = (-1)^n z^n + \cdots$ we find that $T_n=0$
as pointed out in the comments.
Thus the claim becomes
$$n ! \times (-1)^n =
- n \times (n-1)! \times (-1)^{n-1}$$
and we have the result.
A: The first term $(k=0)$ in $S_n$ vanishes, so
$$S_n = \sum_{k=1}^n(-1)^k\binom nk k^n$$
and so
$$S_{n-1}=\sum_{k=1}^{n-1}(-1)^k\binom {n-1}k k^{n-1}$$
Notice that
$$S_n=\sum_{k=1}^n(-1)^k\binom nk k^n=\sum_{k=1}^n (-1)^k \binom{n-1}{k-1} n k^{n-1}$$
because
$$\binom nk k^n=\frac{n!}{k!(n-k)!}k^n=\frac{(n-1)!}{(k-1)!((n-1)-(k-1))!}nk^{n-1}=\binom{n-1}{k-1}nk^{n-1}$$
Then
$$\begin{align}
S_n+nS_{n-1}&=\sum_{k=1}^n (-1)^k \binom{n-1}{k-1} n k^{n-1} + \sum_{k=1}^{n-1}(-1)^k\binom {n-1}k n k^{n-1}
\end{align}$$
In the second sum, if $k=n$, then $\binom{n-1}k=\binom{n-1}n=0$, so we can have both sums over $1\le k\le n$ (or $0\le k\le n$), and the binomial coefficients condense due to Pascal's identity to give the expected result.
$$S_n+nS_{n-1}=\sum_{k=0}^n (-1)^k \binom nk nk^{n-1}$$
A: Note that
$$\sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)^m$$
is the inclusion-exclusion formula for surjections from an $m$-set to an $n$-set.  In particular, taking $m=n-1$ yields no surjections, so
$$\sum_{k=0}^n (-1)^k\binom{n}{k}k^{n-1} = (-1)^n \sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)^{n-1} = 0, \tag1$$
Similarly,
$$(-1)^n S_n =\sum_{k=0}^n (-1)^{n-k}\binom{n}{k}k^n = \sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)^n = n!$$
and
$$(-1)^{n-1} S_{n-1} = (n-1)!.$$
Hence
$$(-1)^n (S_n + n S_{n-1}) = (-1)^n S_n - n (-1)^{n-1} S_{n-1} = n! - n(n-1)! = 0. \tag2$$
Combining $(1)$ and $(2)$ yields $$S_n + n S_{n-1} = 0 = n \sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)^{n-1}.$$
