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.

Solution 1:

Use generating functions.

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

Solution 2:

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.

Solution 3:

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

Solution 4:

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.

Solution 5:

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