Prove $sumlimits_{j=1}^k(-1)^{k-j}j^kbinom{k}{j}=k!$ [duplicate]












20















This question already has an answer here:




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

    6 answers




In reading about A polarization identity for multilinear maps by Erik G F Thomas, I am led to prove the following combinatorial identity, which I cannot find anywhere, nor do I have any idea how to prove it.

$$sumlimits_{j=1}^k(-1)^{k-j}j^kbinom{k}{j}=k!.$$
After some reductions (including $binom{k+1}{j}=binom{k}{j}+binom{k}{j-1}$) and "simplifications", I am still stuck and have no clues how to proceed.

I do not know if this is true, either, though I think it should be.





Any help or reference is sincerely welcomed, thanks in advance.










share|cite|improve this question















marked as duplicate by Marc van Leeuwen, Community May 23 '16 at 8:15


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.















  • Just noticed it is bionomial theorem for $(-1+j)^k$ with $jin mathbb{N}$
    – José Osorio
    May 22 '16 at 11:06






  • 4




    @JoséOsorio But $j$ is not fixed.
    – almagest
    May 22 '16 at 11:10






  • 2




    Isn't this the combinatorial formula for the number of surjections from the set of $k$ elements to itself? Proof by Inclusion-Exclusion.
    – lulu
    May 22 '16 at 11:33






  • 1




    See also (3) in web.mit.edu/~darij/www/QEDMO6P4long.pdf for an algebraic proof.
    – darij grinberg
    May 22 '16 at 13:30








  • 1




    Notice that I prefer the sum to start at $j=0$; otherwise the equality is false for $k=0$.
    – darij grinberg
    May 22 '16 at 13:32
















20















This question already has an answer here:




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

    6 answers




In reading about A polarization identity for multilinear maps by Erik G F Thomas, I am led to prove the following combinatorial identity, which I cannot find anywhere, nor do I have any idea how to prove it.

$$sumlimits_{j=1}^k(-1)^{k-j}j^kbinom{k}{j}=k!.$$
After some reductions (including $binom{k+1}{j}=binom{k}{j}+binom{k}{j-1}$) and "simplifications", I am still stuck and have no clues how to proceed.

I do not know if this is true, either, though I think it should be.





Any help or reference is sincerely welcomed, thanks in advance.










share|cite|improve this question















marked as duplicate by Marc van Leeuwen, Community May 23 '16 at 8:15


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.















  • Just noticed it is bionomial theorem for $(-1+j)^k$ with $jin mathbb{N}$
    – José Osorio
    May 22 '16 at 11:06






  • 4




    @JoséOsorio But $j$ is not fixed.
    – almagest
    May 22 '16 at 11:10






  • 2




    Isn't this the combinatorial formula for the number of surjections from the set of $k$ elements to itself? Proof by Inclusion-Exclusion.
    – lulu
    May 22 '16 at 11:33






  • 1




    See also (3) in web.mit.edu/~darij/www/QEDMO6P4long.pdf for an algebraic proof.
    – darij grinberg
    May 22 '16 at 13:30








  • 1




    Notice that I prefer the sum to start at $j=0$; otherwise the equality is false for $k=0$.
    – darij grinberg
    May 22 '16 at 13:32














20












20








20


10






This question already has an answer here:




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

    6 answers




In reading about A polarization identity for multilinear maps by Erik G F Thomas, I am led to prove the following combinatorial identity, which I cannot find anywhere, nor do I have any idea how to prove it.

$$sumlimits_{j=1}^k(-1)^{k-j}j^kbinom{k}{j}=k!.$$
After some reductions (including $binom{k+1}{j}=binom{k}{j}+binom{k}{j-1}$) and "simplifications", I am still stuck and have no clues how to proceed.

I do not know if this is true, either, though I think it should be.





Any help or reference is sincerely welcomed, thanks in advance.










share|cite|improve this question
















This question already has an answer here:




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

    6 answers




In reading about A polarization identity for multilinear maps by Erik G F Thomas, I am led to prove the following combinatorial identity, which I cannot find anywhere, nor do I have any idea how to prove it.

$$sumlimits_{j=1}^k(-1)^{k-j}j^kbinom{k}{j}=k!.$$
After some reductions (including $binom{k+1}{j}=binom{k}{j}+binom{k}{j-1}$) and "simplifications", I am still stuck and have no clues how to proceed.

I do not know if this is true, either, though I think it should be.





Any help or reference is sincerely welcomed, thanks in advance.





This question already has an answer here:




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

    6 answers








combinatorics summation binomial-coefficients factorial






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 1 at 10:31









Martin Sleziak

44.6k7115270




44.6k7115270










asked May 22 '16 at 10:56









awllower

10.3k42471




10.3k42471




marked as duplicate by Marc van Leeuwen, Community May 23 '16 at 8:15


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.






marked as duplicate by Marc van Leeuwen, Community May 23 '16 at 8:15


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.














  • Just noticed it is bionomial theorem for $(-1+j)^k$ with $jin mathbb{N}$
    – José Osorio
    May 22 '16 at 11:06






  • 4




    @JoséOsorio But $j$ is not fixed.
    – almagest
    May 22 '16 at 11:10






  • 2




    Isn't this the combinatorial formula for the number of surjections from the set of $k$ elements to itself? Proof by Inclusion-Exclusion.
    – lulu
    May 22 '16 at 11:33






  • 1




    See also (3) in web.mit.edu/~darij/www/QEDMO6P4long.pdf for an algebraic proof.
    – darij grinberg
    May 22 '16 at 13:30








  • 1




    Notice that I prefer the sum to start at $j=0$; otherwise the equality is false for $k=0$.
    – darij grinberg
    May 22 '16 at 13:32


















  • Just noticed it is bionomial theorem for $(-1+j)^k$ with $jin mathbb{N}$
    – José Osorio
    May 22 '16 at 11:06






  • 4




    @JoséOsorio But $j$ is not fixed.
    – almagest
    May 22 '16 at 11:10






  • 2




    Isn't this the combinatorial formula for the number of surjections from the set of $k$ elements to itself? Proof by Inclusion-Exclusion.
    – lulu
    May 22 '16 at 11:33






  • 1




    See also (3) in web.mit.edu/~darij/www/QEDMO6P4long.pdf for an algebraic proof.
    – darij grinberg
    May 22 '16 at 13:30








  • 1




    Notice that I prefer the sum to start at $j=0$; otherwise the equality is false for $k=0$.
    – darij grinberg
    May 22 '16 at 13:32
















Just noticed it is bionomial theorem for $(-1+j)^k$ with $jin mathbb{N}$
– José Osorio
May 22 '16 at 11:06




Just noticed it is bionomial theorem for $(-1+j)^k$ with $jin mathbb{N}$
– José Osorio
May 22 '16 at 11:06




