Expressing a factorial as difference of powers: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$?

Question

The successive difference of powers of integers leads to factorial of that power. Here's the formula:

$$\sum_{r=0}^{n}\binom{n}{r}(-1)^r(n-r)^n=n!$$

Can anyone give a proof of this result?

Note: The original question was to prove the more general

$$\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$$

for an integer $l$, which some of the answers address.

Answer 1

Let $A:=\{ x_1,..,x_n \}$ and $B=\{y_1,..,y_m \}$.

Lets count the number of onto functions $f:A \to B$. There are $m^n$ functions from $A$ to $B$. Lets count now the ones which are not onto:

Define

$$P_i= \{ f : A \to B |y_i \notin f(A) \}$$

Then we need to figure out the cardinality of $\cup_i P_i$.

By the inclusion exclusion principle

$$|P_1 \cup P_2 ..\cup P_m |=\sum |P_i|-\sum |P_i \cap P_j|+\sum |P_i \cap P_j \cap P_k| -... \\=\binom{m}{1}(m-1)^n-\binom{m}{2}(m-2)^n+\binom{m}{3}(m-3)^n-... $$

Thus in total there are

$$m^n-\binom{m}{1}(m-1)^n+\binom{m}{2}(m-2)^n-\binom{m}{3}(m-3)^n-...=\sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n$$

When $n=m$ the number of onto functions is

$$\sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)^n$$

But any function $f: \{ x_1,..,x_n \} \to\{y_1,..,y_n \}$ is onto if and only if it is a bijection. Thus the number of onto functions is equal to the number of bijections, which is $n!$.

Hence

$$\sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)^n=n!$$

Answer 2

This identity also has an algebraic proof. Suppose the sum we are trying to evaluate is given by $$\sum_{k=0}^n {n\choose k} (-1)^k (n-k)^{n}.$$

Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that \begin{align} A(z) B(z) &= \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ &= \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!} \end{align} i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Now in the present case we clearly have $$A(z) = \sum_{q\ge 0} (-1)^q \frac{z^q}{q!} = \exp(-z).$$ Furthermore we have $$B_n(z) = \sum_{q\ge 1} q^{n} \frac{z^q}{q!} = \exp(z) \sum_{k=1}^{n} {n\brace k} z^k,$$ as can be seen by induction. For $n=1$ we have $$B_1(z) = \sum_{q\ge 1} q \frac{z^q}{q!} = z \sum_{q\ge 1} \frac{z^{q-1}}{(q-1)!} = \exp(z)\times z.$$ Now using the induction hypothesis we have $$B_{n+1}(z) = z \frac{d}{dz} B_n(z) = z \exp(z) \sum_{k=1}^{n} {n\brace k} k z^{k-1} + z \exp(z) \sum_{k=1}^{n} {n\brace k} z^k.$$ This is \begin{align} & z \exp(z) \sum_{k=0}^{n-1} {n\brace k+1} (k+1) z^k + z \exp(z) \sum_{k=1}^{n} {n\brace k} z^k \\ &= z \exp(z) \left({n\brace 1} + \sum_{k=1}^{n-1} \left({n\brace k+1} (k+1)+{n\brace k}\right)z^k+ {n\brace n} z^{n}\right) \\ &= z \exp(z) \left({n+1\brace 1} + \sum_{k=1}^{n-1} {n+1\brace k+1} z^k + {n+1\brace n+1} z^{n}\right) \\ &= \exp(z) \left({n+1\brace 1} z + \sum_{k=1}^{n-1} {n+1\brace k+1} z^{k+1} + {n+1\brace n+1} z^{n+1}\right) = \exp(z) \sum_{k=1}^{n+1} {n+1\brace k} z^k. \end{align}

Returning to the original problem we find that the sum has the value $$n! [z^n] A(z) B_n(z) = n! [z^n] \sum_{k=1}^{n} {n\brace k} z^k = n! {n\brace n} = n!$$ which was to be shown.

A useful exercise in the algebra of Stirling numbers and binomial coefficients. Here is a MSE link that points to another calculation of the same type.

Addendum. In response to the comment we can actually show that $$\sum_{k=0}^n {n\choose k} (-1)^k (l-k)^{n}$$ for $l$ an integer.

Observe that $$l-k = (n-k)+(l-n)$$ and put $p=l-n.$ Using the same setup as before we now have \begin{align} B(z) &= \sum_{q\ge 0} (q+p)^n \frac{z^q}{q!} = \sum_{q\ge 0} \sum_{m=0}^n {n\choose m} q^m p^{n-m} \frac{z^q}{q!} \\ &= \sum_{q\ge 0} p^n \frac{z^q}{q!} + \sum_{q\ge 0} \sum_{m=1}^n {n\choose m} q^m p^{n-m} \frac{z^q}{q!} = \exp(z) p^n +\sum_{m=1}^n {n\choose m} p^{n-m} \sum_{q\ge 0} q^m \frac{z^q}{q!} \\ &= \exp(z) p^n + \exp(z) \sum_{m=1}^n {n\choose m} p^{n-m} \sum_{k=1}^m {m\brace k} z^k. \end{align} This formula also holds for $p=0$ if we assume that $0^0=1$, in which case it produces the first formula we derived above. It follows that $$n! [z^n] A(z) B_n(z) = n! [z^n] \left(p^n+\sum_{m=1}^n {n\choose m} p^{n-m} \sum_{k=1}^m {m\brace k} z^k\right) = n! {n\choose n} {n\brace n} = n!$$ thereby showing the result for all $l.$

Addendum Oct 10 2016. There is really nothing to prove here as the formula $$\frac{1}{n!} \sum_{k=0}^n {n\choose k} (-1)^{n-k} k^m$$ by definition gives the Stirling number of the second kind $${m\brace n}.$$

