附录 A 求和 (Summations)

核心结论

求和基础：有限和 \(\sum_{k=1}^n a_k\) 与无限和 \(\sum_{k=1}^\infty a_k\) 的记号、收敛条件、绝对收敛与重排定理。
线性性 (Linearity)：\(\sum (c a_k + b_k) = c \sum a_k + \sum b_k\)；可与渐近记号交换，是分析算法运行时间的基本工具。
常用闭合公式：算术级数 \(n(n+1)/2\)、平方和 \(n(n+1)(2n+1)/6\)、立方和 \(n^2(n+1)^2/4\)、几何级数 \((x^{n+1} - 1)/(x - 1)\)、调和数 \(H_n = \ln n + O(1)\)。
求和界定技术：数学归纳法、项界定（最大项）、几何级数界定、分裂求和、积分逼近（式 A.11、A.12）——五种常用方法各有适用场景。
乘积转求和：\(\lg \prod_{k=1}^n a_k = \sum_{k=1}^n \lg a_k\)；处理阶乘、组合数时的标准技巧。
积分逼近的两种方向：单调递增用式 A.11（\(\int_{m-1}^n f(x) dx \leq \sum \leq \int_m^{n+1} f(x) dx\)），单调递减方向相反。

附录主旨

本附录是分析算法运行时间时的「数学工具箱」：从基本公式（算术、几何、调和）到上界/下界界定技术。所有渐进分析（Θ, O, Ω）的核心都是把循环迭代次数化为求和再求闭合式。本附录的公式在第 2-9 章、第 15 章、第 17 章、第 27 章等都反复使用——务必熟悉。

一、核心概念

本附录围绕 5 个核心概念展开：基本公式族、线性性、几何级数、调和数、积分逼近。

概念	定义 + 重要性	实现提示
求和记号与线性性	\(\sum_{k=1}^n a_k\) 有限；\(\sum_{k=1}^\infty a_k\) 无限；线性性允许拆分 + 提系数 + 与渐近记号交换。	§A.1；处理循环运行时间时第一工具。
算术级数与幂次和	\(\sum k = n(n+1)/2\)；\(\sum k^2 = n(n+1)(2n+1)/6\)；\(\sum k^3 = n^2(n+1)^2/4\)。	§A.1；分析嵌套循环、插入排序、归并排序等常见。
几何级数	\(\sum_{k=0}^n x^k = (x^{n+1}-1)/(x-1)\)；无限情形 \(\lvert x \rvert < 1\) 时 = \(1/(1-x)\)。	§A.1；递归树分析、指数递减场景关键。
调和数	\(H_n = \sum_{k=1}^n 1/k = \ln n + O(1)\)；bound \(\ln(n+1) \leq H_n \leq \ln n + 1\)。	§A.1、A.2；分析随机化算法、摊还分析时常见。
积分逼近	单调递增 f：\(\int_{m-1}^n f(x) dx \leq \sum_{k=m}^n f(k) \leq \int_m^{n+1} f(x) dx\)；单调递减方向相反。	§A.2；处理 \(\sum 1/k\)、\(\sum \lg k\) 等不可求闭合式的求和。
求和界定技术	归纳法 / 项界定 / 几何界定 / 分裂 / 积分——五种方法各有适用。	§A.2；每种技术都有陷阱（如渐近记号误用、ratio 必须严格 < 1）。

概念

定义 + 重要性

实现提示

求和记号与线性性

\(\sum_{k=1}^n a_k\) 有限；\(\sum_{k=1}^\infty a_k\) 无限；线性性允许拆分 + 提系数 + 与渐近记号交换。

§A.1；处理循环运行时间时第一工具。

算术级数与幂次和

\(\sum k = n(n+1)/2\)；\(\sum k^2 = n(n+1)(2n+1)/6\)；\(\sum k^3 = n^2(n+1)^2/4\)。

§A.1；分析嵌套循环、插入排序、归并排序等常见。

几何级数

\(\sum_{k=0}^n x^k = (x^{n+1}-1)/(x-1)\)；无限情形 \(\lvert x \rvert < 1\) 时 = \(1/(1-x)\)。