4




4




@JoséOsorio But $j$ is not fixed.
– almagest
May 22 '16 at 11:10




@JoséOsorio But $j$ is not fixed.
– almagest
May 22 '16 at 11:10




2




2




Isn't this the combinatorial formula for the number of surjections from the set of $k$ elements to itself? Proof by Inclusion-Exclusion.
– lulu
May 22 '16 at 11:33




Isn't this the combinatorial formula for the number of surjections from the set of $k$ elements to itself? Proof by Inclusion-Exclusion.
– lulu
May 22 '16 at 11:33




1




1




See also (3) in web.mit.edu/~darij/www/QEDMO6P4long.pdf for an algebraic proof.
– darij grinberg
May 22 '16 at 13:30






See also (3) in web.mit.edu/~darij/www/QEDMO6P4long.pdf for an algebraic proof.
– darij grinberg
May 22 '16 at 13:30






1




1




Notice that I prefer the sum to start at $j=0$; otherwise the equality is false for $k=0$.
– darij grinberg
May 22 '16 at 13:32




Notice that I prefer the sum to start at $j=0$; otherwise the equality is false for $k=0$.
– darij grinberg
May 22 '16 at 13:32










5 Answers
5






active

oldest

votes


















13














Let $L$ be the collection of sequences indexed by $mathbb{N}$ taking values in $mathbb{R}$.
$$L = { (x_0, x_1, x_2, ldots ) : x_i in mathbb{R} }$$
$L$ will be a vector space with respect to componentwise addition and scalar multiplication.

Define a linear map $D$ on $L$ by
$$L ni x = (x_0, x_1, x_2, ldots ) quadmapstoquad Dx = (x_1, x_2, ldots ) in L$$
The result of applying $D - 1$ to a sequence $x$ is the finite difference of $x$.
$$left[ (D-1)x right]_n = x_{n+1} - x_n$$



If you apply $(D-1)^k$ to the sequence $u = (n^k)_{n=0}^infty$, you will find



$$left[ (D-1)^k u right]_n
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j} left[D^j uright]_n
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j} u_{n+j}
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j}(j+n)^k
$$
When $n = 0$, this is the LHS of the equality at hand.



To see LHS of your equality is indeed equal to the RHS, you can use following fact:




If $v$ is a sequence whose value is a polynomial in the index $n$, i.e.
$$v_n = a_p n^p + a_{p-1} n^{p-1} + cdots + a_0$$
for some constants $a_p, a_{p-1},ldots, a_0$, the
finite difference of $v$ will be a polynomial in $n$ with degree one less.
Furthermore, the leading coefficient is multiplied by a factor $p$. i.e.
$$left[(D-1)vright]_n = p a_p n^{p-1} + cdots$$




Apply these $k$ times to the sequence $u = (n^k)_{n=0}^infty$, you find
$$sum_{j=0}^{k}(-1)^{k-j}binom{k}{j}(j+n)^k = left[ (D-1)^k u right]_n = (D-1)^k n^k = k! n^0 = k!$$
which is a constant independent of $n$ and equal to RHS of the equality at hand.






share|cite|improve this answer























  • Thanks! I have conjectured the last formula as a possible way to prove the special case, but had no idea how to prove it. This helps a lot. :)
    – awllower
    May 22 '16 at 12:17





















13














A combinatorial answer.



The right-hand side is the number of permutations of ${0, 1, dots, k-1}$.



I'll let $k=5$ for concreteness.



We count the permutations in another way. Take a $5$-tuple drawn from ${0,1,dots,4}$ - that is, a member of $5^5$. This is probably not a permutations - for example, it might be $00000$.



Remove anything which does not contain a $4$. That is, remove anything which can be drawn from $4^5$.
This leaves all the permutations, but also leaves things like $44444$,
so in fact we should be removing anything which can be drawn from ${ 1, 2, 3, 4}$ and from ${ 0, 2, 3, 4}$ and so on.



That is, we remove $4^5$ things $binom{5}{1} = binom{5}{4}$ times.



OK, we've left all the permutations, but now we've removed some things more than once: we removed $00000$ because it doesn't contain a $4$ but also because it doesn't contain a $3$, for instance.
Generally, we've removed twice anything which has two things it doesn't contain, and we've removed three times anything which has three things it doesn't contain, and so on.
We need to add them back in enough times: we need to add once anything which has two things it doesn't contain, add twice anything which has three things it doesn't contain, and so on.



Add in $3^5$ things $binom{5}{2}$ times: namely, add in anything which does not contain a $0$ and does not contain a $1$, then add in anything which does not contain a $0$ and does not contain a $2$, then… then add in anything which does not contain a $3$ and does not contain a $4$.
We've re-added anything which has two things it doesn't contain, but we've re-added $binom{3}{2}$ times anything which has three things it doesn't contain, re-added $binom{4}{2}$ times anything which has four things it doesn't contain, and so on.



Repeat this procedure of adding and subtracting until we eventually finish.






share|cite|improve this answer























  • Thanks: I was dinning after the post, and my classmate and I just came up with this argument while dining! Quite a coincidence! :D Still thanks for the help!
    – awllower
    May 22 '16 at 12:16





















6














As lulu said, this can be proved by inclusion-exclusion theorem. We have
begin{equation}
|cup_{i=1}^k A_i|=sum_{j=1}^k(-1)^{j+1}(sum_{1leq i_1<...<i_jleq k}|A_{i_1}cap...cap A_{i_j}|).
end{equation}
Now let $A_i$ be the subset of function from $[k]$ to $[k]$ such that $i$ is not an image. Then lhs of the equation is equal to $k^k-k!$, which means we subtrct the bijective functions from all functions. The $j$-th component of rhs is equal to $(-1)^{j+1}begin{pmatrix}k\jend{pmatrix}(k-j)^k$, which means that we choose $j$ elements such that they are not images, and the $k$ elements only have then $k-j$ possibilities to choose an image. Now let $tilde{j}=k-j$, and inserting this into the equation, you will find the solution of the given form.





More details: we obtain then
begin{align}
k^k-k!&=sum_{j=0}^{k-1}(-1)^{k-j+1}begin{pmatrix}k\k-jend{pmatrix}j^k\
&=-1sum_{j=0}^{k-1}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k\
&=-1sum_{j=1}^{k}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k+(-1)^{k-k}begin{pmatrix}k\kend{pmatrix}k^k\
&=-1sum_{j=1}^{k}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k+k^k.
end{align}
Both sides subtrct $k^k$ and devided by $-1$, we obtain the result.






