Show $S_n=-nS_{n-1}+n\sum_{k=0}^n (-1)^k\binom{n}{k}k^{n-1},\quad n\ge1$

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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