好像大家都是拿差分证的，这里给出一个用伯努利数证明的方法。
感觉似乎比差分简洁 ，但你要是非说理解不能，我也没啥办法
定义 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 。
比较同次项系数可知
\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)
考虑直接做差法证明。首先设出两个式子：
\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}
$$\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$ 次多项式。