题解 CF622F 【The Sum of the k-th Powers】

好像大家都是拿差分证的，这里给出一个用伯努利数证明的方法。 感觉似乎比差分简洁 ~~，但你要是非说理解不能，我也没啥办法~~ _____ 定义 $e(x)$ 为如下的多项式 $$e(x)=1+x+\frac{x^2}{2!}+\cdots +\frac{x^n}{n!}+\cdots$$ ## 伯努利数的定义 考虑用母函数的方式定义。此处直接定义伯努利数的指数型母函数是： $$\mathbf B=\frac{x}{e(x)-1}$$ 那么考虑如何展开。记伯努利数为 $\{B_n\}$。发现移一下项 $$x=\left(B_0+B_1x+\frac{B_2}{2!}x^2\cdots\right) * \left(e(x)-1\right)$$ 如果记右边卷出来的结果是 $\{a_n\}$，那么发现 $$a_n=\sum_{k=0}^{n-1}\binom{n}{k}B_k$$ 此处上界为 $n-1$ 的原因是 $\left(e(x)-1\right)_0=0$ ，其余项均为 $1$ 。 比较同次项系数可知 $$B_0=1, \sum_{k=0}^{n-1}\binom{n}{k}B_k=0\qquad (n=2,3,4\cdots)$$ 考虑用这个方程去递推每一项。大致思路是左右两边同时加上 $B_n$ 。 $$\sum_{k=0}^{n}\binom{n}{k}B_k=B_n$$ 然后就可以发现，比如拿 $n=2$ 举例： $$B_0+2B_1+B_2=B_2$$ 就可以消掉 $B_2$ 求出 $B_1$。以此类推，每次用 $n$ 可以消出 $B_{n-1}$ 。 ## 伯努利多项式 考虑观察下列两个EGF的卷积： $$\frac{x}{e(x)-1}*e(tx)$$ 其中 $t$ 是任意常数。考虑记卷积结果为 $\beta(t)$ 。那么显然 $$\beta_n(t)=\sum_{k=0}^n\binom{n}{k}B_kt^{n-k}$$ 记这样的多项式为伯努利多项式。这个多项式有个很有用的性质： $$\beta_{n+1}(t + 1)-\beta_{n+1}(t)=t^n(n+1)\qquad(n=0,1,2,3\cdots)$$ 考虑直接做差法证明。首先设出两个式子： $$\begin{aligned} \frac{xe(tx)}{e(x)-1}&=\sum\frac{\beta_n(t)}{n!}x^n\qquad(1)\\ \frac{xe((t+1)x)}{e(x)-1}&=\sum\frac{\beta_n(t+1)}{n!}x^n\qquad(2)\\ \end{aligned}$$ $(2)-(1)$ 得到 $$\frac{xe(tx)[e(x)-1]}{e(x)-1}=\sum\frac{\beta_n(t+1)-\beta_n(t)}{n!}x^n$$ 即 $$xe(tx)=\sum\frac{\beta_n(t+1)-\beta_n(t)}{n!}x^n$$ 比较系数可知 $$\frac{\beta_n(t+1)-\beta_n(t)}{n!}=\frac{t^{n-1}}{(n-1)!}$$ 变一下形就可以得到： $$\beta_{n+1}(t + 1)-\beta_{n+1}(t)=t^n(n+1)$$ ## 用伯努利多项式求自然数的 $k$ 次方和 考虑决定自然数 $k$ 次方的要素在于下标 $n$ 。于是考虑所有自然数的 $k$ 次方和就是这样： $$(k+1)\mathbf S^{(k)}=\sum_{i=1}^{\infty}\left(\beta_{k+1}(i+1)-\beta_{k+1}(i)\right)$$ 展开之后 $$\mathbf S_n^{(k)}=\frac{\left(\beta_{k+1}(n+1)-\beta_{k+1}(1)\right)}{k+1}$$ 也就是 $$\mathbf S_n^{(k)}=\frac{1}{k+1}\sum_{r=1}^{k+1}\binom{k+1}{r}B_{k+1-r}(n+1)^{r}$$ 于是可以知道，自然数的 $k$ 次方和是关于 $n$ 的一个 $k+1$ 次多项式。