数列求和的几种常用方法

等差与等比各有求和闭式，其余数列的求和靠把它化归到这两族上。常用的三条路线各有明确判据：通项是「等差乘等比」的用错位相减，能拆成相邻两项之差的用裂项相消，正负交替或奇偶项形态不同的先分组。判据看的是通项的结构，不是题目的来源。

1 · 错位相减

通项形如 $c_k = (a_1 + (k-1)d) \cdot q^{k-1}$，即一个等差因子乘一个等比因子。两边乘公比 $q$ 后错开一位相减，中间的 $n - 1$ 项各自留下一个 $d \cdot q^{k}$，合成一个等比和：

$q = 1$ 时整族退化成纯等差，上式的分母为零，须换回等差求和公式。

2 · 裂项相消

判据是通项能否写成 $a_k = u_k - u_{k+1}$。写得出这个 $u$，求和就只剩首尾：$S_n = u_1 - u_{n+1}$，中间全部抵消。三族常见形式：

第二行的因子 $\frac{1}{2}$ 来自两个因式之差：$(2n+1) - (2n-1) = 2$，故拆开时要除以这个差。漏掉它是裂项最常见的错处，检查办法是把 $n = 1$ 代回原式与拆分式各算一次。第三行靠分母有理化拆开，$\frac{1}{\sqrt{n+1}+\sqrt{n}}$ 分子分母同乘 $\sqrt{n+1}-\sqrt{n}$ 即得。

按代码里的写法，第三族的 $u_k$ 是 $-\sqrt{k}$ 而不是 $\sqrt{k}$：$a_k = u_k - u_{k+1}$ 这个形式要求「后一项被减掉」，而 $\sqrt{k+1} - \sqrt{k}$ 里增大的那一项是加号在前的，故须整体取负号才对上。这不是符号疏漏，TELESCOPES 三族共用同一条 $S_n = u_1 - u_{n+1}$，$u$ 的写法就得服从它。

3 · 分组求和与倒序相加

正负交替的数列先按奇偶分组。$S_n = 1 - 2 + 3 - 4 + \dots$ 中相邻两项配成一组，每组的和都是 $-1$：$n$ 为偶数时 $S_n = -\frac{n}{2}$，$n$ 为奇数时把最后一项单独留下，$S_n = \frac{n+1}{2}$。分情形来自「能否配平」，与数列本身无关。

倒序相加则是等差求和公式的来源（见 等差数列与前 n 项和 §3）。它适用的场合比等差更宽：只要首末对称的两项之和是常数，倒着写一遍相加就能把和化成 $n$ 组同值。

4 · 闭式与逐项累加的数值差

三种方法给出的都是闭式，而闭式与逐项累加在浮点下并不逐位相同。裂项一族的差随项数增长：$\sum \frac{1}{k(k+1)}$ 在 $n = 1000$ 时两者差 $6.7 \times 10^{-16}$，$n = 10^6$ 时差 $4.8 \times 10^{-14}$——累加了一百万个数，每次舍入的误差攒起来就是这个量级，而闭式只算两次除法。

等差一侧反而看不出差别：$a_1 = d = 0.1$ 时逐项累加到 $n = 10^7$，与闭式 $na_1 + \frac{n(n-1)}{2}d$ 的差恰为 $0$。原因是这一族的部分和都落在双精度能精确表示的量级上，舍入没有可积累的余地。本系列的单测因此仍拿逐项累加当 oracle，但比对用的是相对误差而非逐位相等：闭式是被验的一方，累加值是参照，两者的角色不能反过来——参照本身带误差的时候，差额说明不了谁对。

5 · 参考文献

1. Telescoping series. Wikipedia. 裂项相消的一般形式与判据。https://en.wikipedia.org/wiki/Telescoping_series
2. Summation by parts. Wikipedia. 错位相减的一般形式（阿贝尔变换）。https://en.wikipedia.org/wiki/Summation_by_parts
3. Kahan summation algorithm. Wikipedia. 逐项累加的误差累积，以及补偿求和的做法。https://en.wikipedia.org/wiki/Kahan_summation_algorithm