小学数学之前 n 个正整数的 a 次方之和

---

我不如小学生.png

作为高中生, 被小学奥 (chang) 数 (shi) 针对了.

于是, 这里集中了形如 $\sum_{i=1}^n i^a, (a = 1, 2, 3, \ldots )$, 即前 $n$ 个正整数的 $a$ 次方和的计算公式.

简单结论

首先, 有以下结论

$$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$ $$\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$$ $$\sum_{i=1}^n i^{3} = \frac{n^2(n+1)^2}{4}$$

至此, 本文结束, 你不应该在这个乐色结论上浪费太多时间 (.

结论证明

• $a = 1$

  设 $S_n = \sum_{i=1}^n i$, 并容易发现这就是个公差为 $1$ 的等差数列, 直接上求和公式即可.

  但是, 这是小学生的数学, 我们换一种方式

  $$S_n = 1 + 2 + 3 + \cdots + (n-2) + (n-1) + n \\ S_n = n + (n-1) + (n-2) + \cdots + 3 + 2 + 1$$

  显然有

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

  这是个数列里普通的技巧 “倒序相加”, 也就能拿来骗小学生玩了

  但是这个方法不能推广到 $a=2$ 的情况, 于是继续换一种方式

  我们有 $(k-1)^2 = k^2 - 2k + 1$, 移项得 $k^2 - (k-1)^2 = 2k - 1$

  所以

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

  所以

  $$n^2 = 2S_n - n \\ S_n = \frac{n(n+1)}{2}$$

• $a = 2$

  同样, 设 $S_n = \sum_{i=1}^n i^2$, 有 $(k-1)^3 = k^3 - 3k^2 + 3k - 1$

  移项, 得

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

  所以

  $$\sum_{i=1}^n k^3 - \sum_{i=1}^n (k-1)^3 = 3 \sum_{k=1}^n k^2 - 3 \sum_{i=1}^n k + n$$ $$\sum_{i=1}^n k^3 - \sum_{i=1}^{n-1} k^3 = n^3 = 3 \sum_{k=1}^n k^2 - 3 \sum_{i=1}^n k + n$$

  经过一番代换, 有

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

• $a = 3$

  同理可得, 留给读者当作练习 (

  $$\sum_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4}$$

  当然, 这个公式有另一种理解方式

  $$\sum_{i=1}^n i^3 = (\sum_{i=1}^n i)^2 = \frac{n(n+1)}{2} \cdot \frac{n(n+1)}{2}$$

  这是为什么呢, 可以参考 Nicomachus’s Proof

• $a \geq 4$

  可以用很多方法做, 然而我只会拉格朗日插值.

  • 拉格朗日插值

    详见 CF622F The Sum of the k-th Powers, 好的实现可以在 $O(a)$ 的时间内计算.

参考资料

• https://brilliant.org/wiki/sum-of-n-n2-or-n3/
• https://proofwiki.org/wiki/Sum_of_Sequence_of_Cubes

---