This article is translated from a Chinese article on my Zhihu account. The original article was posted at 2019-07-13 20:36 +0800.


Definition 1. Let fn ⁣(z)(1z)n+1k=1knzk,f_n\!\left(z\right)\coloneqq\left(1-z\right)^{n+1}\sum_{k=1}^\infty k^nz^k, where nn is a positive integer.

Our goal is to prove that fn ⁣(z)f_n\!\left(z\right) is a polynomial of degree nn w.r.t. zz, and the sum of its coefficients is n!n!.

Lemma 1. fn+1 ⁣(z)=z(1z)n+2ddz(fn ⁣(z)(1z)n+1).f_{n+1}\!\left(z\right)=z\,\left(1-z\right)^{n+2}\frac{\mathrm d}{\mathrm dz}\left(\frac{f_n\!\left(z\right)}{\left(1-z\right)^{n+1}}\right).

Proof. ddz(fn ⁣(z)(1z)n+1)=ddzk=1knzk=k=1kn+1zk1=fn+1 ⁣(z)z(1z)n+2.\begin{align*} \frac{\mathrm d}{\mathrm dz}\left(\frac{f_n\!\left(z\right)}{\left(1-z\right)^{n+1}}\right) &=\frac{\mathrm d}{\mathrm dz}\sum_{k=1}^\infty k^nz^k\\ &=\sum_{k=1}^\infty k^{n+1}z^{k-1}\\ &=\frac{f_{n+1}\!\left(z\right)}{z\,\left(1-z\right)^{n+2}}. \end{align*} \square

Definition 2 (Eulerian numbers). <nk>j=0k+1(1)j(n+1j)(kj+1)n.\left<\begin{matrix}n\\k\end{matrix}\right>\coloneqq\sum_{j=0}^{k+1}\left(-1\right)^j\binom{n+1}j\left(k-j+1\right)^n.

Lemma 2. <n+1k+1>=(nk)<nk>+(k+2)<nk+1>.\left<\begin{matrix}n+1\\k+1\end{matrix}\right>=\left(n-k\right)\left<\begin{matrix}n\\k\end{matrix}\right>+\left(k+2\right)\left<\begin{matrix}n\\k+1\end{matrix}\right>.

