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)≔(1−z)n+1∑k=1∞knzk,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 (1−z)n+2ddz(fn ⁣(z)(1−z)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)(1−z)n+1)=ddz∑k=1∞knzk=∑k=1∞kn+1zk−1=fn+1 ⁣(z)z (1−z)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)(k−j+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>=(n−k)<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.

=  (n−k)<nk>+(k+2)<nk+1>=(n−k)∑j=0k+1(−1)j(n+1j)(k−j+1)n+(k+2)∑j=0k+2(−1)j(n+1j)(k−j+2)n=(n−k)∑j=0k+2(−1)j−1(n+1j−1)(k−j+2)n+(k+2)∑j=0k+2(−1)j(n+1j)(k−j+2)n=∑j=0k+2(−1)j(k−j+2)n((k−n)(n+1j−1)+(k+2)(n+1j))=∑j=0k+2(−1)j(k−j+2)n((k−n)(n+1)!(j−1)!(n−j+2)!+(k+2)(n+1)!j!(n−j+1)!)=∑j=0k+2(−1)j(k−j+2)n(n+1)!j!(n−j+2)((k−n)j+(k+2)(n−j+2))=∑j=0k+2(−1)j(k−j+2)n(n+1)!j!(n−j+2)(n+2)(k−j+2)=∑j=0k+2(−1)j(k−j+2)n+1(n+2)!j!(n−j+2)=∑j=0k+2(−1)j(n+2j)(k−j+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<nn−k>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<nn−k>zk,f_n\left(z\right)=z=\sum_{k=1}^n\left<\begin{matrix}n\\n-k\end{matrix}\right>z^k,

the result stands.

Suppose the result stands when n=n0n=n_0, and then when n=n0+1n=n_0+1,

=  fn ⁣(z)=z (1−z)n0+2ddz(fn0(z)(1−z)n0+1)(Lemma 1)=z (1−z)n0+2dfn0(z)dz(1−z)n0+1−fn0 ⁣(z)d((1−z)n0+1)dz(1−z)2n0+2=z (1−z)n0+2dfn0(z)dz(1−z)n0+1+(n0+1)fn0 ⁣(z)(1−z)n0(1−z)2n0+2=z(dfn0 ⁣(z)dz(1−z)+(n0+1)fn0(z))=z((1−z)ddz∑k=1n0<n0n0−k>zk+(n0+1)∑k=1n0<n0n0−k>zk)(supposed)=z((1−z)∑k=1n0<n0n0−k>kzk−1+(n0+1)∑k=1n0<n0n0−k>zk)=z(∑k=1n0<n0n0−k>kzk−1−∑k=1n0<n0n0−k>kzk+(n0+1)∑k=1n0<n0n0−k>zk)=z(∑k=0n0<n0n0−k−1>(k+1)zk−∑k=0n0<n0n0−k>kzk+(n0+1)∑k=0n0<n0n0−k>zk)(Lemma 3)=z∑k=0n0(<n0n0−k−1>(k+1)zk−<n0n0−k>kzk+(n0+1)<n0n0−k>zk)=∑k=0n0(<n0n0−k−1>(k+1)−<n0n0−k>k+(n0+1)<n0n0−k>)zk+1=∑k=1n0+1(k<n0n0−k>+(n0−k+2)<n0n0−k+1>)zk=∑k=1n0+1<n0+1n0−k+1>zk(Lemma 2)=∑k=1n<nn−k>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)n−j(nj)jn=n!.\sum_{j=0}^n\left(-1\right)^{n-j}\binom njj^n=n!.

Proof. Because ex−1∼x\mathrm e^x-1\sim x (in terms of infinitesimal quantity), (ex−1)n∼xn\left(\mathrm e^x-1\right)^n\sim x^n, i.e.

(ex−1)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)n−j(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)n−j(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)n−j(nj)jn=n!.\sum_{j=0}^n\left(-1\right)^{n-j}\binom njj^n=n!. □\square

Lemma 6.

∑j=0n(−1)n−j(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)n−j+1(n+1j)jn+1(Lemma 5)=∑j=1n(−1)n−j+1(n+1j)jn+1=∑j=1n(−1)n−j+1(n+1)!j!(n−j+1)!jn+1=∑j=1n(−1)n−j+1(n+1)n!(j−1)!(n−j+1)!jn=∑j=0n(−1)n−j(n+1)n!j!(n−j)!(j+1)n=(n+1)∑j=0n(−1)n−j(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=0n∑j=0k+1(−1)j(n+1j)(k−j+1)n=∑k=0n∑j=0k(−1)j(n+1j)(k−j+1)n=∑j=0n∑k=jn(−1)j(n+1j)(k−j+1)n=∑j=0n(−1)j(n+1j)∑k=jn(k−j+1)n=∑j=0n(−1)j(n+1j)∑k=1n−j+1kn=∑j=0n(−1)n−j(n+1n−j)∑k=1j+1kn=∑j=0n(−1)n−j(n+1j+1)∑k=1j+1kn=∑j=0n(−1)n−j((nj)+(nj+1))∑k=1j+1kn=∑j=0n(−1)n−j(nj)∑k=1j+1kn+∑j=0n(−1)n−j(nj+1)∑k=1j+1kn=∑j=0n(−1)n−j(nj)(j+1)n+∑j=0n(−1)n−j(nj)∑k=1jkn+∑j=1n(−1)n−j+1(nj)∑k=1jkn=n!+∑j=1n(−1)n−j(nj)∑k=1jkn−∑j=1n(−1)n−j(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<nn−k>=∑k=0n−1<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