§A.1；递归树分析、指数递减场景关键。

调和数

\(H_n = \sum_{k=1}^n 1/k = \ln n + O(1)\)；bound \(\ln(n+1) \leq H_n \leq \ln n + 1\)。

§A.1、A.2；分析随机化算法、摊还分析时常见。

积分逼近

单调递增 f：\(\int_{m-1}^n f(x) dx \leq \sum_{k=m}^n f(k) \leq \int_m^{n+1} f(x) dx\)；单调递减方向相反。

§A.2；处理 \(\sum 1/k\)、\(\sum \lg k\) 等不可求闭合式的求和。

求和界定技术

归纳法 / 项界定 / 几何界定 / 分裂 / 积分——五种方法各有适用。

§A.2；每种技术都有陷阱（如渐近记号误用、ratio 必须严格 < 1）。

二、详细笔记

2.1 求和记号与线性性

What：求和符号 \(\sum_{k=m}^n a_k\) 表示从 k=m 到 n 的累加；空求和（m > n）值为 0；无限求和定义为极限。

Why：求和是把「循环迭代时间」化为「总体运行时间」的标准形式；线性性允许把复杂求和拆分为已知闭合式。

How：

性质	形式
有限和定义	\(\sum_{k=1}^n a_k = a_1 + a_2 + \cdots + a_n\)
空和	\(\sum_{k=m}^n = 0\) 若 m > n
无限和收敛	\(\sum_{k=1}^\infty a_k = \lim_{n \to \infty} \sum_{k=1}^n a_k\) 极限存在
绝对收敛	\(\sum \lvert a_k \rvert < \infty\)（保证重排合法）
线性性	\(\sum (c a_k + b_k) = c \sum a_k + \sum b_k\)
渐近交换	\(\sum \Theta(f(k)) = \Theta(\sum f(k))\)（左侧 Θ 关于 k，右侧关于 n）

性质

形式

有限和定义

\(\sum_{k=1}^n a_k = a_1 + a_2 + \cdots + a_n\)

空和

\(\sum_{k=m}^n = 0\) 若 m > n

无限和收敛

\(\sum_{k=1}^\infty a_k = \lim_{n \to \infty} \sum_{k=1}^n a_k\) 极限存在

绝对收敛

\(\sum \lvert a_k \rvert < \infty\)（保证重排合法）

线性性

\(\sum (c a_k + b_k) = c \sum a_k + \sum b_k\)

渐近交换

\(\sum \Theta(f(k)) = \Theta(\sum f(k))\)（左侧 Θ 关于 k，右侧关于 n）

When：所有循环/递归运行时间分析。

Example：插入排序最坏情况：\(\sum_{j=2}^n \Theta(j) = \Theta(\sum_{j=1}^n j) = \Theta(n^2)\)。

2.2 算术级数、平方和、立方和

What：三项基本幂次和的闭合公式，是嵌套循环分析的核心。

Why：插入排序 \(O(n^2)\)、归并排序递归树等分析都依赖这些公式。

How：

\[\begin{aligned} \sum_{k=1}^n k &= \frac{1}{2} n (n+1) = \Theta(n^2) \quad \text{(式 A.1)} \\ \sum_{k=0}^n k^2 &= \frac{n(n+1)(2n+1)}{6} \quad \text{(式 A.3)} \\ \sum_{k=0}^n k^3 &= \frac{n^2(n+1)^2}{4} \quad \text{(式 A.4)} \end{aligned}\]

When：所有涉及「每层循环执行次数线性增长」的分析。

Example：双重嵌套循环（每层 i 次，第 j 轮迭代 j 步）总迭代次数 \(\sum_{j=1}^n j = n(n+1)/2\)。

2.3 几何级数与导出公式

What：几何级数 \(\sum x^k\) 在 \(x \neq 1\) 时有闭合式，无限情形要求 \(\lvert x \rvert < 1\)。

Why：递归树中每层工作量以常数因子递减、指数/对数函数求导/积分等场景常用。

How：

\[\sum_{k=0}^n x^k = \frac{x^{n+1} - 1}{x - 1} \quad \text{(式 A.5)}\]

