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

The successive difference of powers of integers leads to factorial of that power.

I think this is the formula

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

But I found no proof on internet.

Please give me a proof for it. Is for any value of $l$ it satisfies ?

Edit: Per the Answer below, here $l$ should have been $n$, else it's false.

-

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

-
.. So the formula $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$ is valid for any value of $l$ or valid only if $l=n$ – hanugm Dec 3 '13 at 21:22
(+1) Beautiful answer. – Jack D'Aurizio Jan 11 '15 at 23:54

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

-
Thanku . How to extend it for all numbers ? ... – hanugm Dec 3 '13 at 19:22
I mean for $(l-k)^n$ inside sigma ...... – hanugm Dec 3 '13 at 19:25
@hanu I think it is true only when $l=n$. – N. S. Dec 3 '13 at 20:11
@N.S. It is true for any $l$. I show it algebraically in my answer, but I haven't tried to think of a combinatorial argument. It would most likely involve the Inclusion-Exclusion Principle, however. – robjohn Dec 4 '13 at 16:19
I might be wrong but shouldn't the expression for PIE be $=\binom{m}{1}(m-1)^n-\binom{m}{2}(m-2)^n+\binom{m}{3}(m-3)^n-...$ ? – r9m Nov 17 '14 at 9:34

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

-

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

-
Very nice. Upvoted. You might have mentioned that in the sums being treated in eq. $(3)$ the coefficient on $j^n$ is actually $(-1)^n$ which cancels the $(-1)^n$ in the outer sum to produce the desired result. Very useful the fact that when writing a polynomial as a sum of binomial coefficients only the highest degree term contributes to the leading coefficient and we know what that contribution is. – Marko Riedel Dec 4 '13 at 0:57
@MarkoRiedel: thanks! To be explicit, I added equation $(4)$. – robjohn Dec 4 '13 at 1:36

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.

-