Proof. = (nk)<nk>+(k+2)<nk+1>=(nk)j=0k+1(1)j(n+1j)(kj+1)n+(k+2)j=0k+2(1)j(n+1j)(kj+2)n=(nk)j=0k+2(1)j1(n+1j1)(kj+2)n+(k+2)j=0k+2(1)j(n+1j)(kj+2)n=j=0k+2(1)j(kj+2)n((kn)(n+1j1)+(k+2)(n+1j))=j=0k+2(1)j(kj+2)n((kn)(n+1)!(j1)!(nj+2)!+(k+2)(n+1)!j!(nj+1)!)=j=0k+2(1)j(kj+2)n(n+1)!j!(nj+2)((kn)j+(k+2)(nj+2))=j=0k+2(1)j(kj+2)n(n+1)!j!(nj+2)(n+2)(kj+2)=j=0k+2(1)j(kj+2)n+1(n+2)!j!(nj+2)=j=0k+2(1)j(n+2j)(kj+2)n+1=<n+1k+1>.\begin{align*} &\phantom{=}~\,\left(n-k\right)\left<\begin{matrix}n\\k\end{matrix}\right>+\left(k+2\right)\left<\begin{matrix}n\\k+1\end{matrix}\right>\\ &=\left(n-k\right)\sum_{j=0}^{k+1}\left(-1\right)^j\binom{n+1}j\left(k-j+1\right)^n+\left(k+2\right)\sum_{j=0}^{k+2}\left(-1\right)^j\binom{n+1}j\left(k-j+2\right)^n\\ &=\left(n-k\right)\sum_{j=0}^{k+2}\left(-1\right)^{j-1}\binom{n+1}{j-1}\left(k-j+2\right)^n+\left(k+2\right)\sum_{j=0}^{k+2}\left(-1\right)^j\binom{n+1}j\left(k-j+2\right)^n\\ &=\sum_{j=0}^{k+2}\left(-1\right)^j\left(k-j+2\right)^n\left(\left(k-n\right)\binom{n+1}{j-1}+\left(k+2\right)\binom{n+1}j\right)\\ &=\sum_{j=0}^{k+2}\left(-1\right)^j\left(k-j+2\right)^n\left(\left(k-n\right)\frac{\left(n+1\right)!}{\left(j-1\right)!\left(n-j+2\right)!}+\left(k+2\right)\frac{\left(n+1\right)!}{j!\left(n-j+1\right)!}\right)\\ &=\sum_{j=0}^{k+2}\left(-1\right)^j\left(k-j+2\right)^n\frac{\left(n+1\right)!}{j!\left(n-j+2\right)}\left(\left(k-n\right)j+\left(k+2\right)\left(n-j+2\right)\right)\\ &=\sum_{j=0}^{k+2}\left(-1\right)^j\left(k-j+2\right)^n\frac{\left(n+1\right)!}{j!\left(n-j+2\right)}\left(n+2\right)\left(k-j+2\right)\\ &=\sum_{j=0}^{k+2}\left(-1\right)^j\left(k-j+2\right)^{n+1}\frac{\left(n+2\right)!}{j!\left(n-j+2\right)}\\ &=\sum_{j=0}^{k+2}\left(-1\right)^j\binom{n+2}j\left(k-j+2\right)^{n+1}\\ &=\left<\begin{matrix}n+1\\k+1\end{matrix}\right>. \end{align*} \square

Lemma 3. <n0>=1,<nn>=0.\left<\begin{matrix}n\\0\end{matrix}\right>=1,\quad\left<\begin{matrix}n\\n\end{matrix}\right>=0.

Brief proof. Easily proved by Definition 2. \square

Lemma 4. fn ⁣(z)=k=1n<nnk>zk.f_n\!\left(z\right)=\sum_{k=1}^n\left<\begin{matrix}n\\n-k\end{matrix}\right>z^k.

Proof. By mathematical induction. When n=1n=1, fn(z)=z=k=1n<nnk>zk,f_n\left(z\right)=z=\sum_{k=1}^n\left<\begin{matrix}n\\n-k\end{matrix}\right>z^k, the result holds.