share|cite|improve this answer























  • I am confused: where is the $k!$ factor? Also, I think $(-1)^{j+1}$ becomes $(-1)^{k-overline{j}+1},$ but the factor in the equation in the question is $(-1)^{k-j} ?$
    – awllower
    May 22 '16 at 12:28












  • @awllower notice your index of $tilde{j}$ only varies form $0$ to $k-1$, and in your formula the index is from $1$ to $k$, so there are some more terms appear, and they will give you $k!$.
    – Yongyong
    May 22 '16 at 12:30










  • @awllower for the $-1$ term, you have the identity $(-1)^{k-j+1}=(-1)(-1)^{k-j}$.
    – Yongyong
    May 22 '16 at 12:31










  • ok let me add the details in the answer :)
    – Yongyong
    May 22 '16 at 12:33










  • @awllower I think I also made an error, the lhs is then $k^k-k!$, but not the former one, sorry for the confusion.
    – Yongyong
    May 22 '16 at 12:50



















5














In this answer, it is shown that for any $l$,
$$
begin{align}
sum_{r=0}^nbinom{n}{r}(-1)^r(l-r)^n
&=sum_{r=0}^n(-1)^{n-r}binom{n}{r}(r-l)^n\
&=n!
end{align}
$$
The given identity is this identity using $l=0$.






share|cite|improve this answer























  • Thanks for referencing the question, where many nice answers are!
    – awllower
    May 22 '16 at 14:06



















2














Here is a variant based upon the coefficient of operator $[z^k]$ used to denote the coefficient of $z^k$ in a series. This way we can write e.g.
begin{align*}
[z^j](1+z)^k=binom{k}{j}qquadqquadtext{or}qquadqquad k![z^k]e^{jz}=j^k
end{align*}




We obtain
begin{align*}
sum_{j=1}^k(-1)^{k-j}j^kbinom{k}{j}
&=sum_{j=0}^infty(-1)^{k-j}k![z^k]e^{jz}[u^k](1+u)^ktag{1}\
&=(-1)^kk![z^k]sum_{j=0}^{infty}left(-e^{z}right)^j[u^k](1+u)^ktag{2}\
&=(-1)^kk![z^k](1-e^z)^ktag{3}\
&=k![z^k]left(z+frac{z^2}{2!}+frac{z^3}{3!}+cdotsright)^ktag{4}\
&=k!
end{align*}
and the claim follows.




Comment:




  • In (1) we apply the coefficient of operator twice and extend the lower and upper limit of the series without changing anything, since we add only zeros.


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


  • In (3) we use the substitution rule with $u=-e^z$:



begin{align*}
A(z)=sum_{j=0}^infty a_jz^j=sum_{j=0}^infty z^j [u^k]A(u)
end{align*}




  • In (4) we see that in each of the $k$ factors $(e^z-1)$ only $z^1$ provide a contribution to $z^k$.






share|cite|improve this answer























  • Thanks for this interesting use of the coefficient operator which makes the approach through exponential functions more natural. :)
    – awllower
    May 23 '16 at 8:16










  • @awllower: You're welcome! :-)
    – Markus Scheuer
    May 23 '16 at 8:28


















5 Answers
5






active

oldest

votes








5 Answers
5






active

oldest

votes









active

oldest

votes






active

oldest

votes









13














Let $L$ be the collection of sequences indexed by $mathbb{N}$ taking values in $mathbb{R}$.
$$L = { (x_0, x_1, x_2, ldots ) : x_i in mathbb{R} }$$
$L$ will be a vector space with respect to componentwise addition and scalar multiplication.

Define a linear map $D$ on $L$ by
$$L ni x = (x_0, x_1, x_2, ldots ) quadmapstoquad Dx = (x_1, x_2, ldots ) in L$$
The result of applying $D - 1$ to a sequence $x$ is the finite difference of $x$.
$$left[ (D-1)x right]_n = x_{n+1} - x_n$$



If you apply $(D-1)^k$ to the sequence $u = (n^k)_{n=0}^infty$, you will find



$$left[ (D-1)^k u right]_n
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j} left[D^j uright]_n
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j} u_{n+j}
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j}(j+n)^k
$$
When $n = 0$, this is the LHS of the equality at hand.



To see LHS of your equality is indeed equal to the RHS, you can use following fact:




If $v$ is a sequence whose value is a polynomial in the index $n$, i.e.
$$v_n = a_p n^p + a_{p-1} n^{p-1} + cdots + a_0$$
for some constants $a_p, a_{p-1},ldots, a_0$, the
finite difference of $v$ will be a polynomial in $n$ with degree one less.
Furthermore, the leading coefficient is multiplied by a factor $p$. i.e.
$$left[(D-1)vright]_n = p a_p n^{p-1} + cdots$$




Apply these $k$ times to the sequence $u = (n^k)_{n=0}^infty$, you find
$$sum_{j=0}^{k}(-1)^{k-j}binom{k}{j}(j+n)^k = left[ (D-1)^k u right]_n = (D-1)^k n^k = k! n^0 = k!$$
which is a constant independent of $n$ and equal to RHS of the equality at hand.






share|cite|improve this answer























  • Thanks! I have conjectured the last formula as a possible way to prove the special case, but had no idea how to prove it. This helps a lot. :)
    – awllower
    May 22 '16 at 12:17


















13














Let $L$ be the collection of sequences indexed by $mathbb{N}$ taking values in $mathbb{R}$.
$$L = { (x_0, x_1, x_2, ldots ) : x_i in mathbb{R} }$$
$L$ will be a vector space with respect to componentwise addition and scalar multiplication.

Define a linear map $D$ on $L$ by
$$L ni x = (x_0, x_1, x_2, ldots ) quadmapstoquad Dx = (x_1, x_2, ldots ) in L$$
The result of applying $D - 1$ to a sequence $x$ is the finite difference of $x$.
$$left[ (D-1)x right]_n = x_{n+1} - x_n$$



If you apply $(D-1)^k$ to the sequence $u = (n^k)_{n=0}^infty$, you will find



$$left[ (D-1)^k u right]_n
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j} left[D^j uright]_n
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j} u_{n+j}
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j}(j+n)^k
$$
When $n = 0$, this is the LHS of the equality at hand.



To see LHS of your equality is indeed equal to the RHS, you can use following fact:




If $v$ is a sequence whose value is a polynomial in the index $n$, i.e.
$$v_n = a_p n^p + a_{p-1} n^{p-1} + cdots + a_0$$
for some constants $a_p, a_{p-1},ldots, a_0$, the
finite difference of $v$ will be a polynomial in $n$ with degree one less.
Furthermore, the leading coefficient is multiplied by a factor $p$. i.e.
$$left[(D-1)vright]_n = p a_p n^{p-1} + cdots$$




Apply these $k$ times to the sequence $u = (n^k)_{n=0}^infty$, you find
$$sum_{j=0}^{k}(-1)^{k-j}binom{k}{j}(j+n)^k = left[ (D-1)^k u right]_n = (D-1)^k n^k = k! n^0 = k!$$
which is a constant independent of $n$ and equal to RHS of the equality at hand.






