「Learning Notes」Power Sum of Natural Numbers

Notations

S_{k}(n) 表示前 n 个自然数的 k 次幂和:

S_{k}(n)=\sum_{i=1}^{n}i^{k}

\hat{A}(z) 表示数列 \left\{A_{n}\right\} \text{EGF}

\hat{A}(z)=\sum_{k=0}^{+\infty}\frac{A_{i}}{k!}z^{k}

Methods

Method 1:Bernoulli Number

伯努利数(Bernoulli Number)的 EGF 定义为:

\begin{aligned} \hat{B}(z)&=\frac{z}{e^{z}-1}\\ &=\frac{z}{\sum_{i=1}^{+\infty}\frac{z^{i}}{i!}}\\ &=\frac{1}{\sum_{i=0}^{+\infty}\frac{z^{i}}{\left(i+1\right)!}} \end{aligned}

则可通过多项式求逆 O(n \log{n}) 时间内求得伯努利数的前 n 项.

S_{k}(n) 的 EGF 为:

G\left(z,n\right)=\sum_{k=0}^{+\infty}\frac{S_{k}(n)}{k!}z^{k}

则有:

\begin{aligned} G\left(z,n\right) =&\sum_{k=0}^{+\infty}\frac{S_{k}(n)}{k!}z^{k}\\ =&\sum_{k=0}^{+\infty}\sum_{i=1}^{n}\frac{1}{k!}\left(iz\right)^{k}\\ =&\sum_{i=1}^{n}e^{iz}\\ =&\frac{1-e^{zn}}{e^{-z}-1}\\ =&\left(1-e^{zn}\right)\frac{\hat{B}\left(-z\right)}{-z}\\ =&-\sum_{i=1}^{+\infty}\frac{1}{i!}\left(zn\right)^{i}\sum_{j=0}^{+\infty}\frac{B_{j}}{j!}\left(-z\right)^{j-1}\\ =&\sum_{i=1}^{+\infty}\sum_{j=0}^{+\infty}\frac{(-1)^{j}B_{j}n^{i}}{i!j!}z^{i+j-1}\\ =&\sum_{k=0}^{+\infty}\sum_{j=0}^{k}\frac{(-1)^{j}B_{j}n^{k+1-j}}{\left(k+1-j\right)!j!}z^{k}\\ =&\sum_{k=0}^{+\infty}\sum_{j=0}^{k}\frac{(-1)^{j}B_{j}n^{k+1-j}}{\left(k+1\right)!}\binom{k+1}{j}z^{k}\\ =&\sum_{k=0}^{+\infty}\left(\frac{1}{k+1}\sum_{j=0}^{k}(-1)^{j}\binom{k+1}{j}B_{j}n^{k+1-j}\right)\frac{1}{k!}z^{k} \end{aligned}

即:

S_{k}(n)=\frac{1}{k+1}\sum_{i=0}^{k}(-1)^{i}\binom{k+1}{i}B_{i}n^{k+1-i}

B_{i} 复杂度 O\left(k\log{k}\right) ,求 S_{k}(n) 复杂度 O(k) ,总复杂度 O\left(k\log{k}\right)

References

Bernoulli Number