Suppose the result holds when n=n0n=n_0, and then when n=n0+1n=n_0+1, = fn ⁣(z)=z(1z)n0+2ddz(fn0(z)(1z)n0+1)(Lemma 1)=z(1z)n0+2dfn0(z)dz(1z)n0+1fn0 ⁣(z)d((1z)n0+1)dz(1z)2n0+2=z(1z)n0+2dfn0(z)dz(1z)n0+1+(n0+1)fn0 ⁣(z)(1z)n0(1z)2n0+2=z(dfn0 ⁣(z)dz(1z)+(n0+1)fn0(z))=z((1z)ddzk=1n0<n0n0k>zk+(n0+1)k=1n0<n0n0k>zk)(supposed)=z((1z)k=1n0<n0n0k>kzk1+(n0+1)k=1n0<n0n0k>zk)=z(k=1n0<n0n0k>kzk1k=1n0<n0n0k>kzk+(n0+1)k=1n0<n0n0k>zk)=z(k=0n0<n0n0k1>(k+1)zkk=0n0<n0n0k>kzk+(n0+1)k=0n0<n0n0k>zk)(Lemma 3)=zk=0n0(<n0n0k1>(k+1)zk<n0n0k>kzk+(n0+1)<n0n0k>zk)=k=0n0(<n0n0k1>(k+1)<n0n0k>k+(n0+1)<n0n0k>)zk+1=k=1n0+1(k<n0n0k>+(n0k+2)<n0n0k+1>)zk=k=1n0+1<n0+1n0k+1>zk(Lemma 2)=k=1n<nnk>zk.\begin{align*} &\phantom{=}~\,f_n\!\left(z\right)\\ &=z\,\left(1-z\right)^{n_0+2}\frac{\mathrm d}{\mathrm dz}\left(\frac{f_{n_0}\left(z\right)}{\left(1-z\right)^{n_0+1}}\right) &\text{(Lemma 1)}\\ &=z\,\left(1-z\right)^{n_0+2}\frac{\frac{\mathrm df_{n_0}\left(z\right)}{\mathrm dz}\left(1-z\right)^{n_0+1}-f_{n_0}\!\left(z\right)\frac{\mathrm d\left(\left(1-z\right)^{n_0+1}\right)}{\mathrm dz}}{\left(1-z\right)^{2n_0+2}}\\ &=z\,\left(1-z\right)^{n_0+2}\frac{\frac{\mathrm df_{n_0}\left(z\right)}{\mathrm dz}\left(1-z\right)^{n_0+1}+\left(n_0+1\right)f_{n_0}\!\left(z\right)\left(1-z\right)^{n_0}}{\left(1-z\right)^{2n_0+2}}\\ &=z\left(\frac{\mathrm df_{n_0}\!\left(z\right)}{\mathrm dz}\left(1-z\right)+\left(n_0+1\right)f_{n_0}\left(z\right)\right)\\ &=z\left(\left(1-z\right)\frac{\mathrm d}{\mathrm dz}\sum_{k=1}^{n_0}\left<\begin{matrix}n_0\\n_0-k\end{matrix}\right>z^k+\left(n_0+1\right)\sum_{k=1}^{n_0}\left<\begin{matrix}n_0\\n_0-k\end{matrix}\right>z^k\right) &\text{(supposed)}\\ &=z\left(\left(1-z\right)\sum_{k=1}^{n_0}\left<\begin{matrix}n_0\\n_0-k\end{matrix}\right>kz^{k-1}+\left(n_0+1\right)\sum_{k=1}^{n_0}\left<\begin{matrix}n_0\\n_0-k\end{matrix}\right>z^k\right)\\ &=z\left(\sum_{k=1}^{n_0}\left<\begin{matrix}n_0\\n_0-k\end{matrix}\right>kz^{k-1}-\sum_{k=1}^{n_0}\left<\begin{matrix}n_0\\n_0-k\end{matrix}\right>kz^k+\left(n_0+1\right)\sum_{k=1}^{n_0}\left<\begin{matrix}n_0\\n_0-k\end{matrix}\right>z^k\right)\\ &=z\left(\sum_{k=0}^{n_0}\left<\begin{matrix}n_0\\n_0-k-1\end{matrix}\right>\left(k+1\right)z^k-\sum_{k=0}^{n_0}\left<\begin{matrix}n_0\\n_0-k\end{matrix}\right>kz^k+\left(n_0+1\right)\sum_{k=0}^{n_0}\left<\begin{matrix}n_0\\n_0-k\end{matrix}\right>z^k\right) &\text{(Lemma 3)}\\ &=z\sum_{k=0}^{n_0}\left(\left<\begin{matrix}n_0\\n_0-k-1\end{matrix}\right>\left(k+1\right)z^k-\left<\begin{matrix}n_0\\n_0-k\end{matrix}\right>kz^k+\left(n_0+1\right)\left<\begin{matrix}n_0\\n_0-k\end{matrix}\right>z^k\right)\\ &=\sum_{k=0}^{n_0}\left(\left<\begin{matrix}n_0\\n_0-k-1\end{matrix}\right>\left(k+1\right)-\left<\begin{matrix}n_0\\n_0-k\end{matrix}\right>k+\left(n_0+1\right)\left<\begin{matrix}n_0\\n_0-k\end{matrix}\right>\right)z^{k+1}\\ &=\sum_{k=1}^{n_0+1}\left(k\left<\begin{matrix}n_0\\n_0-k\end{matrix}\right>+\left(n_0-k+2\right)\left<\begin{matrix}n_0\\n_0-k+1\end{matrix}\right>\right)z^k\\ &=\sum_{k=1}^{n_0+1}\left<\begin{matrix}n_0+1\\n_0-k+1\end{matrix}\right>z^k &\text{(Lemma 2)}\\ &=\sum_{k=1}^n\left<\begin{matrix}n\\n-k\end{matrix}\right>z^k. \end{align*} Then we can derive that the result is true by mathematical induction. \square

