Prove that $x^n=\sum_{k=1}^{n}\sum_{j=1}^{k}(-1)^{k-j}\binom{k}{j}\binom{x}{k}j^n$ Prove that for every $x,n \in \mathbb{N}$ holds
$$x^n=\sum_{k=1}^{n}\sum_{j=1}^{k}(-1)^{k-j}\binom{k}{j}\binom{x}{k}j^n$$
This is so called MacMillan Double Binomial Sum, see Mathworld - Power, equation 12.
 A: Here is a combinatorial proof. Both sides count the number of functions from a set $N$ of size $n$ to a set $X$ of size $x$. (This part assumes $x$ is a positive integer; however, if a polynomial equation holds for infinitely many inputs, then it holds for all complex inputs as well).
To choose a function $N\to X$, first choose the size of the range, $k$, and then choose the range in $\binom{x}k$ ways. Letting $K$ be the chosen elements, you must then choose a surjection from $N\to K$. This is done using the principle of inclusion exclusion. First, take all $k^n$ functions from $N$ to $K$, then for each element of $K$, subtract the $(k-1)^n$ functions whose range does not contain that element. But functions whose range misses two elements of $K$ were doubly subtracted, so they must be added back in, etc. The result is
$$
\sum_{j=0}^{k-1}(-1)^j\binom{k}j(k-j)^n=\sum_{j=1}^k(-1)^{k-j}\binom{k}jj^n
$$
Finally, multiply this by $\binom{x}k$ and sum over $k$.
A: We will prove more generally that if $m \geq n$ then
$$
x^n = \sum_{0 \le j \le k \le m} (-1)^{k-j} \binom{k}{j} \binom{x}{k} j^n.
$$
The proof is by induction on $n$. When $n = 0$, the right-hand side is
$$
\sum_{0 \le j \le k \le m} (-1)^{k-j} \binom{k}{j} \binom{x}{k} =
\sum_{0 \le k \le m} (1+(-1))^k \binom{x}{k} = x^0.
$$
Now let us assume that the claim holds for some $n-1$, and prove it for $n$. Since $n \geq 1$, we can start the sum at $j \geq 1$.
Since
$$
\binom{k}{j} \binom{x}{k} j^n = x \binom{k-1}{j-1} \binom{x-1}{k-1} j^{n-1},
$$
the right-hand side equals
$$
x \sum_{1 \le j \le k \le m} (-1)^{(k-1)-(j-1)} \binom{k-1}{j-1} \binom{x-1}{k-1} j^{n-1}.
$$
Writing $j^{n-1}$ as $((j-1)+1)^{n-1}$, this equals
$$
x \sum_{\ell=0}^{n-1} \binom{n-1}{\ell} \sum_{0 \le j-1 \le k-1 \le m-1} (-1)^{(k-1)-(j-1)} \binom{k-1}{j-1} \binom{x-1}{k-1} (j-1)^\ell.
$$
Applying the induction hypothesis, this equals
$$
x \sum_{\ell=0}^{n-1} \binom{n-1}{\ell} (x-1)^\ell = x ((x-1)+1)^{n-1} = x^n.
$$

There should also be a combinatorial proof using inclusion-exclusion.
