n的a次方求和问题

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

前言

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

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

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

k=1nk3=n(n+1)(2n+1)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+(n1)]+...+[n+(n+1)](1 + n) + [2 + (n-1)] + ... + [n + (n+1)]

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

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

k=1nka=1a+1j=0a(1)j(a+1j)Bjna+1j\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 个正整数的总和

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

  1. 首先二项式展开:

(k1)2=k22k+1(k-1)^2 = k^2 -2k + 1

  1. 重新排列项目:

k2(k1)2=2k1k^2 - (k-1)^2 = 2k - 1

  1. 对等式两边求和:

k=1n(k2(k1)2)=2k=1nkk=1n1\sum_{k=1}^n{\left( k^2-\left( k-1 \right) ^2\right)}=2\sum_{k=1}^n{k-}\sum_{k=1}^n{1}

  1. 调整位置后求解得到:n2=2Snnn^2 = 2S_n - n

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

前 n 个正整数平方的总和

用同样的方法,这次我们推导 n2\sum{n^2}

  1. 首先二项式展开:

(k1)3=k33k2+3k1(k-1)^3 = k^3 - 3k^2 + 3k - 1

  1. 重新排列项目:

k3(k1)3=3k23k+1k^3 - (k-1)^3 = 3k^2 - 3k + 1

  1. 和之前一样对两边求和,可以得到:

n3=3(k=1nk2)3k=1nk+k=1n1=3(k=1nk2)3n(n+1)2+n\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}

  1. 调整位置后求解得到:

k=1nk2=13n3+12n2+16n=n(n+1)(2n+1)6\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 次方的总和

用同样的办法,求和后可以得到:

n4=4S3,n6S2,n+4S1,nnn^4 = 4S_{3,n} - 6S_{2,n} + 4S_{1,n} - n

结合上面求到的 S3,nS_{3,n}S2,nS_{2,n}S1,nS_{1,n} 可得:

4S3,n=n4+6n(n+1)(2n+1)64n(n+1)2+nS3,n=14n4+12n3+14n2=n2(n+1)24\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}

一般化

根据上面的推导,我们可以把 Sa,n=naS_{a,n} = \sum{n^a} 一般化为:

na+1=(a+11)Sa,n(a+12)Sa1,n+(a+13)Sa2,n+(1)a1(a+1a)S1,n+(1)ann^{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

然后便可以解出 Sa,nS_{a,n} 的表达式(其中 cic_i 代表有理数):

Sa,n=1a+1na+1+ca1Sa1,n+ca2Sa2,n++c1S1,n+c0nS_{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

注意: 通过观察可以发现,这个和式近似于积分 0nxadx=1a+1na+1\int_0^n{x^adx=\frac{1}{a+1}n^{a+1}}(低级项可看作误差)

Faulhaber 公式

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

k=1nka=1a+1j=0a(1)j(a+1j)Bjna+1j\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的a次方求和问题
https://infiniture.cn/2019/09/30/n的a次方求和问题/
作者
NickHopps
发布于
2019年9月30日
许可协议