# sum of alternating binomial

Compute the sum $\sum_{k=0}^{n}(-1)^k k^n\binom{n}{k}$

I've seen a solution along the following lines here, page 3:

Consider $(1+x)^n=\sum_{k=0}^{n}\binom{n}{k}x^k$. ($\star$) We prove by induction that $\sum_{k=0}^{n}(-1)^k k^t\binom{n}{k}=0$ for $t< n$. We prove this by differentiating ($\star$) t times, setting $x=-1$ and using the inductive step.

Now if we differentiate $(\star)$ n times we get: $n!=\sum_{k=0}^{n} k \cdot (k-1) \dots \cdot (k-(n-1)) \binom{n}{k}x^{k-n}=\sum_{k=0}^{n} k^n\binom{n}{k}x^{k-n}$ (by the inductive step).

So $n!=\sum_{k=0}^{n} k^n\binom{n}{k}x^{k-n}$ and by setting $x=-1$ and multiplying by $(-1)^n$ we get $\sum_{k=0}^{n}(-1)^k k^n\binom{n}{k}=n! (-1)^n$.

My question is, starting from $(1+x)^n=\sum_{k=0}^{n}\binom{n}{k}x^k$, if we differentiate it n times, most of the RHS terms will vanish ,leaving us with $n!=n!$, not $n!=\sum_{k=0}^{n} k \cdot (k-1) \dots \cdot (k-(n-1)) \binom{n}{k}x^{k-n}$. How is that a valid step and also how can the sum in question be evaluated?

• Notes that for R.H.S. ,when $0\le k\lt n$, the corresponding term does vanish and the last formula doesn't seems wrong at my first sight – Tony Ma May 13 '18 at 13:51
• @Jean-ClaudeArbaut So is this really a valid proof of $\sum_{k=0}^{n}(-1)^k k^n\binom{n}{k}=n! (-1)^n$? – harlem May 13 '18 at 14:12

Here is an answer based upon generating functions which might provide an alternate solution. It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write for instance \begin{align*} n![x^n]e^{kx}=k^n\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=0}^n\binom{n}{k}(-1)^kk^n} &=\sum_{k=0}^n\binom{n}{k}(-1)^k n![x^n]e^{kx}\tag{2}\\ &=n![x^n]\sum_{k=0}^n\binom{n}{k}\left(-e^x\right)^k\tag{3}\\ &=n![x^n](1-e^x)^n\tag{4}\\ &=n![x^n]\left(-x-\frac{x^2}{2!}-\frac{x^3}{3!}-\cdots\right)^n\\ &\,\,\color{blue}{=(-1)^nn!}\tag{5} \end{align*}

Comment:

• In (2) we apply the coefficient of operator according to (1).

• In (3) we use the linearity of the coefficient of operator.

• In (4) we apply the binomial theorem.

• In (5) we select the coefficient of $x^n$.

First some preliminary identities:

We use the identity $$k^n=\sum_{m=0}^n{n\brace m}(k)_m\tag{1}$$ where the braces indicate stirling numbers of the second kind and $(k)_m=k(k-1)\dotsb (k-m+1)$ indicates the falling factorial of length $m$. Also note that $$(1-x)^n=\sum_{k=0}^n\binom{n}{k} (-1)^kx^k$$ implies that $$\sum_{k=0}^n\binom{n}{k} (k)_m(-1)^k=\frac{d^m}{dx^m}(1-x)^n\bigg|_{x=1}=(n)_m(-1)^m\delta_{n,m}\quad (0\leq m\leq n)\tag{2}$$ where $\delta$ indicates the Kronecker Delta. Now we can proceed with the problem. Indeed, \begin{align} \sum_{k=0}^n\binom{n}{k}(-1)^kk^n &\stackrel{(1)}{=}\sum_{k=0}^n\binom{n}{k}(-1)^k\left( \sum_{m=0}^n{n\brace m}(k)_m \right)\\ &=\sum_{m=0}^n{n\brace m}\left(\sum_{k=0}^n(-1)^k\binom{n}{k}(k)_m\right)\\ &\stackrel{(2)}{=}\sum_{m=0}^n{n\brace m}(n)_m(-1)^m\delta_{n,m}\\ &=(-1)^nn! \end{align} as desired.

Define the linear functional transform $\;D_x[f(x)] := x f'(x).\;$ Clearly, $\;D_x[x^n] = nx^n,\;$ also $\;D_x[(x+y)^n] = nx(x+y)^{n-1}.\;$ The binomial theorem states that $\;(x+y)^n = \sum_{k=0}^n {n \choose k}x^k y^{n-k}.\;$ Apply $\;D_x\;$ to both sides of the equation gives $\;nx(x+y)^{n-1} = \sum_{k=0}^n {n \choose k}\;k\; x^k y^{n-k}.\;$ Apply $\;D_x\;$ to both sides several times gives a polynomial in $\;x,y\;$ whose coefficients (up to alternating sign) are OEIS triangular sequence A258773. The right side is $\; \sum_{k=0}^n {n \choose k}\;k^n\; x^k y^{n-k}.\;$ Let $\;x=-1,\; y=1\;$ to get $\;n!(-1)^n = \sum_{k=0}^n {n \choose k}\;k^n\;(-1)^k,$ where the left side comes from the OEIS sequence entry.

I also used $\;D_x\;$ in my answer to a MSE question 2772848 on property of Bernstein polynomial.