# How to prove that $\sum\limits_{i=0}^p (-1)^{p-i} {p \choose i} i^j$ is $0$ for $j < p$ and $p!$ for $j = p$

Let $p \in \mathbf{N}$. I don't know how to prove that $$\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^j=0 \textrm{ for } j \in \{0,\ldots,p-1\},$$ and $$\sum_{i=0}^p (-1)^{p-i} {p \choose i} i^p=p!$$

(Maybe using the following hint, but not necessarily. Let's consider Cramer's system of equations (where $0^0:=1$): $$0^j x_0+1^j x_1+\ldots + p^j x_p=p! \delta_{j,p}$$

($j=0, \ldots,p$). The solution is probably given by $x_i=(-1)^{p-i} {p \choose i}$ for $i=0,\ldots, p$.)

Thanks.

• See also the proofs here, which is basically the same question. – Mike Spivey Sep 30 '11 at 15:36

Another Solution could be as follows:

It's a double counting of the surjective functions from the set $\{1,\dots,j\}$ to the set $\{1,\dots, p\}$.

On one hand, clearly these functions are $p!$ if $j=p$, while there are no such functions if $j<p$.

Let's count these functions in a different way:

For $1\leq i\leq p$ let us define the sets $$A_i:=\{\text{the functions from }\{1,\dots,j\}\text{ to }\{1,\dots,p\}\text{ which doesn't contain }\; i\;\text{ in their image}\}.$$

We have then

\begin{align} |A_i|&=(p-1)^j\\ |A_i\cap A_l|&=(p-2)^j\\ &\vdots&\\ \left|\bigcap_{i=1}^p A_i\right|&=0.\end{align}

We are interested in calculate the following: $$|\overline{A_1}\cap\overline{A_2}\cap\dots\cap\overline{A_p}|=|\overline{A_1\cup A_2 \cup\dots\cup A_p}|= p^j-|A_1\cup A_2 \cup\dots\cup A_p|=$$ $$p^j-\sum_{i=1}^p\left((-1)^{i+1}\sum_{1\leq j_1<\dots<j_i\leq p}\left|\bigcap_{k=1}^i A_{j_k}\right|\right)=\sum_{k=0}^p(-1)^{p+k}\binom{p}{k}k^j.$$ From which the thesis follows.

EDIT Since I spent a lot of time on this problem a year ago, I would like to give two other pennies on the topic, and I would give another solution, or at least a sketch of it:

So, let us consider the differential operator which realizes: $$D(f(x)) = \frac{\mathrm d}{\mathrm dx}(x\cdot f(x)) = f(x) + x\cdot\frac{\mathrm df}{\mathrm dx}.$$ Immediately one sees that $$D(x^m)=m\cdot x^m,$$ hence $$\sum_{k=0}^{p}(-1)^k \binom{p}{k}\,k^j = \left.D^j\left((1-x)^p\right)\right|_{x=1}.$$ So, (almost) immediately, again the thesis follows.

Let me say one last thing. This formula is strictly related to Stirling numbers of the second kind, but note how the second proof I gave you does not say much on what happens if $j>p$, while the first fits perfectly even in this situation.

• As it turns out, OP's problem, when recast in the notation of Stirling subset numbers, becomes the matter of proving that $$\left\{j \atop p\right\}=\begin{cases}0 &\text{if } j < p\\1 &\text{if } j=p\end{cases}$$. Recast in the language of difference calculus, this just says that if $j < p$, the $p$-th difference of $x^j$ is 0, much akin to the continuous case... – J. M. is a poor mathematician Sep 23 '11 at 10:20

Call $s_{j,p}$ the $j$th sum and consider the exponential generating function $S_p$ of the sequence $(s_{j,p})_{j\geqslant0}$ defined as $$S_p(x)=\sum\limits_{j=0}^{+\infty}s_{j,p}\frac{x^j}{j!}=\sum\limits_{i=0}^p(-1)^{p-i}{p\choose i}\sum\limits_{j=0}^{+\infty}i^j\frac{x^j}{j!}=\sum\limits_{i=0}^p(-1)^{p-i}{p\choose i}\mathrm e^{ix}.$$ By the binomial theorem, the last sum is $$\sum\limits_{i=0}^p{p\choose i}a^ib^{p-i}=(a+b)^p,$$ for $a=\mathrm e^x$ and $b=-1$, hence $$S_p(x)=(\mathrm e^x-1)^p.$$ The series expansion of $\mathrm e^x-1$ has no $x^0$ term hence the valuation of $S_p(x)$ is at least $p$. This proves that $s_{j,p}=0$ for every $0\leqslant j\leqslant p-1$.

Furthermore $\mathrm e^x-1=x+o(x)$ hence the $x^p$ term in $S_p(x)$ is exactly $1$ and $s_{p,p}=p!$.

This method provides $s_{p+j,p}$ for every positive $j$ as well, for example, $$\frac{s_{p+1,p}}{(p+1)!}=\frac{p}2,\qquad \frac{s_{p+2,p}}{(p+2)!}=\frac{p(3p+1)}{24},$$ and, more generally, for every nonnegative $j$, the ratio $\dfrac{s_{p+j,p}}{(p+j)!}$ is a polynomial in $p$ of degree $j$ and with rational coefficients.

Remark To compute $S_p(x)$, one can also note that the sum at the end of our first displayed equation is a multiple of the expectation of the sum $X_p=Y_1+\cdots+Y_p$ of $p$ i.i.d. Bernoulli random variables $Y_k$ with expectation $x$, hence $$S_p(x)=2^p(-1)^p\mathrm E((-1)^{X_p}\mathrm e^{xX_p}).$$ By independence the expectation is a product of $\mathrm E((-1)^{Y_k}\mathrm e^{xY_k})=\frac12(1-\mathrm e^x)$, hence $$S_p(x)=(-1)^p(1-\mathrm e^x)^p=(\mathrm e^x-1)^p.$$

• You can shorten this by observing the formula for $S_p(x)$ at the end of the first displayed line is just the binomial expansion of $(e^x - 1)^p$. – Zarrax Sep 23 '11 at 14:03
• @Zarrax, yes. Added this to the post. – Did Sep 23 '11 at 15:09

Let $\Sigma$ be an alphabet of $p$ different letters. I claim that $$\sum\limits_{i=0}^p (-1)^{p-i} \binom{p}{i} i^j$$ counts the number of words over $\Sigma$ of length $j$ that use all $p$ of the letters at least once each. This is just the inclusion-exclusion principle. For each $i$ from $0$ through $p$ there are $\binom{p}{i}i^j$ ways to choose a subset of $i$ letters and form a $j$-letter word using only letters from that subset, but not all of these ways use all $i$ of the letters in the subset. Thus, $$\binom{p}{p}p^j = p^j$$ is only a first approximation. From that we subtract the words that use only $p-1$ of the letters to get a second approximation, $$\binom{p}{p}p^j - \binom{p}{p-1}(p-1)^j.$$ Of course every word that’s missing at least two of the letters has been subtracted too often, so we have to add those back in to get a third approximation, $$\binom{p}{p}p^j - \binom{p}{p-1}(p-1)^j + \binom{p}{p-2}(p-2)^j.$$ The final result after all of the corrections is made is the original sum, $$\sum\limits_{i=0}^p (-1)^{p-i} \binom{p}{i} i^j.$$

Your result is an immediate consequence: if $j \in \{0,1,\dots,p-1\}$, there are of course no words of length $j$ that use all $p$ letters, and if $j=p$, the words that use all $p$ letters are precisely the $p!$ permutations of $\Sigma$.

• I've seen this proved many ways, but this is the first time I've seen it proven using the inclusion-exclusion principle. Cool! – robjohn Sep 23 '11 at 15:08

A comparison with the definition of the $p$-th forward difference shows that

$$\sum_{j=0}^p (-1)^{p-j} \binom{p}{j} j^k=\left.\Delta^p x^k\right\vert_{x=0}$$

Now, $x^k$ can be expanded as a series of falling factorials:

$$x^k=\sum_{j=0}^k \left\{k \atop j\right\} x^{(j)}$$

where $\left\{n \atop j\right\}$ is a Stirling subset number. Thus,

$$\Delta^p x^k=\sum_{j=0}^k \left\{k \atop j\right\}\Delta^p x^{(j)}$$

where we used the linearity of the forward difference operator. Since

$$\Delta^p x^{(k)}=\left(\prod_{j=0}^{p-1} (k-j)\right)x^{(k-p)}$$

and the product becomes zero if $k < p$, $\Delta^p x^{(k)}=0$ if $k < p$. Similarly, if $k=p$, the product in front is equal to $p!$, and we also have the property $x^{(0)}=1$; thus, $\Delta^p x^{(p)}=p!$. Substituting those into the expansion of $x^k$ in terms of the $x^{(j)}$, and noting that $\left\{k \atop k\right\}=1$, the claim is proven.

• More generally, this argument shows that $\sum_{j=0}^p (-1)^{p-j} {p \choose j} j^k = \left\{k \atop p\right\} p!$, which holds for all nonnegative integers $k$. – Mike Spivey Sep 23 '11 at 15:57
• A funny bit about Mathematica: it knows how to evaluate Sum[(-1)^j Binomial[p, j] (p - j)^n, {j, 0, p}] but is completely stumped by the reversal Sum[(-1)^(p - j) Binomial[p, j] j^n, {j, 0, p}]. Hmm... – J. M. is a poor mathematician Sep 24 '11 at 5:47

Note that $\displaystyle\binom{p}{i}\binom{i}{k}=\binom{p}{k}\binom{p-k}{i-k}$, Therefore, \begin{align} \sum_i(-1)^i\binom{p}{i}\binom{i}{k} &=\sum_i(-1)^i\binom{p}{k}\binom{p-k}{i-k}\\ &=\binom{p}{k}(1-1)^{p-k}\\ &=\binom{p}{k}0^{p-k}\tag{1} \end{align} Which is $1$ when $k=p$ and $0$ when $k<p$. Thus, $\displaystyle T_pf=\sum_i(-1)^i\binom{p}{i}f(i)$ kills all combinatorial polynomials with degree less than $p$.

$\displaystyle k!\binom{i}{k}$ is a degree $k$ polynomial in $i$ with lead coefficient $1$. Thus, we can write $$i^j=j!\binom{i}{j}+\sum_{k=0}^{j-1}a_{jk} k!\binom{i}{k}\tag{2}$$ for some integers $a_{jk}$. Therefore, putting together $(1)$ and $(2)$, \begin{align} \sum_i(-1)^i\binom{p}{i}i^j &=\sum_i(-1)^i\binom{p}{i}\left(j!\binom{i}{j}+\sum_{k=0}^{j-1}a_k k!\binom{i}{k}\right)\\ &=j!\binom{p}{j}0^{p-j}+\sum_{k=0}^{j-1}a_kk!\binom{p}{k}0^{p-k}\\ &=\left\{\begin{array}{rl}0&\text{if }j<p\\p!&\text{if }j=p\end{array}\right.\tag{3} \end{align}

• More or less similar to my approach, since $k!\binom{i}{k}=i^{(k)}$... the $a_k$ in equation $(2)$ are the Stirling subset numbers, as I mentioned in my answer. – J. M. is a poor mathematician Sep 23 '11 at 15:02
• @J. M.: Yes, it is. I had started mine a while ago, so I didn't see yours until after I had finished mine. – robjohn Sep 23 '11 at 15:25