Prove that for every $x,n \in \mathbb{N}$ holds


This is so called MacMillan Double Binomial Sum, see Mathworld - Power, equation 12.


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

  • $\begingroup$ Thank you for presenting the connection to Stirling numbers, I have added this proof to my answer below. (+1). $\endgroup$ – 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


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.

  • $\begingroup$ 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$$ ? $\endgroup$ – Petro Kolosov Apr 6 at 9:11
  • $\begingroup$ It expresses the linear transformation between two bases for the space of univariate polynomials. $\endgroup$ – Yuval Filmus Apr 6 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.