随笔:由自然数幂和推导出伯努利数

所谓自然数幂次和就是这样的一个问题:给定$n, m$,求:

$$ \sum_{i=1}^n i^m $$

一般来说$n$都很大,而$m$比较小,所以我们可以考虑固定$n$,写出答案关于$m$的指数生成函数:

$$
\begin{aligned}
F(x)=&\sum_{k=0}^\infty \frac{\sum_{i=0}^n i^k}{k!}x^k\\
=&\sum_{i=0}^n e^{ix}\\
=&\frac{e^{(n+1)x-1}}{e^x-1}
\end{aligned}
$$

直接按照这个式子跑一次求逆就可以在$O(m\log m)$时间内求出$1$~$m$次幂的和了。

实际上如果把分母提出来,定义$B(x)=\frac x {e^x – 1}$,那么就有

$$
\begin{aligned}
&\sum_{i=0}^n i^m \\
=&m![x^m]F(x) \\
=&\frac 1{m+1}\sum_{i=0}^m {m+1\choose i}B_i(n+1)^{m+1-i}
\end{aligned}
$$

$\{B_i\}$就是伯努利数,而这个等式也就是众所周知的伯努利等式。

也就是说,通过指数生成函数,我们可以很快地由自然数幂次和问题推导出伯努利数的解法。(但通过普通生成函数就不是这么容易了。)

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注