\[\sum_{k=0}^\infty x^k = \frac{1}{1-x} \quad \text{(当 } |x| < 1 \text{, 式 A.6)}\]

导出：对 A.6 求导并乘 x 得 \(\sum_{k=0}^\infty k x^k = x / (1-x)^2\)（式 A.8，\(\lvert x \rvert < 1\)）。

When：递归树分析（如归并排序每层总工作量 = n）、指数级数求和、概率分布（如几何分布）。

Example：归并排序递归树：每层总工作量 = n，共 lg n 层 → 总工作量 \(n \lg n\)；也可用几何级数：根 \(n\)，下一层 \(n/2 + n/2 = n\)，等等。

2.4 调和数与积分界定

What：调和数 \(H_n = \sum_{k=1}^n 1/k\) 是增长最慢的非线性求和之一，与 \(\ln n\) 同阶。

Why：调和数在摊还分析、随机化算法（如 quicksort 平均时间）、集合覆盖近似比（35 章）等都出现。

How：

\[\ln(n+1) \leq H_n \leq \ln n + 1 \quad \text{(式 A.13、A.14)}\]

或用「分裂求和」：将 [1, n] 分成 ⌊lg n⌋+1 段，每段元素 ≤ 2^i 个，每个 ≤ 1/2^i，总和 ≤ ⌊lg n⌋ + 1（式 A.10）。

When：分析随机算法期望运行时间（quicksort = Θ(H_n) · n = Θ(n lg n)）、调和增长的界。

Example：quicksort 期望比较次数 = 2(n+1) H_n - 4n = O(n lg n)。

2.5 求和界定技术 (Bounding Techniques)

What：五种常用方法，用于在无法求闭合式时获得上/下界。

Why：很多实际求和（如分治递归树中的合并成本）无简单闭合式；界定技术给出足够精确的渐进界。

How：

技术	适用
典型陷阱	数学归纳法
小型闭合式证明	Θ 记号中「常数」必须真正固定
项界定（最大项）	所有项 ≤ amax
给出较松上界，几何场景过粗	几何级数界定
连续项比 ≤ r < 1（常数）	「比 < 1」不够，必须有常数上界 r
分裂求和	求和项与 n 独立时可丢弃前几项
前几项必须常数个	积分逼近
f 单调且可积	单调性是前提；上下界方向取决于单调性

技术

适用

典型陷阱

数学归纳法

小型闭合式证明

Θ 记号中「常数」必须真正固定

项界定（最大项）

所有项 ≤ amax

给出较松上界，几何场景过粗

几何级数界定

连续项比 ≤ r < 1（常数）

「比 < 1」不够，必须有常数上界 r

分裂求和

求和项与 n 独立时可丢弃前几项

前几项必须常数个

积分逼近

f 单调且可积

单调性是前提；上下界方向取决于单调性

关键陷阱： * 渐近记号在归纳法中：「big-oh 常数随 n 变化」是常见错误（§A.2 例子） * 几何级数界定：要求比值有常数上界 r < 1；调和级数比值 k/(k+1) → 1，无常数上界

When：所有需要「足够紧」的求和界，但不必精确闭合式。