Lemma 5. j=0n(1)nj(nj)jn=n!.\sum_{j=0}^n\left(-1\right)^{n-j}\binom njj^n=n!.

Proof. Because ex1x\mathrm e^x-1\sim x (in terms of infinitesimal quantity), (ex1)nxn\left(\mathrm e^x-1\right)^n\sim x^n, i.e. (ex1)n=xn+o ⁣(xn)\left(\mathrm e^x-1\right)^n=x^n+o\!\left(x^n\right) (where oo denotes higher order of infinitesimal quantity).

Apply Newton’s binomial theorem to the left-hand side, and we have j=0n(1)nj(nj)ejx=xn+o ⁣(xn).\sum_{j=0}^n\left(-1\right)^{n-j}\binom nj\mathrm e^{jx}=x^n+o\!\left(x^n\right). Take nnth derivative of the equation, and we have j=0n(1)nj(nj)jnejx=n!+o ⁣(1).\sum_{j=0}^n\left(-1\right)^{n-j}\binom njj^n\mathrm e^{jx}=n!+o\!\left(1\right). Take x=0x=0, and we have j=0n(1)nj(nj)jn=n!.\sum_{j=0}^n\left(-1\right)^{n-j}\binom njj^n=n!. \square

Lemma 6. j=0n(1)nj(nj)(j+1)n=n!.\sum_{j=0}^n\left(-1\right)^{n-j}\binom nj\left(j+1\right)^n=n!.

Proof. (n+1)!=j=0n(1)nj+1(n+1j)jn+1(Lemma 5)=j=1n(1)nj+1(n+1j)jn+1=j=1n(1)nj+1(n+1)!j!(nj+1)!jn+1=j=1n(1)nj+1(n+1)n!(j1)!(nj+1)!jn=j=0n(1)nj(n+1)n!j!(nj)!(j+1)n=(n+1)j=0n(1)nj(nj)(j+1)n.\begin{align*} \left(n+1\right)!&=\sum_{j=0}^n\left(-1\right)^{n-j+1}\binom{n+1}jj^{n+1}& \text{(Lemma 5)}\\ &=\sum_{j=1}^n\left(-1\right)^{n-j+1}\binom{n+1}jj^{n+1}\\ &=\sum_{j=1}^n\left(-1\right)^{n-j+1}\frac{\left(n+1\right)!}{j!\left(n-j+1\right)!}j^{n+1} \\ &=\sum_{j=1}^n\left(-1\right)^{n-j+1}\frac{\left(n+1\right)n!}{\left(j-1\right)!\left(n-j+1\right)!}j^n\\ &=\sum_{j=0}^n\left(-1\right)^{n-j}\frac{\left(n+1\right)n!}{j!\left(n-j\right)!}\left(j+1\right)^n\\ &=\left(n+1\right)\sum_{j=0}^n\left(-1\right)^{n-j}\binom nj\left(j+1\right)^n. \end{align*} \square

Lemma 7. k=0n<nk>=n!.\sum_{k=0}^n\left<\begin{matrix}n\\k\end{matrix}\right>=n!.

