Proving a complex sum equals factorial I have just stumbled across the equality that:
$$
\sum_{j=0}^{n}(-1) ^ {n + j}  j ^ {n} \binom{n}{j} = n!
$$
How would I go about proving this equality?
Also, what is the left hand side equal to if the power of j is increased:
$$
\sum_{j=0}^{n}(-1) ^ {n + j}  j ^ {n+k} \binom{n}{j} = ?
$$
where k=1,2,3...
Thanks!
 A: It’s an instance of the inclusion-exclusion principle. First let’s rewrite the expression. Let $k=n-j$:
$$\sum_{j=0}^n(-1)^{n+j}j^n\binom{n}j=\sum_{k=0}^n(-1)^k(n-k)^n\binom{n}{n-k}=\sum_{k=0}^n(-1)^k(n-k)^n\binom{n}k\;.$$
Now imagine that you have $n$ toys to distribute to $n$ children, and you want each child to get a toy; clearly you can distribute the toys in $n!$ different ways. On the other hand, you can consider the number of ‘bad’ distributions, in which some child gets no toy. For $k=1,\dots,n$, $\binom{n}k(n-k)^n$ is the number of ways to choose $k$ of the children to receive no toy and to distribute the $n$ toys to the other $n-k$ children. Of course some of the $n-k$ potentially lucky children may end up with no toy; that’s why you need an inclusion-exclusion argument. It tells you that there are
$$\sum_{k=1}^n(-1)^{k-1}\binom{n}k(n-k)^n$$
bad distributions, and since there are $n^n=(-1)^0\binom{n}n(n-0)^n$ distributions altogether, there must be
$$n^n-\sum_{k=1}^n(-1)^{k-1}\binom{n}k(n-k)^n=\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^n$$
good ones.
This is a special case of the explicit formula for the Stirling numbers of the second kind,
$${n\brace k}=\frac1{k!}\sum_{j=0}^k(-1)^{k-j}\binom{k}jj^n\;.$$
Note that with a change of variables this can be rewritten as
$$\frac1{n!}\sum_{j=0}^n(-1)^{n-j}\binom{n}jj^{n+k}\;,$$
and $(-1)^{n-j}=(-1)^{n+j}$; this should point you in the right direction for the second part of the question.
A: The solution of this problem and problems alike, including $k=1,2,3,\ldots$, can be obtained algorithmically. See Petkovšek's algorithm. The algorithm is explained in the book $A=B$.
A: The $n^{\text{th}}$ repeated difference of a degree $m$ polynomial is $0$ if $n\gt m$:
$$
\begin{align}
\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}\binom{k}{m}
&=\sum_{k=0}^n(-1)^{n-k}\binom{n}{m}\binom{n-m}{n-k}\\
&=\binom{n}{m}0^{n-m}\tag{1}
\end{align}
$$
If $n=m$, $(1)$ says that the polynomial in $k$, $\binom{k}{n}$, has an $n^{\text{th}}$ repeated difference of $1$.
It is not difficult to see that we can find $a_m$ so that
$$
k^n=n!\binom{k}{n}+\sum_{m\lt n}a_m\binom{k}{m}\tag{2}
$$
Thus, $(1)$ and $(2)$ say
$$
\begin{align}
\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^n
&=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}\left(n!\binom{k}{n}+\sum_{m\lt n}a_m\binom{k}{m}\right)\\
&=n!\tag{3}
\end{align}
$$
