n的a次方求和问题

本文通过推导 n, n² 和 n³ 的求和公式最终引出 Faulhaber’s formula，即 n 的 a 次方求和公式。

前言

常见的 n 项递增数列的求和公式有以下 3 个：

$\sum_{k=1}^n{k=\frac{n\left(n+1\right)}{2}}$

$\sum_{k=1}^n{k^2=\frac{n\left( n+1 \right) \left( 2n+1 \right)}{6}}$

$\sum_{k=1}^n{k^3=\frac{n\left( n+1 \right) \left( 2n+1 \right)}{6}}$

其中关于第一个公式的故事大概已经是家喻户晓了，不过据说高斯当时真正解出的题，比 1 加到 100 要难多了。正如传说中高斯的解法一样，从 1 加到 n，我们只需要重新组合这些数：

$(1 + n) + [2 + (n-1)] + ... + [n + (n+1)]$

每一组的值都是相等的，都等于 $n + 1$，总共有 $n/2$ 组，因此就可以很方便地得到等差数列的求和公式。

然而我们无法使用这个方法来求 $1^2+2^2+...+n^2$，而在弦论、量子力学、人工智能等前沿学科中，这种方式（$\sum{n^a}$）的求和会非常常见，因此了解如何推导这样的求和公式就非常有意义。通过查找资料发现^[1]，这个式子的求和公式最早是由德国数学家 Faulhaber 提出的，因此也叫做 Faulhaber’s formula：

$\sum_{k=1}^n{k^a}=\frac{1}{a+1}\sum_{j=0}^a{\left( -1 \right) ^j\left( \begin{array}{c} a+1\\ j\\ \end{array} \right) B_jn^{a+1-j}}$

前 n 个正整数的总和

了解上面这个公式前先看看另一种推导 $\sum{n}$ 的方法：

1. 首先二项式展开：

$(k-1)^2 = k^2 -2k + 1$

2. 重新排列项目：

$k^2 - (k-1)^2 = 2k - 1$

3. 对等式两边求和：

$\sum_{k=1}^n{\left( k^2-\left( k-1 \right) ^2\right)}=2\sum_{k=1}^n{k-}\sum_{k=1}^n{1}$

4. 调整位置后求解得到：$n^2 = 2S_n - n$。

根据最终得到的式子求出 $S_n$ 即可得到 $\sum{n}$ 的计算公式。

前 n 个正整数平方的总和

用同样的方法，这次我们推导 $\sum{n^2}$：

1. 首先二项式展开：

$(k-1)^3 = k^3 - 3k^2 + 3k - 1$

2. 重新排列项目：

$k^3 - (k-1)^3 = 3k^2 - 3k + 1$

3. 和之前一样对两边求和，可以得到：

$\begin{aligned} n^3&=3\left( \sum_{k=1}^n{k^2} \right) -3\sum_{k=1}^n{k}+\sum_{k=1}^n{1} \\ &=3\left( \sum_{k=1}^n{k^2} \right) -3\frac{n\left( n+1 \right)}{2}+n \end{aligned}$

4. 调整位置后求解得到：

$\begin{aligned} \sum_{k=1}^n{k^2}&=\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n\\ &=\frac{n\left( n+1 \right) \left( 2n+1 \right)}{6}\\ \end{aligned}$

前 n 个正整数的 3 次方的总和

用同样的办法，求和后可以得到：

$n^4 = 4S_{3,n} - 6S_{2,n} + 4S_{1,n} - n$

结合上面求到的 $S_{3,n}$、$S_{2,n}$、$S_{1,n}$ 可得：

$\begin{aligned} 4S_{3,n}&=n^4+6\frac{n\left( n+1 \right) \left( 2n+1 \right)}{6}-4\frac{n\left( n+1 \right)}{2}+n\\ S_{3,n}&=\frac{1}{4}n^4+\frac{1}{2}n^3+\frac{1}{4}n^2\\ &=\frac{n^2\left( n+1 \right) ^2}{4}\\ \end{aligned}$

一般化

根据上面的推导，我们可以把 $S_{a,n} = \sum{n^a}$ 一般化为：

$n^{a+1}=\left( \begin{array}{c} a+1\\ 1\\ \end{array} \right) S_{a,n}-\left( \begin{array}{c} a+1\\ 2\\ \end{array} \right) S_{a-1,n}+\left( \begin{array}{c} a+1\\ 3\\ \end{array} \right) S_{a-2,n}-\cdots +\left( -1 \right) ^{a-1}\left( \begin{array}{c} a+1\\ a\\ \end{array} \right) S_{1,n}+\left( -1 \right) ^an$

然后便可以解出 $S_{a,n}$ 的表达式（其中 $c_i$ 代表有理数）：

$S_{a,n}=\frac{1}{a+1}n^{a+1}+c_{a-1}S_{a-1,n}+c_{a-2}S_{a-2,n}+\cdots +c_1S_{1,n}+c_0n$

注意： 通过观察可以发现，这个和式近似于积分 $\int_0^n{x^adx=\frac{1}{a+1}n^{a+1}}$（低级项可看作误差）

Faulhaber 公式

由于我们可以把 $S_{a,n}$ 近似地表达为 $S_{a,n} = \frac{1}{a+1}n^{a+1} + (lower\ terms)$，因此现在的问题就变成了如何找到 $lower\ terms$ 的一个精确解。事实上，我们可以用伯努利数来实现，从而得到了 Faulhaber’s formula：

$\sum_{k=1}^n{k^a}=\frac{1}{a+1}\sum_{j=0}^a{\left( -1 \right) ^j\left( \begin{array}{c} a+1\\ j\\ \end{array} \right) B_jn^{a+1-j}}$

1. Sum of n, n², or n³ ↩