# Are there any identities for alternating binomial sums of the form $\sum_{k=0}^{n} (-1)^{k}k^{p}{n \choose k}$?

In equations (20) - (25) of Mathworld's article on binomial sums, identities are given for sums of the form $$\sum_{k=0}^{n} k^{p}{n \choose k},$$ with $$p \in \mathbb{Z}_{\geq 0}$$. I wonder whether identities also exist for the alternating counterparts: $$\sum_{k=0}^{n} (-1)^{k}k^{p}{n \choose k} .$$ Furthermore, I'm interested in results for the same sum that is “cut off”, i.e. when the summands go from $$k=0$$ to some $$D.

A rewrite of formula (10) on MathWorld (replacing the summation index $$k-i\mapsto i$$) gives the desired formula: $$\sum_{k=0}^{n} (-1)^{k}k^{p}{n \choose k} =(-1)^n n! S_2(p,n),$$ where $$S_2(p,n)$$ is the Stirling number of the second kind (the number of ways of partitioning a set of $$p$$ elements into $$n$$ non-empty subsets).
It is remarkable that the alternating sum equals zero for $$p.

• It's not so remarkable that the alternating sum is zero for $p<n$. The sum is the $n$th difference at 0 of a polynomial of degree $p$. For any polynomial of degree $p$, the $p$th difference is constant and the $n$th difference for $n>p$ is 0. Aug 30 '20 at 21:48

For the cutoff version:

We can get a subtraction-free formula for the cutoff version, which should be sufficient to get asymptotics, by the same idea that gives a simple bijective proof of the identity that Carlo Beenakker mentioned. That is:

$$k^p$$ counts maps from a $$p$$-element set $$[p]$$ to a $$k$$-element set

Thus $$\binom{n}{k} k^p$$ counts pairs of a $$k$$-element subset $$S$$ of an $$n$$-elements set $$[n]$$ with a map from $$[p]$$ to $$S$$. In other words, it counts maps $$f$$ from $$[p]$$ to $$[n]$$ together with a $$k$$-element subset $$S$$ of $$[n]$$ containing the image of $$f$$.

So $$\sum_{k=0}^d (-1)^k \binom{n}{k} k^p$$ is the sum over maps $$f: [p] \to n$$ of the sum over subsets $$S$$ of $$[n]$$, containing the image of $$f$$, of size at most $$k$$, of $$(-1)^{|S|}$$. We may assume the image of $$f$$ has size $$\leq d < n$$ and thus that there is some element $$e$$ not in the image of $$f$$. We can cancel each subset with $$e\notin S$$ with the $$S \cup \{e\}$$, as these have opposite signs. The only subsets that fail to cancel are those that have size exactly $$d$$ and do not contain $$e$$, of which there are $$\binom{n - | \operatorname{Im}(f) | -1}{ d - |\operatorname{Im}(f)| }$$.

With $$S_2(p,j)$$ again the Stirling numbers of the second kind, the number of maps from $$[p]$$ to $$[n]$$ with image of size $$j$$ is $$\frac{n!}{ (n-j)!} S_2(p,j)$$, so the sum is

$$(-1)^d \sum_{j=0}^d S_2(p,j) \frac{n!}{(n-j)!} \binom{ n-j-1}{d-j}$$

$$= (-1)^d \frac{n!}{ (n-1-d)!} \sum_{j=0}^d S_2(p,j) \frac{1}{(n-j)} \frac{1}{(d-j)!}$$

(If $$d=n$$ then all subsets cancel and so only the terms with $$| \operatorname{Im} f| =n$$ remain, so we just obtain the count of surjections from $$[p]$$ to $$[n]$$, as in Carlo Beenakker's answer.)

Alternately, a formula-based proof:

we have $$k^p = \sum_{j=0}^k S_2( p,j) \frac{k!}{ (k-j)!}$$ ( a standard identity.) so

$$\sum_{k=0}^d (-1)^k k^p {n \choose k} = \sum_{j=0}^d \sum_{k=j}^d (-1)^k S_2( p,j) \frac{k!}{(k-j)!} {n \choose k}$$ and $$\frac{k!}{(k-j)!}{n\choose k} = \frac{k! n!}{ (k-j)! k! (n-k)! } = \frac{n!}{ (k-j)! (n-k)!} = \frac{n!}{(n-j)!} \binom{n-j}{k-j}$$ so $$\sum_{k=0}^d (-1)^k k^p {n \choose k} = \sum_{j=0}^d \sum_{k=j}^d (-1)^k S_2( p,j) \frac{n!}{(n-j)!} \binom{n-j}{k-j}$$ $$= \sum_{j=0}^d (-1)^d S_2( p,j) \frac{n!}{(n-j)!} \binom{n-j-1}{d-j} = (-1)^d \frac{n!}{ (n-1-d)!} \sum_{j=0}^d S_2(p,j) \frac{1}{(n-j)} \frac{1}{(d-j)!}$$

• Thank you! It is at times like these that I wish I could accept two answers. Aug 31 '20 at 11:12

Up to the factor $$(-1)^n$$, the uncut sum is $$s_{p,n}:=\sum_{k=0}^n(-1)^{n-k}\, k^p\,\binom nk.$$ As noted in the comment by Richard Stanley, $$s_{p,n}=(\Delta^n f_p)(0),$$ where $$f_p(x):=x^p$$ and $$(\Delta f)(x):=f(x+1)-f(x)$$. Here and in what follows, $$x$$ denotes any real number.

It is easy to check by induction on $$n$$ that for any smooth enough function $$f$$ we have $$(\Delta^n f)(x)=Ef^{(n)}(x+S_n),$$ where $$f^{(n)}$$ is the $$n$$th derivative of $$f$$, $$S_n:=U_1+\cdots+U_n$$, and $$U_1,\dots,U_n$$ are independent random variables uniformly distributed on the interval $$[0,1]$$. So, $$s_{p,n}=n!\binom pn ES_n^{p-n} \tag{1}$$ for $$p=0,1,\dots$$ and $$n=0,1,\dots$$. In particular, it follows that $$s_{p,n}=0$$ for $$n=p+1,p+2,\dots$$, as noted in the answer by Carlo Beenakker.

In fact, (1) holds for all real $$p\ge n$$ (and $$n=0,1,\dots$$), and then, obviously, $$0

If $$p-n\ge1$$, then, in view of Jensen's inequality, the lower bound $$0$$ on $$s_{p,n}$$ in (2) can be greatly improved, to $$b_{p,n}:=n!\binom pn \Big(\frac n2\Big)^{p-n}.$$

Moreover, by the law of large numbers, $$S_n/n\to1/2$$ in probability (say). Also, $$0\le S_n/n\le1$$. So, by dominated convergence, from (1) we immediately get the following asymptotics: if $$n\to\infty$$ and $$p-n\to a$$ for some real $$a>0$$, then $$s_{p,n}\sim b_{p,n}.$$

You can find plenty of documentation on Gould's site. Maybe it could be useful. The link is https://math.wvu.edu/~hgould/ Interesting files are Vol.1.PDF to Vol. 8.PDF.