Example：证明 \(\sum_{k=1}^\infty k/3^k < 1\)：改写为 \(\sum_{k=0}^\infty (k+1)/3^{k+1}\)，首项 = 1/3，比值 = (k+2)/3^{k+2} / k+1)/3^{k+1}) = (k+2)/(3(k+1 ≤ 2/3（常数上界）→ 用几何级数 ≤ (1/3) · 1/(1-2/3) = 1。

2.6 积分逼近 (式 A.11, A.12)

What：当 \(f(x)\) 单调时，求和可被积分精确界定。

Why：处理 \(\sum 1/k\)、\(\sum \lg k\)、\(\sum \sqrt{k}\) 等求和的「标准方法」。

How：

\[\int_{m-1}^n f(x)\,dx \;\leq\; \sum_{k=m}^n f(k) \;\leq\; \int_m^{n+1} f(x)\,dx \quad \text{(f 单调递增, 式 A.11)}\]

\[\int_m^{n+1} f(x)\,dx \;\leq\; \sum_{k=m}^n f(k) \;\leq\; \int_{m-1}^n f(x)\,dx \quad \text{(f 单调递减, 式 A.12)}\]

When：求和项是「平滑」函数 f 在整数点的值，且 f 可积。

Example：调和数上界 \(H_n = \sum_{k=1}^n 1/k \leq \int_1^{n+1} dx/x = \ln(n+1)\)。

三、关键图表

核心公式对照表

公式编号

内容

式 A.1

\(\sum_{k=1}^n k = n(n+1)/2 = \Theta(n^2)\)

式 A.3

\(\sum_{k=0}^n k^2 = n(n+1)(2n+1)/6\)

式 A.4

\(\sum_{k=0}^n k^3 = n^2(n+1)^2/4\)

式 A.5

\(\sum_{k=0}^n x^k = (x^{n+1}-1)/(x-1)\)

式 A.6

\(\sum_{k=0}^\infty x^k = 1/(1-x)\)（\(\lvert x \rvert < 1\)）

式 A.7

\(H_n = \ln n + O(1)\)

式 A.8

\(\sum_{k=0}^\infty k x^k = x/(1-x)^2\)

式 A.9

telescoping: \(\sum (a_k - a_{k-1}) = a_n - a_0\)

式 A.10

\(H_n \leq \lfloor \lg n \rfloor + 1\)

式 A.11

单调递增 f 积分逼近

式 A.12

单调递减 f 积分逼近

式 A.13

\(H_n \geq \ln(n+1)\)

式 A.14

\(H_n \leq \ln n + 1\)

四、思维导图

mindmap
  root((附录 A 求和))
    基本记号
      有限与无限
      收敛与重排
      线性性
    常用闭合
      算术级数
      平方立方和
      几何级数
      调和数
    界定技术
      归纳法
      项界定
      几何界定
      分裂求和
    积分逼近
      单调递增
      单调递减
      调和数界
    乘积与对数
      lg乘积转求和
      阶乘分析

五、重点与易错点

渐近记号在归纳法中：「常数 hidden by big-oh 随 n 变化」是常见错误（§A.2 例）——必须明确固定常数 c，验证基础情况和归纳步骤都满足。
几何级数界定要求常数 r < 1：调和级数比值 k/(k+1) → 1，无常数上界，不能用几何级数界定；很多错误是「比 < 1 就以为是几何」。
调和数 \(H_n\) 与 \(\ln n\) 同阶但不相等：\(\ln(n+1) \leq H_n \leq \ln n + 1\)，在算法分析中常被简化写为 \(\ln n + O(1)\)。
积分逼近方向：单调递增用式 A.11，单调递减用式 A.12（上下界颠倒）；弄反会导致错误结论。
平方和 / 立方和 / 算术和 是嵌套循环分析的核心；背诵三个闭合式比每次推导更高效。
几何级数无限情形要求 \(\lvert x \rvert < 1\)——\(x = 1\) 时级数发散，\(x = -1\) 时振荡，\(x > 1\) 时发散。
分裂求和 前几项必须常数个：late xmath:[\sum_{k=0}^\infty k^2/2k = \sum_{k=0}^2 k^2/2k + \sum_{k=3}^\infty k^2/2k]，前 3 项 Θ(1)，尾部用几何级数界定。
乘积转求和：late xmath:[\lg \prod a_k = \sum \lg a_k] 是处理阶乘、组合数的桥梁；斯特林近似是结果之一。
伸缩 (telescoping) 求和 \(\sum (a_k - a_{k-1}) = a_n - a_0\)：对分拆项常有用，如 \(1/(k(k+1)) = 1/k - 1/(k+1)\)。
记号一致性：本附录用 \(\sum_{k=1}^n\)；部分上下文用 \(\sum_{k=0}^{n-1}\)；转换时注意边界（off-by-one）。
运行时间 vs 求和：每个循环的迭代次数 + 每步代价 = 总时间；本附录的公式用于「求总迭代次数」这一步。
APX 技术选择：闭合式 > 积分 > 分裂 > 几何 > 项界定；优先选择能给出最紧界的工具。