share|cite|improve this answer























  • Thanks! I have conjectured the last formula as a possible way to prove the special case, but had no idea how to prove it. This helps a lot. :)
    – awllower
    May 22 '16 at 12:17
















13












13








13






Let $L$ be the collection of sequences indexed by $mathbb{N}$ taking values in $mathbb{R}$.
$$L = { (x_0, x_1, x_2, ldots ) : x_i in mathbb{R} }$$
$L$ will be a vector space with respect to componentwise addition and scalar multiplication.

Define a linear map $D$ on $L$ by
$$L ni x = (x_0, x_1, x_2, ldots ) quadmapstoquad Dx = (x_1, x_2, ldots ) in L$$
The result of applying $D - 1$ to a sequence $x$ is the finite difference of $x$.
$$left[ (D-1)x right]_n = x_{n+1} - x_n$$



If you apply $(D-1)^k$ to the sequence $u = (n^k)_{n=0}^infty$, you will find



$$left[ (D-1)^k u right]_n
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j} left[D^j uright]_n
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j} u_{n+j}
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j}(j+n)^k
$$
When $n = 0$, this is the LHS of the equality at hand.



To see LHS of your equality is indeed equal to the RHS, you can use following fact:




If $v$ is a sequence whose value is a polynomial in the index $n$, i.e.
$$v_n = a_p n^p + a_{p-1} n^{p-1} + cdots + a_0$$
for some constants $a_p, a_{p-1},ldots, a_0$, the
finite difference of $v$ will be a polynomial in $n$ with degree one less.
Furthermore, the leading coefficient is multiplied by a factor $p$. i.e.
$$left[(D-1)vright]_n = p a_p n^{p-1} + cdots$$




Apply these $k$ times to the sequence $u = (n^k)_{n=0}^infty$, you find
$$sum_{j=0}^{k}(-1)^{k-j}binom{k}{j}(j+n)^k = left[ (D-1)^k u right]_n = (D-1)^k n^k = k! n^0 = k!$$
which is a constant independent of $n$ and equal to RHS of the equality at hand.






share|cite|improve this answer














Let $L$ be the collection of sequences indexed by $mathbb{N}$ taking values in $mathbb{R}$.
$$L = { (x_0, x_1, x_2, ldots ) : x_i in mathbb{R} }$$
$L$ will be a vector space with respect to componentwise addition and scalar multiplication.

Define a linear map $D$ on $L$ by
$$L ni x = (x_0, x_1, x_2, ldots ) quadmapstoquad Dx = (x_1, x_2, ldots ) in L$$
The result of applying $D - 1$ to a sequence $x$ is the finite difference of $x$.
$$left[ (D-1)x right]_n = x_{n+1} - x_n$$



If you apply $(D-1)^k$ to the sequence $u = (n^k)_{n=0}^infty$, you will find



$$left[ (D-1)^k u right]_n
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j} left[D^j uright]_n
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j} u_{n+j}
= sum_{j=0}^{k}(-1)^{k-j}binom{k}{j}(j+n)^k
$$
When $n = 0$, this is the LHS of the equality at hand.



To see LHS of your equality is indeed equal to the RHS, you can use following fact:




If $v$ is a sequence whose value is a polynomial in the index $n$, i.e.
$$v_n = a_p n^p + a_{p-1} n^{p-1} + cdots + a_0$$
for some constants $a_p, a_{p-1},ldots, a_0$, the
finite difference of $v$ will be a polynomial in $n$ with degree one less.
Furthermore, the leading coefficient is multiplied by a factor $p$. i.e.
$$left[(D-1)vright]_n = p a_p n^{p-1} + cdots$$




Apply these $k$ times to the sequence $u = (n^k)_{n=0}^infty$, you find
$$sum_{j=0}^{k}(-1)^{k-j}binom{k}{j}(j+n)^k = left[ (D-1)^k u right]_n = (D-1)^k n^k = k! n^0 = k!$$
which is a constant independent of $n$ and equal to RHS of the equality at hand.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited May 23 '16 at 0:03









Zhanxiong

8,83111031




8,83111031










answered May 22 '16 at 11:42









achille hui

95.2k5129256




95.2k5129256












  • Thanks! I have conjectured the last formula as a possible way to prove the special case, but had no idea how to prove it. This helps a lot. :)
    – awllower
    May 22 '16 at 12:17




















  • Thanks! I have conjectured the last formula as a possible way to prove the special case, but had no idea how to prove it. This helps a lot. :)
    – awllower
    May 22 '16 at 12:17


















Thanks! I have conjectured the last formula as a possible way to prove the special case, but had no idea how to prove it. This helps a lot. :)
– awllower
May 22 '16 at 12:17






Thanks! I have conjectured the last formula as a possible way to prove the special case, but had no idea how to prove it. This helps a lot. :)
– awllower
May 22 '16 at 12:17













13














A combinatorial answer.



The right-hand side is the number of permutations of ${0, 1, dots, k-1}$.



I'll let $k=5$ for concreteness.



We count the permutations in another way. Take a $5$-tuple drawn from ${0,1,dots,4}$ - that is, a member of $5^5$. This is probably not a permutations - for example, it might be $00000$.



Remove anything which does not contain a $4$. That is, remove anything which can be drawn from $4^5$.
This leaves all the permutations, but also leaves things like $44444$,
so in fact we should be removing anything which can be drawn from ${ 1, 2, 3, 4}$ and from ${ 0, 2, 3, 4}$ and so on.



That is, we remove $4^5$ things $binom{5}{1} = binom{5}{4}$ times.



OK, we've left all the permutations, but now we've removed some things more than once: we removed $00000$ because it doesn't contain a $4$ but also because it doesn't contain a $3$, for instance.
Generally, we've removed twice anything which has two things it doesn't contain, and we've removed three times anything which has three things it doesn't contain, and so on.
We need to add them back in enough times: we need to add once anything which has two things it doesn't contain, add twice anything which has three things it doesn't contain, and so on.



Add in $3^5$ things $binom{5}{2}$ times: namely, add in anything which does not contain a $0$ and does not contain a $1$, then add in anything which does not contain a $0$ and does not contain a $2$, then… then add in anything which does not contain a $3$ and does not contain a $4$.
We've re-added anything which has two things it doesn't contain, but we've re-added $binom{3}{2}$ times anything which has three things it doesn't contain, re-added $binom{4}{2}$ times anything which has four things it doesn't contain, and so on.



Repeat this procedure of adding and subtracting until we eventually finish.






share|cite|improve this answer























  • Thanks: I was dinning after the post, and my classmate and I just came up with this argument while dining! Quite a coincidence! :D Still thanks for the help!
    – awllower
    May 22 '16 at 12:16


















