伯努利数

本文最后更新于:2022年1月19日 晚上

伯努利数

今天看吉米多维奇的时候偶然看到伯努利数,一查oi-wiki上也有,就学了一下,就当第一篇博客了。(之后会写FFT和NTT,多项式求逆和多项式除法的)

背景:等幂求和

$$
\begin{aligned}\sum_{k=0}^{n-1}k^m=\frac{1}{m+1}\sum_{k=0}^mC_{m+1}^kB_kn^{m+1-k}\end{aligned}
$$

利用$(k+1)^2-k^2=2k+1$可得
$$
\begin{aligned}\sum_{k=1}^n[(k+1)^2-k^2]=\sum_{k=1}^n(2k+1)\end{aligned}
$$
整理后即为
$$
\begin{aligned}\sum_{k=1}^nk=\frac{n(n+1)}{2}\end{aligned}
$$
类似的,利用$(k+1)^3-k^3=3k^2+3k+1$可得
$$
\begin{aligned}\sum_{k=1}^n[(k+1)^3-k^3]=\sum_{k=1}^n(3k^2+3k+1)=3\sum_{k=1}^nk^2+3\sum_{k=1}^nk+n\end{aligned}
$$

$$
\begin{aligned}=3\sum_{k=1}^nk^2+\frac{3n(n+1)}{2}+n\end{aligned}
$$

整理后即为
$$
\begin{aligned}\sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}{6}\end{aligned}
$$
继续下去可得
$$
\begin{aligned}\sum_{k=1}^nk^3=[\frac{n(n+1)}{2}]^2\end{aligned}
$$
由此,伯努利得到了$\sum_{k=0}^{n-1}k^m$的通项,如上文。

一个优美的性质

令公式中的$n=1$可得
$$
\begin{aligned}0=\frac{1}{m+1}\sum_{k=0}^mC_{m+1}^kB_k\end{aligned}
$$

$$
\begin{aligned}\sum_{k=0}^mC_{m+1}^kB_k=0\end{aligned}
$$

证明(咕咕咕)

方法1:归纳法

方法2:生成函数


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!