1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Tony Ma May 13 '18 at 13:51
  • $\begingroup$ @Jean-ClaudeArbaut So is this really a valid proof of $\sum_{k=0}^{n}(-1)^k k^n\binom{n}{k}=n! (-1)^n$? $\endgroup$ – harlem May 13 '18 at 14:12
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.