自然数幂和

S_m(n)=\sum_{i=0}^{n-1}i^m

伯努利数

伯努利数常用于计算自然数幂和。

伯努利数第

i

项记作

B_i

，满足：

\sum_{i=0}^n\binom{n+1}iB_i=[n=0]

两边加上

B_{i+1}

，即

\sum_{i=0}^{n+1}\binom{n+1}iB_i=[n=0]+B_{n+1}\\ \sum_{i=0}^n\binom niB_i=[n=1]+B_n\\ \sum_{i=0}^n\frac{B_i}{i!}\cdot\frac1{(n-i)!}=[n=1]+\frac{B_n}{n!}

记

B

的 EGF 为

B(x)

，有：

B(x)e^x=x+B(x)\\ B(x)=\frac x{e^x-1}

可以

O(n\log n)

求出伯努利数。

关于其与自然数幂和的关系，有

S_m(n)=\frac1{m+1}\sum_{i=0}^m\binom{m+1}iB_in^{m+1-i}

证明：

设

F_n(x)=\sum_{m\ge0}\frac{S_m(n)}{m!}x^m

。

F_n(x)=\sum_{m\ge0}\sum_{i=0}^{n-1}\frac{i^mx^m}{m!}\\ F_n(x)=\sum_{i=0}^{n-1}e^{ix}\\ F_n(x)=\frac{e^{nx}-1}{e^x-1}\\ F_n(x)=\frac x{e^x-1}\cdot\frac{e^{nx}-1}x\\ F_n(x)=B(x)\sum_{i\ge1}\frac{n^ix^{i-1}}{i!}\\ F_n(x)=(\sum_{i\ge0}\frac{B_ix^i}{i!})(\sum_{i\ge0}\frac{n^{i+1}x^i}{(i+1)!})\\ S_m(n)=m![x^m]F_n(x)\\ S_m(n)=m!\sum_{i=0}^m\frac{B_i}{i!}\cdot\frac{n^{m-i+1}}{(m-i+1)!}\\ S_m(n)=\frac1{m+1}\sum_{i=0}^m\binom{m+1}iB_in^{m-i+1}