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.

3 Answers

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

• Thank you for presenting the connection to Stirling numbers, I have added this proof to my answer below. (+1). – Marko Riedel Apr 6 at 18:56

Starting from

$$x^n = \sum_{k=1}^n \sum_{j=1}^k (-1)^{k-j} {k\choose j} {x\choose k} j^n$$

where $$x$$ is an integer, or even a complex number and we view it as a variable so that the RHS is a polynomial in $$x$$ we extract the coefficient on $$[x^q]$$ where owing to $$k\ge 1$$ we have $$1\le q\le n.$$

$$[x^q] \sum_{k=1}^n \sum_{j=1}^k (-1)^{k-j} {k\choose j} {x\choose k} j^n \\ = \sum_{k=q}^n \frac{1}{k!} \sum_{j=1}^k (-1)^{k-j} {k\choose j} (-1)^{k+q} {k\brack q} j^n \\ = \sum_{k=q}^n \frac{1}{k!} {k\brack q} \sum_{j=1}^k (-1)^{j} {k\choose j} (-1)^{q} j^n \\ = (-1)^q \sum_{k=q}^n \frac{1}{k!} {k\brack q} \sum_{j=1}^k (-1)^j {k\choose j} j^n \\ = (-1)^q n! [z^n] \sum_{k=q}^n \frac{1}{k!} {k\brack q} \sum_{j=1}^k (-1)^j {k\choose j} \exp(jz) \\ = (-1)^q n! [z^n] \sum_{k=q}^n \frac{1}{k!} {k\brack q} (-1+(1-\exp(z))^k).$$

Now we may suppose that $$n\ge 1$$ and $$n\in \mathbb{N}$$ since when $$n=0$$ we get $$1$$ on the LHS and zero on the RHS due to the sum being empty.

Therefore we may continue with

$$(-1)^q n! [z^n] \sum_{k=q}^n \frac{1}{k!} {k\brack q} (1-\exp(z))^k.$$

Observe that

$$1-\exp(z) = - z - z^2/2 - z^3/6 - \cdots$$

so there no constant coefficient and

$$(1-\exp(z))^k = (-1)^k z^k + \cdots.$$

Hence we may extend the sum in $$k$$ to infinity because there is no contribution when $$k\gt n:$$

$$(-1)^q n! [z^n] \sum_{k\ge q} \frac{1}{k!} {k\brack q} (1-\exp(z))^k.$$

What we have here is the EGF of the Stirling numbers of the first kind which is

$$\sum_{k\ge q} \frac{1}{k!} {k\brack q} w^k = \frac{1}{q!} \left(\log\frac{1}{1-w}\right)^q.$$

so we obtain for the main sum

$$(-1)^q n! [z^n] \frac{1}{q!} \left(\log\frac{1}{1-(1-\exp(z))}\right)^q \\ = (-1)^q n! [z^n] \frac{1}{q!} (\log\exp(-z))^q = (-1)^q n! [z^n] \frac{1}{q!} (-1)^q z^q.$$

Now this is obviously equal to zero when $$q\lt n.$$ We get for $$q=n$$:

$$(-1)^n n! [z^n] \frac{1}{n!} (-1)^n z^n = (-1)^n n! \frac{1}{n!} (-1)^n = 1$$

and we have the claim.

Remark. In order to be fully rigorous here we need to prove the formal power series identity

$$\log\frac{1}{1-(1-\exp(z))} = -z.$$

This computation was done at the following MSE link, where we start from the equivalent

$$\log\frac{1}{1+(\exp(z)-1)}.$$

Addendum. Following the work by @MikeEarnest we recognize the closed form for the Stirling numbers of the second kind, which is

$${n\brace k} = \frac{1}{k!} \sum_{j=1}^k (-1)^{k-j} {k\choose j} j^n.$$

Our claim then becomes

$$x^n = \sum_{k=1}^n {x\choose k} k! {n\brace k}.$$

With $$x$$ an integer suppose we throw $$n$$ different balls into $$x$$ different boxes, there are $$x^n$$ ways of doing this. On the other hand we may classify every distribution of balls obtained in this way by the number $$k$$ of boxes that were not empty. To get this kind of distribution we choose the $$k$$ boxes in $${x\choose k}$$ ways and partition the $$n$$ balls into $$k$$ sets in $${n\brace k}$$ ways. These $$k$$ sets can be matched to the chosen $$k$$ boxes in $$k!$$ ways and every such configuration constitutes a distribution of the balls, and we have equality.

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.

• so, it is just partial case of binomial theorem $$x^n = \sum_{k=0}^n \binom{n}{k} (x-1)^k = \sum_{k=0}^n \sum_{t=0}^k \binom{n}{k} (-1)^{k-t} x^t$$ ? – Petro Kolosov Apr 6 at 9:11
• It expresses the linear transformation between two bases for the space of univariate polynomials. – Yuval Filmus Apr 6 at 9:13