伯努利数

今天看吉米多维奇的时候偶然看到伯努利数，一查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：生成函数