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.
 A: 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.
A: 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$.
A: 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.
A: 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}
$$
A: 
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.
$$