13














A combinatorial answer.



The right-hand side is the number of permutations of ${0, 1, dots, k-1}$.



I'll let $k=5$ for concreteness.



We count the permutations in another way. Take a $5$-tuple drawn from ${0,1,dots,4}$ - that is, a member of $5^5$. This is probably not a permutations - for example, it might be $00000$.



Remove anything which does not contain a $4$. That is, remove anything which can be drawn from $4^5$.
This leaves all the permutations, but also leaves things like $44444$,
so in fact we should be removing anything which can be drawn from ${ 1, 2, 3, 4}$ and from ${ 0, 2, 3, 4}$ and so on.



That is, we remove $4^5$ things $binom{5}{1} = binom{5}{4}$ times.



OK, we've left all the permutations, but now we've removed some things more than once: we removed $00000$ because it doesn't contain a $4$ but also because it doesn't contain a $3$, for instance.
Generally, we've removed twice anything which has two things it doesn't contain, and we've removed three times anything which has three things it doesn't contain, and so on.
We need to add them back in enough times: we need to add once anything which has two things it doesn't contain, add twice anything which has three things it doesn't contain, and so on.



Add in $3^5$ things $binom{5}{2}$ times: namely, add in anything which does not contain a $0$ and does not contain a $1$, then add in anything which does not contain a $0$ and does not contain a $2$, then… then add in anything which does not contain a $3$ and does not contain a $4$.
We've re-added anything which has two things it doesn't contain, but we've re-added $binom{3}{2}$ times anything which has three things it doesn't contain, re-added $binom{4}{2}$ times anything which has four things it doesn't contain, and so on.



Repeat this procedure of adding and subtracting until we eventually finish.






share|cite|improve this answer























  • Thanks: I was dinning after the post, and my classmate and I just came up with this argument while dining! Quite a coincidence! :D Still thanks for the help!
    – awllower
    May 22 '16 at 12:16
















13












13








13






A combinatorial answer.



The right-hand side is the number of permutations of ${0, 1, dots, k-1}$.



I'll let $k=5$ for concreteness.



We count the permutations in another way. Take a $5$-tuple drawn from ${0,1,dots,4}$ - that is, a member of $5^5$. This is probably not a permutations - for example, it might be $00000$.



Remove anything which does not contain a $4$. That is, remove anything which can be drawn from $4^5$.
This leaves all the permutations, but also leaves things like $44444$,
so in fact we should be removing anything which can be drawn from ${ 1, 2, 3, 4}$ and from ${ 0, 2, 3, 4}$ and so on.



That is, we remove $4^5$ things $binom{5}{1} = binom{5}{4}$ times.



OK, we've left all the permutations, but now we've removed some things more than once: we removed $00000$ because it doesn't contain a $4$ but also because it doesn't contain a $3$, for instance.
Generally, we've removed twice anything which has two things it doesn't contain, and we've removed three times anything which has three things it doesn't contain, and so on.
We need to add them back in enough times: we need to add once anything which has two things it doesn't contain, add twice anything which has three things it doesn't contain, and so on.



Add in $3^5$ things $binom{5}{2}$ times: namely, add in anything which does not contain a $0$ and does not contain a $1$, then add in anything which does not contain a $0$ and does not contain a $2$, then… then add in anything which does not contain a $3$ and does not contain a $4$.
We've re-added anything which has two things it doesn't contain, but we've re-added $binom{3}{2}$ times anything which has three things it doesn't contain, re-added $binom{4}{2}$ times anything which has four things it doesn't contain, and so on.



Repeat this procedure of adding and subtracting until we eventually finish.






share|cite|improve this answer














A combinatorial answer.



The right-hand side is the number of permutations of ${0, 1, dots, k-1}$.



I'll let $k=5$ for concreteness.



We count the permutations in another way. Take a $5$-tuple drawn from ${0,1,dots,4}$ - that is, a member of $5^5$. This is probably not a permutations - for example, it might be $00000$.



Remove anything which does not contain a $4$. That is, remove anything which can be drawn from $4^5$.
This leaves all the permutations, but also leaves things like $44444$,
so in fact we should be removing anything which can be drawn from ${ 1, 2, 3, 4}$ and from ${ 0, 2, 3, 4}$ and so on.



That is, we remove $4^5$ things $binom{5}{1} = binom{5}{4}$ times.



OK, we've left all the permutations, but now we've removed some things more than once: we removed $00000$ because it doesn't contain a $4$ but also because it doesn't contain a $3$, for instance.
Generally, we've removed twice anything which has two things it doesn't contain, and we've removed three times anything which has three things it doesn't contain, and so on.
We need to add them back in enough times: we need to add once anything which has two things it doesn't contain, add twice anything which has three things it doesn't contain, and so on.



Add in $3^5$ things $binom{5}{2}$ times: namely, add in anything which does not contain a $0$ and does not contain a $1$, then add in anything which does not contain a $0$ and does not contain a $2$, then… then add in anything which does not contain a $3$ and does not contain a $4$.
We've re-added anything which has two things it doesn't contain, but we've re-added $binom{3}{2}$ times anything which has three things it doesn't contain, re-added $binom{4}{2}$ times anything which has four things it doesn't contain, and so on.



Repeat this procedure of adding and subtracting until we eventually finish.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited May 22 '16 at 13:26

























answered May 22 '16 at 11:45









Patrick Stevens

28.4k52874




28.4k52874












  • Thanks: I was dinning after the post, and my classmate and I just came up with this argument while dining! Quite a coincidence! :D Still thanks for the help!
    – awllower
    May 22 '16 at 12:16




















  • Thanks: I was dinning after the post, and my classmate and I just came up with this argument while dining! Quite a coincidence! :D Still thanks for the help!
    – awllower
    May 22 '16 at 12:16


















Thanks: I was dinning after the post, and my classmate and I just came up with this argument while dining! Quite a coincidence! :D Still thanks for the help!
– awllower
May 22 '16 at 12:16






Thanks: I was dinning after the post, and my classmate and I just came up with this argument while dining! Quite a coincidence! :D Still thanks for the help!
– awllower
May 22 '16 at 12:16













6














As lulu said, this can be proved by inclusion-exclusion theorem. We have
begin{equation}
|cup_{i=1}^k A_i|=sum_{j=1}^k(-1)^{j+1}(sum_{1leq i_1<...<i_jleq k}|A_{i_1}cap...cap A_{i_j}|).
end{equation}
Now let $A_i$ be the subset of function from $[k]$ to $[k]$ such that $i$ is not an image. Then lhs of the equation is equal to $k^k-k!$, which means we subtrct the bijective functions from all functions. The $j$-th component of rhs is equal to $(-1)^{j+1}begin{pmatrix}k\jend{pmatrix}(k-j)^k$, which means that we choose $j$ elements such that they are not images, and the $k$ elements only have then $k-j$ possibilities to choose an image. Now let $tilde{j}=k-j$, and inserting this into the equation, you will find the solution of the given form.





