Proving a complex sum equals factorial

Question

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!

Answer 1

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.

Answer 2

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

Answer 3

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