几种计算平方和的方法

问题：计算

$S_n = \sum_{k=0}^n k^n$

大胆假设，归纳法验证

也许你能一下子猜到，

$S_n = \frac{n(n+1)(2n+1)}{6}.$

显然有 $S_0=0$，假设 $n>0$，且 $n-1$ 时上式成立，由于有 $S_n = S_{n-1}+n^2$，那么就有

$\begin{aligned} 6S_n&=n(n-1)(2n-1)+6n^2\\ &=(2n^3-3n^2+n)+6n^2\\ &=2n^3+3n^2+n\\ &=n(n+1)(2n+1). \end{aligned}$

因此上式成立。

分离 $S_{n+1}$ 的第一项与最后一项，用两种方法改写 $S_n$，得到关于 $S_n$ 的一个方程

$\begin{aligned} S_n+(n+1)^2 &= \sum_{k=0}^n (k+1)^2\\ &= \sum_{k=0}^n (k^2+2k+1)\\ &= S_n + 2\sum_{k=0}^n k + (n+1). \end{aligned}$

遗憾的是，两边的 $S_n$ 被消掉了。但是，这仍得到了一个结果

$2\sum_{k=0}^n k = (n+1)^2 - (n+1).$

这似乎暗示了一种得到封闭形式的方法，现在考虑整数的立方 $T_n$，对其使用扰动法

$\begin{aligned} T_n+(n+1)^3 &= \sum_{k=0}^n (k+1)^3\\ &= \sum_{k=0}^n (k^3+3k^2+3k+1)\\ &= T_n + 3S_n + \frac{3n(n+1)}{2} + (n+1). \end{aligned}$

因此便能够得到上面的结果。