More details: we obtain then
begin{align}
k^k-k!&=sum_{j=0}^{k-1}(-1)^{k-j+1}begin{pmatrix}k\k-jend{pmatrix}j^k\
&=-1sum_{j=0}^{k-1}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k\
&=-1sum_{j=1}^{k}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k+(-1)^{k-k}begin{pmatrix}k\kend{pmatrix}k^k\
&=-1sum_{j=1}^{k}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k+k^k.
end{align}
Both sides subtrct $k^k$ and devided by $-1$, we obtain the result.






share|cite|improve this answer























  • I am confused: where is the $k!$ factor? Also, I think $(-1)^{j+1}$ becomes $(-1)^{k-overline{j}+1},$ but the factor in the equation in the question is $(-1)^{k-j} ?$
    – awllower
    May 22 '16 at 12:28












  • @awllower notice your index of $tilde{j}$ only varies form $0$ to $k-1$, and in your formula the index is from $1$ to $k$, so there are some more terms appear, and they will give you $k!$.
    – Yongyong
    May 22 '16 at 12:30










  • @awllower for the $-1$ term, you have the identity $(-1)^{k-j+1}=(-1)(-1)^{k-j}$.
    – Yongyong
    May 22 '16 at 12:31










  • ok let me add the details in the answer :)
    – Yongyong
    May 22 '16 at 12:33










  • @awllower I think I also made an error, the lhs is then $k^k-k!$, but not the former one, sorry for the confusion.
    – Yongyong
    May 22 '16 at 12:50
















6














As lulu said, this can be proved by inclusion-exclusion theorem. We have
begin{equation}
|cup_{i=1}^k A_i|=sum_{j=1}^k(-1)^{j+1}(sum_{1leq i_1<...<i_jleq k}|A_{i_1}cap...cap A_{i_j}|).
end{equation}
Now let $A_i$ be the subset of function from $[k]$ to $[k]$ such that $i$ is not an image. Then lhs of the equation is equal to $k^k-k!$, which means we subtrct the bijective functions from all functions. The $j$-th component of rhs is equal to $(-1)^{j+1}begin{pmatrix}k\jend{pmatrix}(k-j)^k$, which means that we choose $j$ elements such that they are not images, and the $k$ elements only have then $k-j$ possibilities to choose an image. Now let $tilde{j}=k-j$, and inserting this into the equation, you will find the solution of the given form.





More details: we obtain then
begin{align}
k^k-k!&=sum_{j=0}^{k-1}(-1)^{k-j+1}begin{pmatrix}k\k-jend{pmatrix}j^k\
&=-1sum_{j=0}^{k-1}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k\
&=-1sum_{j=1}^{k}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k+(-1)^{k-k}begin{pmatrix}k\kend{pmatrix}k^k\
&=-1sum_{j=1}^{k}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k+k^k.
end{align}
Both sides subtrct $k^k$ and devided by $-1$, we obtain the result.






share|cite|improve this answer























  • I am confused: where is the $k!$ factor? Also, I think $(-1)^{j+1}$ becomes $(-1)^{k-overline{j}+1},$ but the factor in the equation in the question is $(-1)^{k-j} ?$
    – awllower
    May 22 '16 at 12:28












  • @awllower notice your index of $tilde{j}$ only varies form $0$ to $k-1$, and in your formula the index is from $1$ to $k$, so there are some more terms appear, and they will give you $k!$.
    – Yongyong
    May 22 '16 at 12:30










  • @awllower for the $-1$ term, you have the identity $(-1)^{k-j+1}=(-1)(-1)^{k-j}$.
    – Yongyong
    May 22 '16 at 12:31










  • ok let me add the details in the answer :)
    – Yongyong
    May 22 '16 at 12:33










  • @awllower I think I also made an error, the lhs is then $k^k-k!$, but not the former one, sorry for the confusion.
    – Yongyong
    May 22 '16 at 12:50














6












6








6






As lulu said, this can be proved by inclusion-exclusion theorem. We have
begin{equation}
|cup_{i=1}^k A_i|=sum_{j=1}^k(-1)^{j+1}(sum_{1leq i_1<...<i_jleq k}|A_{i_1}cap...cap A_{i_j}|).
end{equation}
Now let $A_i$ be the subset of function from $[k]$ to $[k]$ such that $i$ is not an image. Then lhs of the equation is equal to $k^k-k!$, which means we subtrct the bijective functions from all functions. The $j$-th component of rhs is equal to $(-1)^{j+1}begin{pmatrix}k\jend{pmatrix}(k-j)^k$, which means that we choose $j$ elements such that they are not images, and the $k$ elements only have then $k-j$ possibilities to choose an image. Now let $tilde{j}=k-j$, and inserting this into the equation, you will find the solution of the given form.





More details: we obtain then
begin{align}
k^k-k!&=sum_{j=0}^{k-1}(-1)^{k-j+1}begin{pmatrix}k\k-jend{pmatrix}j^k\
&=-1sum_{j=0}^{k-1}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k\
&=-1sum_{j=1}^{k}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k+(-1)^{k-k}begin{pmatrix}k\kend{pmatrix}k^k\
&=-1sum_{j=1}^{k}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k+k^k.
end{align}
Both sides subtrct $k^k$ and devided by $-1$, we obtain the result.






share|cite|improve this answer














As lulu said, this can be proved by inclusion-exclusion theorem. We have
begin{equation}
|cup_{i=1}^k A_i|=sum_{j=1}^k(-1)^{j+1}(sum_{1leq i_1<...<i_jleq k}|A_{i_1}cap...cap A_{i_j}|).
end{equation}
Now let $A_i$ be the subset of function from $[k]$ to $[k]$ such that $i$ is not an image. Then lhs of the equation is equal to $k^k-k!$, which means we subtrct the bijective functions from all functions. The $j$-th component of rhs is equal to $(-1)^{j+1}begin{pmatrix}k\jend{pmatrix}(k-j)^k$, which means that we choose $j$ elements such that they are not images, and the $k$ elements only have then $k-j$ possibilities to choose an image. Now let $tilde{j}=k-j$, and inserting this into the equation, you will find the solution of the given form.





More details: we obtain then
begin{align}
k^k-k!&=sum_{j=0}^{k-1}(-1)^{k-j+1}begin{pmatrix}k\k-jend{pmatrix}j^k\
&=-1sum_{j=0}^{k-1}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k\
&=-1sum_{j=1}^{k}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k+(-1)^{k-k}begin{pmatrix}k\kend{pmatrix}k^k\
&=-1sum_{j=1}^{k}(-1)^{k-j}begin{pmatrix}k\jend{pmatrix}j^k+k^k.
end{align}
Both sides subtrct $k^k$ and devided by $-1$, we obtain the result.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited May 22 '16 at 13:05

