Answer 3

In this answer are three different proofs of this cancellation lemma: $$ \sum_{j=k}^n(-1)^{n-j}\binom{n}{j}\binom{j}{k} =\left\{\begin{array}{} 1&\text{if }n=k\\ 0&\text{otherwise} \end{array}\right.\tag{1} $$ Inductively, we can see that any polynomial in $j$ of degree $m$ can be written uniquely as $$ \sum_{k=0}^mc_k\binom{j}{k}\tag{2} $$ where the coefficient of $j^m$ is $\dfrac{c_m}{m!}$.

Putting $(1)$ and $(2)$ together, for $m\le n$, we have $$ \begin{align} \sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}\sum_{k=0}^mc_k\binom{j}{k} &=\sum_{k=0}^m\sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}\binom{j}{k}\\ &=c_n\tag{3} \end{align} $$ If $m\lt n$, then $c_n=0$. If $m=n$, then $c_n$ is $n!$ times the coefficient of $j^n$.

---

Applying $(3)$ $$ \begin{align} \sum_{r=0}^n\binom{n}{r}(-1)^r(l-r)^n &=\sum_{r=0}^n(-1)^{n-r}\binom{n}{r}(r-l)^n\\ &=n!\tag{4} \end{align} $$ because, for any $l$, $(r-l)^n$ is a degree $n$ polynomial in $r$ in which the coefficient of $r^n$ is $1$.

Answer 4

Using the definition of the Exponential Series,

$$e^x=\sum_{0\le r<\infty}\frac{x^r}{r!} \implies e^x-1=x+\frac{x^2}{2!}++\frac{x^3}{3!}+\cdots$$

Taking $n$th power, $$ (e^x-1)^n=\left(x+\frac{x^2}{2!}++\frac{x^3}{3!}+\cdots\right)^n$$

$$\text{Now, }(e^x-1)^n=e^{nx}-\binom n1e^{(n-1)x}+\binom n2e^{(n-2)x}-\cdots$$

$$=\sum_{0\le r<\infty}\frac{(nx)^r}{r!}-\binom n1\sum_{0\le r<\infty}\frac{\{(n-1)x\}^r}{r!}+\binom n2\sum_{0\le r<\infty}\frac{\{(n-2)x\}^r}{r!}-\cdots$$

So, the coefficient of $x^r$ in $(e^x-1)^n$

$$\frac{n^r}{r!}-\binom n1\frac{(n-1)^r}{r!}+\binom n2\frac{(n-2)^r}{r!}-\cdots$$

$$\text{ Again, } \left(x+\frac{x^2}{2!}++\frac{x^3}{3!}+\cdots\right)^n=x^n+\text{ the higher powers of } x$$

Equating we get

$$\frac{n^r}{r!}-\binom n1\frac{(n-1)^r}{r!}+\binom n2\frac{(n-2)^r}{r!}-\cdots=\begin{cases} 0 &\mbox{if } 0\le r< n \\ 1 & \mbox{if } r=n \end{cases} $$

Answer 5

Suppose we are trying to evaluate $$\sum_{q=0}^n {n\choose q} (-1)^q (k-q)^n.$$ Observe that $$(k-q)^n = \frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((k-q)z) \; dz.$$

This gives for the sum the integral $$\frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{q=0}^n {n\choose q} (-1)^q \exp((k-q)z) \; dz \\ = \frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{\exp(kz)}{z^{n+1}} \sum_{q=0}^n {n\choose q} (-1)^q \exp(-qz) \; dz \\ = \frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{\exp(kz)}{z^{n+1}} (1-\exp(-z))^n \; dz.$$

Observe that $$1-\exp(-z) = z-\frac{1}{2}z^2+\frac{1}{6}z^3-\cdots$$ so $(1-\exp(-z))^n$ starts at $z^n$, which means that the residue is one ($\exp(kz)$ starts at $z^0$), giving $$n!$$ as the end result.

Answer 6

In the following we use the coefficient of operator $[z^r]$ to denote the coefficient of $z^r$ in a series. This way we can write e.g. \begin{align*} \binom{n}{r}=[z^r](1+z)^n\qquad\text{and}\qquad r^n=n![z^n]e^{rz} \end{align*}

We obtain for $n\geq 0$ and $l\in\mathbb{C}$ \begin{align*} \sum_{r=0}^n&\binom{n}{r}(-1)^r(l-r)^n\\ &=\sum_{r=0}^\infty[z^r](1+z)^n(-1)^rn![u^n]e^{(l-r)u}\tag{1}\\ &=n![u^n]e^{lu}\sum_{r=0}^\infty\left(-e^{-u}\right)^r[z^r](1+z)^n\tag{2}\\ &=n![u^n]e^{lu}\left(1-e^{-u}\right)^n\tag{3}\\ &=n![u^n]u^n\tag{4}\\ &=n!\\ \end{align*} and the claim follows.

Please note the formula is valid for any $l$.

Comment:

• In (1) we apply the coefficient of operator to $\binom{n}{r}$ and to $(l-r)^n$ using $e^{(l-r)u}$. We also extend the limit to infty without changing anything since we are adding zeros only.

• In (2) we do some rearrangements using the linearity of the coefficient of operator.

• In (3) we apply the substitution rule \begin{align*} A(u)=\sum_{r=0}^\infty a_r u^r=\sum_{r=0}^\infty u^r [z^r]A(z) \end{align*}

• In (4) we consider the series expansion \begin{align*} e^{lu}(1-e^{-u})^n&=(1+lu+\cdots)\left(u-\frac{u^2}{2}+\cdots\right)^n\\ &=1\cdot\left(u^n\mp\text{powers of }u\text{ greater than }n\cdots\right) \end{align*} and need only to respect the $u$-term with power equal to $n$.