Proof. = k=0n<nk>=k=0nj=0k+1(1)j(n+1j)(kj+1)n=k=0nj=0k(1)j(n+1j)(kj+1)n=j=0nk=jn(1)j(n+1j)(kj+1)n=j=0n(1)j(n+1j)k=jn(kj+1)n=j=0n(1)j(n+1j)k=1nj+1kn=j=0n(1)nj(n+1nj)k=1j+1kn=j=0n(1)nj(n+1j+1)k=1j+1kn=j=0n(1)nj((nj)+(nj+1))k=1j+1kn=j=0n(1)nj(nj)k=1j+1kn+j=0n(1)nj(nj+1)k=1j+1kn=j=0n(1)nj(nj)(j+1)n+j=0n(1)nj(nj)k=1jkn+j=1n(1)nj+1(nj)k=1jkn=n!+j=1n(1)nj(nj)k=1jknj=1n(1)nj(nj)k=1jkn(Lemma 6)=n!.\begin{align*} &\phantom{=}~\,\sum_{k=0}^n\left<\begin{matrix}n\\k\end{matrix}\right>\\ &=\sum_{k=0}^n\sum_{j=0}^{k+1}\left(-1\right)^j\binom{n+1}j\left(k-j+1\right)^n\\ &=\sum_{k=0}^n\sum_{j=0}^k\left(-1\right)^j\binom{n+1}j\left(k-j+1\right)^n\\ &=\sum_{j=0}^n\sum_{k=j}^n\left(-1\right)^j\binom{n+1}j\left(k-j+1\right)^n\\ &=\sum_{j=0}^n\left(-1\right)^j\binom{n+1}j\sum_{k=j}^n\left(k-j+1\right)^n\\ &=\sum_{j=0}^n\left(-1\right)^j\binom{n+1}j\sum_{k=1}^{n-j+1}k^n\\ &=\sum_{j=0}^n\left(-1\right)^{n-j}\binom{n+1}{n-j}\sum_{k=1}^{j+1}k^n\\ &=\sum_{j=0}^n\left(-1\right)^{n-j}\binom{n+1}{j+1}\sum_{k=1}^{j+1}k^n\\ &=\sum_{j=0}^n\left(-1\right)^{n-j}\left(\binom nj+\binom n{j+1}\right)\sum_{k=1}^{j+1}k^n\\ &=\sum_{j=0}^n\left(-1\right)^{n-j}\binom nj\sum_{k=1}^{j+1}k^n+\sum_{j=0}^n\left(-1\right)^{n-j}\binom n{j+1}\sum_{k=1}^{j+1}k^n\\ &=\sum_{j=0}^n\left(-1\right)^{n-j}\binom nj\left(j+1\right)^n+\sum_{j=0}^n\left(-1\right)^{n-j}\binom nj\sum_{k=1}^jk^n+\sum_{j=1}^n\left(-1\right)^{n-j+1}\binom nj\sum_{k=1}^jk^n\\ &=n!+\sum_{j=1}^n\left(-1\right)^{n-j}\binom nj\sum_{k=1}^jk^n-\sum_{j=1}^n\left(-1\right)^{n-j}\binom nj\sum_{k=1}^jk^n &\text{(Lemma 6)}\\ &=n!. \end{align*} \square

Proof of the original proposition. By Lemma 4, fn ⁣(z)f_n\!\left(z\right) is a polynomial of degree nn in zz (Lemma 3 guarantees that the coefficient of the nnth degree term is not 00).

The sum of coefficients k=1n<nnk>=k=0n1<nk>=k=0n<nk>(Lemma 3)=n!.(Lemma 7)\begin{align*} \sum_{k=1}^n\left<\begin{matrix}n\\n-k\end{matrix}\right> &=\sum_{k=0}^{n-1}\left<\begin{matrix}n\\k\end{matrix}\right>\\ &=\sum_{k=0}^n\left<\begin{matrix}n\\k\end{matrix}\right> &\text{(Lemma 3)}\\ &=n!. &\text{(Lemma 7)} \end{align*} \square