Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

up vote 4 down vote accepted

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

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

share|improve this answer
    
.. 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$ –  hanu Dec 3 '13 at 21:22

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{n}{1}(m-1)^n-\binom{n}{2}(m-2)^n+\binom{n}{3}(m-3)^n-... $$

Thus in total there are

$$m^n-\binom{n}{1}(m-1)^n+\binom{n}{2}(m-2)^n-\binom{n}{3}(m-3)^n-...=\sum_{k=0}^m (-1)^k\binom{n}{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!$$

share|improve this answer
    
Thanku . How to extend it for all numbers ? ... –  hanu Dec 3 '13 at 19:22
    
I mean for $(l-k)^n$ inside sigma ...... –  hanu 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

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

share|improve this answer
    
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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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