answered May 22 '16 at 12:21









Yongyong

579512




579512












  • I am confused: where is the $k!$ factor? Also, I think $(-1)^{j+1}$ becomes $(-1)^{k-overline{j}+1},$ but the factor in the equation in the question is $(-1)^{k-j} ?$
    – awllower
    May 22 '16 at 12:28












  • @awllower notice your index of $tilde{j}$ only varies form $0$ to $k-1$, and in your formula the index is from $1$ to $k$, so there are some more terms appear, and they will give you $k!$.
    – Yongyong
    May 22 '16 at 12:30










  • @awllower for the $-1$ term, you have the identity $(-1)^{k-j+1}=(-1)(-1)^{k-j}$.
    – Yongyong
    May 22 '16 at 12:31










  • ok let me add the details in the answer :)
    – Yongyong
    May 22 '16 at 12:33










  • @awllower I think I also made an error, the lhs is then $k^k-k!$, but not the former one, sorry for the confusion.
    – Yongyong
    May 22 '16 at 12:50


















  • I am confused: where is the $k!$ factor? Also, I think $(-1)^{j+1}$ becomes $(-1)^{k-overline{j}+1},$ but the factor in the equation in the question is $(-1)^{k-j} ?$
    – awllower
    May 22 '16 at 12:28












  • @awllower notice your index of $tilde{j}$ only varies form $0$ to $k-1$, and in your formula the index is from $1$ to $k$, so there are some more terms appear, and they will give you $k!$.
    – Yongyong
    May 22 '16 at 12:30










  • @awllower for the $-1$ term, you have the identity $(-1)^{k-j+1}=(-1)(-1)^{k-j}$.
    – Yongyong
    May 22 '16 at 12:31










  • ok let me add the details in the answer :)
    – Yongyong
    May 22 '16 at 12:33










  • @awllower I think I also made an error, the lhs is then $k^k-k!$, but not the former one, sorry for the confusion.
    – Yongyong
    May 22 '16 at 12:50
















I am confused: where is the $k!$ factor? Also, I think $(-1)^{j+1}$ becomes $(-1)^{k-overline{j}+1},$ but the factor in the equation in the question is $(-1)^{k-j} ?$
– awllower
May 22 '16 at 12:28






I am confused: where is the $k!$ factor? Also, I think $(-1)^{j+1}$ becomes $(-1)^{k-overline{j}+1},$ but the factor in the equation in the question is $(-1)^{k-j} ?$
– awllower
May 22 '16 at 12:28














@awllower notice your index of $tilde{j}$ only varies form $0$ to $k-1$, and in your formula the index is from $1$ to $k$, so there are some more terms appear, and they will give you $k!$.
– Yongyong
May 22 '16 at 12:30




@awllower notice your index of $tilde{j}$ only varies form $0$ to $k-1$, and in your formula the index is from $1$ to $k$, so there are some more terms appear, and they will give you $k!$.
– Yongyong
May 22 '16 at 12:30












@awllower for the $-1$ term, you have the identity $(-1)^{k-j+1}=(-1)(-1)^{k-j}$.
– Yongyong
May 22 '16 at 12:31




@awllower for the $-1$ term, you have the identity $(-1)^{k-j+1}=(-1)(-1)^{k-j}$.
– Yongyong
May 22 '16 at 12:31












ok let me add the details in the answer :)
– Yongyong
May 22 '16 at 12:33




ok let me add the details in the answer :)
– Yongyong
May 22 '16 at 12:33












@awllower I think I also made an error, the lhs is then $k^k-k!$, but not the former one, sorry for the confusion.
– Yongyong
May 22 '16 at 12:50




@awllower I think I also made an error, the lhs is then $k^k-k!$, but not the former one, sorry for the confusion.
– Yongyong
May 22 '16 at 12:50











5














In this answer, it is shown that for any $l$,
$$
begin{align}
sum_{r=0}^nbinom{n}{r}(-1)^r(l-r)^n
&=sum_{r=0}^n(-1)^{n-r}binom{n}{r}(r-l)^n\
&=n!
end{align}
$$
The given identity is this identity using $l=0$.






share|cite|improve this answer























  • Thanks for referencing the question, where many nice answers are!
    – awllower
    May 22 '16 at 14:06
















5














In this answer, it is shown that for any $l$,
$$
begin{align}
sum_{r=0}^nbinom{n}{r}(-1)^r(l-r)^n
&=sum_{r=0}^n(-1)^{n-r}binom{n}{r}(r-l)^n\
&=n!
end{align}
$$
The given identity is this identity using $l=0$.






share|cite|improve this answer























  • Thanks for referencing the question, where many nice answers are!
    – awllower
    May 22 '16 at 14:06














5












5








5






In this answer, it is shown that for any $l$,
$$
begin{align}
sum_{r=0}^nbinom{n}{r}(-1)^r(l-r)^n
&=sum_{r=0}^n(-1)^{n-r}binom{n}{r}(r-l)^n\
&=n!
end{align}
$$
The given identity is this identity using $l=0$.






share|cite|improve this answer














In this answer, it is shown that for any $l$,
$$
begin{align}
sum_{r=0}^nbinom{n}{r}(-1)^r(l-r)^n
&=sum_{r=0}^n(-1)^{n-r}binom{n}{r}(r-l)^n\
&=n!
end{align}
$$
The given identity is this identity using $l=0$.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Apr 13 '17 at 12:21









Community

1




1










answered May 22 '16 at 13:40









robjohn

264k27302623




264k27302623












  • Thanks for referencing the question, where many nice answers are!
    – awllower
    May 22 '16 at 14:06


















  • Thanks for referencing the question, where many nice answers are!
    – awllower
    May 22 '16 at 14:06
















Thanks for referencing the question, where many nice answers are!
– awllower
May 22 '16 at 14:06




Thanks for referencing the question, where many nice answers are!
– awllower
May 22 '16 at 14:06











2














Here is a variant based upon the coefficient of operator $[z^k]$ used to denote the coefficient of $z^k$ in a series. This way we can write e.g.
begin{align*}
[z^j](1+z)^k=binom{k}{j}qquadqquadtext{or}qquadqquad k![z^k]e^{jz}=j^k
end{align*}




We obtain
begin{align*}
sum_{j=1}^k(-1)^{k-j}j^kbinom{k}{j}
&=sum_{j=0}^infty(-1)^{k-j}k![z^k]e^{jz}[u^k](1+u)^ktag{1}\
&=(-1)^kk![z^k]sum_{j=0}^{infty}left(-e^{z}right)^j[u^k](1+u)^ktag{2}\
&=(-1)^kk![z^k](1-e^z)^ktag{3}\
&=k![z^k]left(z+frac{z^2}{2!}+frac{z^3}{3!}+cdotsright)^ktag{4}\
&=k!
end{align*}
and the claim follows.




