# Algebraic expression of a sum

Let: $$S_n = \sum_{k=0}^n (-1)^k{n\choose k} k^n$$

1. Show that: $$S_n = -nS_{n-1} + n\sum_{k=0}^n (-1)^k{n\choose k}k^{n-1}, \qquad n \geq 1$$

2. If: $$\sum_{k=0}^N(-1)^k{N\choose k}k^m = 0, \quad \forall N > m \geq 0$$ Show that $$S_n=(-1)^n n!, \; n\geq 1$$.

3. Show that, $$\forall m,n \in \mathbb{N}$$, we have: $$\sum_{k=0}^n (-1)^k{n\choose k}(m+k)^n = (-1)^nn!$$

The only hint I have is that 2) can be shown by induction. Can anyone solve it or give any hints? Thanks!

• How far have you gotten with this? – saulspatz Apr 7 at 23:22

(1) is a fairly straightforward calculation if you’re familiar with basic binomial coefficient identities:

\begin{align*} &n\sum_{k=0}^n(-1)^k\binom{n}kk^{n-1}-n\sum_{k=0}^{n-1}(-1)^k\binom{n-1}kk^{n-1}\\ &\qquad=n\sum_{k=0}^n(-1)^k\left(\binom{n}k-\binom{n-1}k\right)k^{n-1}\\ &\qquad=n\sum_{k=0}^n(-1)^k\binom{n-1}{k-1}k^{n-1}\\ &\qquad=\sum_{k=0}^n(-1)^kk\binom{n}kk^{n-1}\\ &\qquad=\sum_{k=0}^n(-1)^k\binom{n}kk^n\\ &\qquad=S_n\,. \end{align*}

The hypothesis in (2) implies that

$$n\sum_{k=0}^n(-1)^k\binom{n}kk^{n-1}=0$$

for all $$n\ge 1$$. (Why?) Combining this with the identity in (1) easily gives you the induction step in a proof by induction on $$n$$ that $$S_n=(-1)^nn!$$ for $$n\ge 1$$.

For (3) you will need both the hypothesis and the result of (2). Start by applying the binomial theorem and reversing the order of summation:

\begin{align*} \sum_{k=0}^n(-1)^k\binom{n}k(m+k)^n&=\sum_{k=0}^n(-1)^k\binom{n}k\sum_{i=0}^n\binom{n}ik^im^{n-i}\\ &=\sum_{i=0}^n\binom{n}im^{n-i}\sum_{k=0}^n(-1)^k\binom{n}kk^i \end{align*}

Then apply (2).

• Didn't understood the first equality in 1). The sums have different maximum, can you put them together like that? Why? – Geaquinto Apr 8 at 13:34
• Never mind, I got it. Thanks a lot! – Geaquinto Apr 8 at 13:43
• @Geaquinto: You’re welcome! – Brian M. Scott Apr 8 at 18:11
• Can you help me on one more thing? I didn't understood why $k^i$ went to the other summation on the 3) part, in the second equality. – Geaquinto Apr 8 at 21:45
• @Geaquinto: Since it involves both $k$ and $i$, it has to be inside both of the summations, so it has to be inside the inner summation. Fortunately, that’s where we want it, because then we can apply (2) to the inner summation except when $i=n$. – Brian M. Scott Apr 9 at 0:30