Prove that $x^n=\sum_{k=1}^{n}\sum_{j=1}^{k}(-1)^{k-j}\binom{k}{j}\binom{x}{k}j^n$

Question

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.

Answer 1

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

Answer 2

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.