Comment:




  • In (1) we apply the coefficient of operator twice and extend the lower and upper limit of the series without changing anything, since we add only zeros.


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


  • In (3) we use the substitution rule with $u=-e^z$:



begin{align*}
A(z)=sum_{j=0}^infty a_jz^j=sum_{j=0}^infty z^j [u^k]A(u)
end{align*}




  • In (4) we see that in each of the $k$ factors $(e^z-1)$ only $z^1$ provide a contribution to $z^k$.






share|cite|improve this answer























  • Thanks for this interesting use of the coefficient operator which makes the approach through exponential functions more natural. :)
    – awllower
    May 23 '16 at 8:16










  • @awllower: You're welcome! :-)
    – Markus Scheuer
    May 23 '16 at 8:28
















2














Here is a variant based upon the coefficient of operator $[z^k]$ used to denote the coefficient of $z^k$ in a series. This way we can write e.g.
begin{align*}
[z^j](1+z)^k=binom{k}{j}qquadqquadtext{or}qquadqquad k![z^k]e^{jz}=j^k
end{align*}




We obtain
begin{align*}
sum_{j=1}^k(-1)^{k-j}j^kbinom{k}{j}
&=sum_{j=0}^infty(-1)^{k-j}k![z^k]e^{jz}[u^k](1+u)^ktag{1}\
&=(-1)^kk![z^k]sum_{j=0}^{infty}left(-e^{z}right)^j[u^k](1+u)^ktag{2}\
&=(-1)^kk![z^k](1-e^z)^ktag{3}\
&=k![z^k]left(z+frac{z^2}{2!}+frac{z^3}{3!}+cdotsright)^ktag{4}\
&=k!
end{align*}
and the claim follows.




Comment:




  • In (1) we apply the coefficient of operator twice and extend the lower and upper limit of the series without changing anything, since we add only zeros.


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


  • In (3) we use the substitution rule with $u=-e^z$:



begin{align*}
A(z)=sum_{j=0}^infty a_jz^j=sum_{j=0}^infty z^j [u^k]A(u)
end{align*}




  • In (4) we see that in each of the $k$ factors $(e^z-1)$ only $z^1$ provide a contribution to $z^k$.






share|cite|improve this answer























  • Thanks for this interesting use of the coefficient operator which makes the approach through exponential functions more natural. :)
    – awllower
    May 23 '16 at 8:16










  • @awllower: You're welcome! :-)
    – Markus Scheuer
    May 23 '16 at 8:28














2












2








2






Here is a variant based upon the coefficient of operator $[z^k]$ used to denote the coefficient of $z^k$ in a series. This way we can write e.g.
begin{align*}
[z^j](1+z)^k=binom{k}{j}qquadqquadtext{or}qquadqquad k![z^k]e^{jz}=j^k
end{align*}




We obtain
begin{align*}
sum_{j=1}^k(-1)^{k-j}j^kbinom{k}{j}
&=sum_{j=0}^infty(-1)^{k-j}k![z^k]e^{jz}[u^k](1+u)^ktag{1}\
&=(-1)^kk![z^k]sum_{j=0}^{infty}left(-e^{z}right)^j[u^k](1+u)^ktag{2}\
&=(-1)^kk![z^k](1-e^z)^ktag{3}\
&=k![z^k]left(z+frac{z^2}{2!}+frac{z^3}{3!}+cdotsright)^ktag{4}\
&=k!
end{align*}
and the claim follows.




Comment:




  • In (1) we apply the coefficient of operator twice and extend the lower and upper limit of the series without changing anything, since we add only zeros.


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


  • In (3) we use the substitution rule with $u=-e^z$:



begin{align*}
A(z)=sum_{j=0}^infty a_jz^j=sum_{j=0}^infty z^j [u^k]A(u)
end{align*}




  • In (4) we see that in each of the $k$ factors $(e^z-1)$ only $z^1$ provide a contribution to $z^k$.






share|cite|improve this answer














Here is a variant based upon the coefficient of operator $[z^k]$ used to denote the coefficient of $z^k$ in a series. This way we can write e.g.
begin{align*}
[z^j](1+z)^k=binom{k}{j}qquadqquadtext{or}qquadqquad k![z^k]e^{jz}=j^k
end{align*}




We obtain
begin{align*}
sum_{j=1}^k(-1)^{k-j}j^kbinom{k}{j}
&=sum_{j=0}^infty(-1)^{k-j}k![z^k]e^{jz}[u^k](1+u)^ktag{1}\
&=(-1)^kk![z^k]sum_{j=0}^{infty}left(-e^{z}right)^j[u^k](1+u)^ktag{2}\
&=(-1)^kk![z^k](1-e^z)^ktag{3}\
&=k![z^k]left(z+frac{z^2}{2!}+frac{z^3}{3!}+cdotsright)^ktag{4}\
&=k!
end{align*}
and the claim follows.




Comment:




  • In (1) we apply the coefficient of operator twice and extend the lower and upper limit of the series without changing anything, since we add only zeros.


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


  • In (3) we use the substitution rule with $u=-e^z$:



begin{align*}
A(z)=sum_{j=0}^infty a_jz^j=sum_{j=0}^infty z^j [u^k]A(u)
end{align*}




  • In (4) we see that in each of the $k$ factors $(e^z-1)$ only $z^1$ provide a contribution to $z^k$.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Feb 4 at 23:00

























answered May 23 '16 at 8:07









Markus Scheuer

59.9k455143




59.9k455143












  • Thanks for this interesting use of the coefficient operator which makes the approach through exponential functions more natural. :)
    – awllower
    May 23 '16 at 8:16










  • @awllower: You're welcome! :-)
    – Markus Scheuer
    May 23 '16 at 8:28


















  • Thanks for this interesting use of the coefficient operator which makes the approach through exponential functions more natural. :)
    – awllower
    May 23 '16 at 8:16










  • @awllower: You're welcome! :-)
    – Markus Scheuer
    May 23 '16 at 8:28
















Thanks for this interesting use of the coefficient operator which makes the approach through exponential functions more natural. :)
– awllower
May 23 '16 at 8:16




Thanks for this interesting use of the coefficient operator which makes the approach through exponential functions more natural. :)
– awllower
May 23 '16 at 8:16












@awllower: You're welcome! :-)
– Markus Scheuer
May 23 '16 at 8:28




@awllower: You're welcome! :-)
– Markus Scheuer
May 23 '16 at 8:28



Popular posts from this blog

Berounka

Sphinx de Gizeh

Different font size/position of beamer's navigation symbols template's content depending on regular/plain...