第2章求和 (Summation)

一、导读

2.1 本章学习目标

在本章结束时，你将能够：

掌握求和符号 Σ 的基本运算规则和性质
运用扰动法求解复杂求和问题，理解其核心思想
交换多重求和顺序，简化复杂表达式
使用有限微积分方法处理求和问题
识别常见求和模式：等差数列、等比数列、调和级数等
应用求和技术分析算法的时间复杂度
理解无穷级数与有限求和的区别与联系

2.2 为什么本章如此重要

求和是计算机科学中最基本的操作之一。从计算数组元素的总和，到分析算法的时间复杂度，再到概率论中的期望值计算，求和无处不在。然而，许多程序员对求和的理解停留在"逐项相加"的层面，缺乏系统性的技巧。

《具体数学》将求和作为第二章，正是因为它是后续章节（如二项式系数、特殊数、渐近分析）的基础工具。掌握求和技巧，意味着你能够：

精确分析算法：不依赖实验测量，而是通过数学推导得出精确的运行时间

优化代码性能：识别可以简化的求和表达式，避免不必要的循环

理解高级主题：生成函数、离散概率等高级内容都建立在求和基础之上

对于程序员而言，求和不仅是数学工具，更是思维训练。学会从不同角度看待同一个求和问题，能够培养灵活的数学直觉。

2.3 核心问题引导

在阅读本章之前，请思考以下问题：

如何快速计算 1 + 2 + 3 + ... + n？高斯的方法是什么？

扰动法的核心思想是什么？为什么 S + a_{n+1} 的变换如此有效？

双重求和 ∑∑ a_{ij} 中，交换求和顺序的条件是什么？

什么是有限微积分？它与连续微积分有何异同？

调和数 H_n = 1 + 1/2 + 1/3 + ... + 1/n 有闭合形式吗？为什么？

如何将求和问题转化为递推关系？

无穷级数与有限求和在处理方法上有何不同？

在算法分析中，哪些场景会用到求和技术？

二、核心概念详解

2.1 求和符号与基本规则

求和符号的定义

求和符号 Σ（Sigma）是数学中表示累加的标准记号：

$$\sum_{k=1}^{n} a_k = a_1 + a_2 + a_3 + \cdots + a_n$$

其中：

k 是求和指标（index of summation）
1 是下限（lower bound）
n 是上限（upper bound）
a_k 是被加项（summand）

通俗地说，Σ 就像一个循环：for k in range(1, n+1): sum += a[k]

基本运算规则

规则 1：线性性

$$\sum_{k=1}^{n} (ca_k + b_k) = c\sum_{k=1}^{n} a_k + \sum_{k=1}^{n} b_k$$

其中 c 是常数。这条规则允许我们将复杂的求和拆分为简单的部分。

规则 2：常数求和

$$\sum_{k=1}^{n} c = cn$$

常数 c 被加了 n 次。

规则 3：指标平移

$$\sum_{k=1}^{n} a_k = \sum_{j=0}^{n-1} a_{j+1} = \sum_{i=m}^{m+n-1} a_{i-m+1}$$

求和指标只是一个"哑变量"，可以任意替换，只要保持对应关系。

规则 4：拆分求和范围

$$\sum_{k=1}^{n} a_k = \sum_{k=1}^{m} a_k + \sum_{k=m+1}^{n} a_k$$

其中 1 ≤ m < n。这条规则在分治算法分析中非常有用。

常见求和公式

以下是必须熟记的基本求和公式：

等差数列求和：

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

证明（高斯方法）：设 S = 1 + 2 + 3 + ... + n，则

$$S = 1 + 2 + 3 + \cdots + n$$

$$S = n + (n-1) + (n-2) + \cdots + 1$$

两式相加：2S = n(n+1)，所以 S = n(n+1)/2。

等比数列求和：

$$\sum_{k=0}^{n} x^k = \frac{x^{n+1} - 1}{x - 1}, \quad x \neq 1$$

证明：设 S = 1 + x + x² + ... + xⁿ，则 xS = x + x² + ... + xⁿ + xⁿ⁺¹。

两式相减：xS - S = xⁿ⁺¹ - 1，所以 S = (xⁿ⁺¹ - 1)/(x - 1)。

特别地，当 x = 2 时：

$$\sum_{k=0}^{n} 2^k = 2^{n+1} - 1$$

平方和：

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

立方和：

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

这个公式非常优美：前 n 个数的立方和等于它们的和的平方。

2.2 扰动法：求和的巧妙变换

扰动法（Perturbation Method）是《具体数学》中最具创意的求和技术之一。其核心思想是：将求和 S 与其自身的一个"扰动"版本进行比较，通过代数操作消去大部分项，从而得到闭合形式。

基本原理

设 S = a₀ + a₁ + a₂ + ... + aₙ。考虑 S + a_{n+1}：

$$S + a_{n+1} = a_0 + a_1 + a_2 + \cdots + a_n + a_{n+1}$$

另一方面，如果我们将每一项用递推关系表示，可能会得到另一个关于 S 的表达式。比较这两个表达式，就能解出 S。

示例 1：等比数列求和

让我们用扰动法重新推导等比数列求和公式。

设 $S = \sum_{k=0}^{n} x^k = 1 + x + x^2 + \cdots + x^n$。

考虑 S + xⁿ⁺¹：

$$S + x^{n+1} = 1 + x + x^2 + \cdots + x^n + x^{n+1}$$

另一方面，将 S 乘以 x：

$$xS = x + x^2 + x^3 + \cdots + x^{n+1}$$

观察发现：S + xⁿ⁺¹ = 1 + xS。因此：

$$S + x^{n+1} = 1 + xS$$

$$S - xS = 1 - x^{n+1}$$

$$S(1-x) = 1 - x^{n+1}$$

$$S = \frac{1 - x^{n+1}}{1 - x} = \frac{x^{n+1} - 1}{x - 1}$$

这与之前的结果一致，但推导过程更加优雅。

示例 2：求 ∑ k·2ᵏ

这是一个经典的算法分析问题。设 $S = \sum_{k=0}^{n} k \cdot 2^k$。

直接计算很困难，我们使用扰动法。首先写出 S 的展开：

$$S = 0 \cdot 2^0 + 1 \cdot 2^1 + 2 \cdot 2^2 + 3 \cdot 2^3 + \cdots + n \cdot 2^n$$

考虑 2S：

$$2S = 0 \cdot 2^1 + 1 \cdot 2^2 + 2 \cdot 2^3 + \cdots + (n-1) \cdot 2^n + n \cdot 2^{n+1}$$

现在计算 S - 2S：

$$S - 2S = 0 \cdot 2^0 + (1-0) \cdot 2^1 + (2-1) \cdot 2^2 + (3-2) \cdot 2^3 + \cdots + (n-(n-1)) \cdot 2^n - n \cdot 2^{n+1}$$

$$-S = 0 + 2^1 + 2^2 + 2^3 + \cdots + 2^n - n \cdot 2^{n+1}$$

$$-S = \sum_{k=1}^{n} 2^k - n \cdot 2^{n+1}$$

$$-S = (2^{n+1} - 2) - n \cdot 2^{n+1}$$

$$-S = 2^{n+1}(1-n) - 2$$

$$S = (n-1) \cdot 2^{n+1} + 2$$

验证：n = 3 时，S = 0·1 + 1·2 + 2·4 + 3·8 = 0 + 2 + 8 + 24 = 34。

公式给出：(3-1)·2⁴ + 2 = 2·16 + 2 = 34。✓

示例 3：求 ∑ k·xᵏ（一般情况）

设 $S = \sum_{k=0}^{n} k \cdot x^k$。

类似地：

$$S = 0 + 1x + 2x^2 + 3x^3 + \cdots + nx^n$$

$$xS = 0 + 1x^2 + 2x^3 + \cdots + (n-1)x^n + nx^{n+1}$$

$$S - xS = x + x^2 + x^3 + \cdots + x^n - nx^{n+1}$$

$$S(1-x) = \sum_{k=1}^{n} x^k - nx^{n+1}$$

$$S(1-x) = \frac{x(x^n - 1)}{x - 1} - nx^{n+1}$$

$$S = \frac{x(x^n - 1)}{(x-1)^2} - \frac{nx^{n+1}}{1-x}$$

化简后：

$$S = \frac{x - (n+1)x^{n+1} + nx^{n+2}}{(1-x)^2}$$

当 |x| < 1 且 n → ∞ 时，xⁿ⁺¹ 和 xⁿ⁺² 趋于 0，得到无穷级数：

$$\sum_{k=0}^{\infty} k \cdot x^k = \frac{x}{(1-x)^2}$$

扰动法的通用策略

扰动法的关键在于找到合适的"扰动"方式。常见策略包括：

添加末项：考虑 S + a_{n+1}

乘以常数：考虑 cS，特别是当 a_k 包含指数项时

指标平移：考虑 S - a₀ + a_{n+1}

分组重组：将项重新分组，寻找可消去的模式

2.3 多重求和与交换顺序

双重求和的定义

双重求和是对两个指标进行累加：

$$\sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij} = \sum_{i=1}^{m} \left(\sum_{j=1}^{n} a_{ij}\right)$$

通俗地说，这相当于嵌套循环：外层遍历 i，内层遍历 j。

交换求和顺序

对于有限求和，交换顺序总是合法的：

$$\sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij} = \sum_{j=1}^{n} \sum_{i=1}^{m} a_{ij}$$

直观理解：无论是先按行求和再按列求和，还是先按列求和再按行求和，最终都是将所有元素相加。

示例 1：计算 ∑∑ ij

计算 $\sum_{i=1}^{n} \sum_{j=1}^{n} ij$。

方法 1：先对内层求和

$$\sum_{i=1}^{n} \sum_{j=1}^{n} ij = \sum_{i=1}^{n} i \left(\sum_{j=1}^{n} j\right) = \sum_{i=1}^{n} i \cdot \frac{n(n+1)}{2} = \frac{n(n+1)}{2} \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \cdot \frac{n(n+1)}{2} = \frac{n^2(n+1)^2}{4}$$

方法 2：利用独立性

由于 ij = i × j，且 i 和 j 独立：

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

两种方法结果一致。

示例 2：三角形区域的求和

计算 $\sum_{1 \leq i \leq j \leq n} ij$，即只对满足 i ≤ j 的 (i,j) 对求和。

这个求和区域是一个三角形：

j=1: (1,1)
j=2: (1,2), (2,2)
j=3: (1,3), (2,3), (3,3)
...
j=n: (1,n), (2,n), ..., (n,n)

方法 1：固定 j，对 i 求和

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

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

方法 2：交换顺序，固定 i，对 j 求和

$$\sum_{i=1}^{n} \sum_{j=i}^{n} ij = \sum_{i=1}^{n} i \left(\sum_{j=i}^{n} j\right) = \sum_{i=1}^{n} i \cdot \frac{(i+n)(n-i+1)}{2}$$

这种方法稍复杂，但两种方法应该得到相同结果。

示例 3：算法分析中的应用

考虑以下代码的时间复杂度：

python

count = 0
for i in range(1, n+1):
    for j in range(i, n+1):
        count += 1

内层循环执行次数为 n - i + 1，总次数为：

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

这里我们用到了指标替换 k = n+1-i。

2.4 有限微积分：离散的微积分

有限微积分（Finite Calculus）是将连续微积分的概念推广到离散域的工具。它为求和提供了系统性的方法。

差分算子

定义向前差分算子 Δ：

$$\Delta f(x) = f(x+1) - f(x)$$

这与导数 df/dx 类似，但适用于离散函数。

示例：

Δx = (x+1) - x = 1
Δx² = (x+1)² - x² = 2x + 1
Δ2ˣ = 2ˣ⁺¹ - 2ˣ = 2ˣ

下降幂

为了简化有限微积分的计算，引入下降幂（falling power）：

$$x^{\underline{n}} = x(x-1)(x-2)\cdots(x-n+1)$$

其中 x⁰̲ = 1，x¹̲ = x，x²̲ = x(x-1)，等等。

下降幂的美妙之处在于它的差分形式非常简单：

$$\Delta x^{\underline{n}} = n \cdot x^{\underline{n-1}}$$

证明：

$$\Delta x^{\underline{n}} = (x+1)^{\underline{n}} - x^{\underline{n}} = (x+1)x(x-1)\cdots(x-n+2) - x(x-1)\cdots(x-n+1)$$

$$= x(x-1)\cdots(x-n+2)[(x+1) - (x-n+1)] = x^{\underline{n-1}} \cdot n$$

这与连续微积分中 d(xⁿ)/dx = nxⁿ⁻¹ 的形式完全一致！

普通幂到下降幂的转换

我们需要将普通幂表示为下降幂的线性组合：

x⁰ = 1 = x⁰̲
x¹ = x = x¹̲
x² = x(x-1) + x = x²̲ + x¹̲
x³ = x(x-1)(x-2) + 3x(x-1) + x = x³̲ + 3x²̲ + x¹̲

一般地，$x^n = \sum_{k=0}^{n} \left\{ {n \atop k} \right\} x^{\underline{k}}$，其中 {n \atop k} 是第二类斯特林数（将在第 6 章详细讨论）。

不定和与定和

类比于不定积分，定义不定和：

$$\Delta^{-1} f(x) = g(x) \iff \Delta g(x) = f(x)$$

基本定理（离散版本的微积分基本定理）：

$$\sum_{k=a}^{b-1} f(k) = g(b) - g(a)$$

其中 g(x) 是 f(x) 的不定和，即 Δg(x) = f(x)。

示例：计算 $\sum_{k=0}^{n-1} k^{\underline{2}}$。

由于 Δx³̲ = 3x²̲，所以 Δ(x³̲/3) = x²̲。因此：

$$\sum_{k=0}^{n-1} k^{\underline{2}} = \left.\frac{x^{\underline{3}}}{3}\right|_0^n = \frac{n^{\underline{3}}}{3} - 0 = \frac{n(n-1)(n-2)}{3}$$

分部求和

类比于分部积分，有分部求和公式：

$$\sum u \Delta v = uv - \sum Ev \Delta u$$

其中 E 是移位算子：Ef(x) = f(x+1)。

这个公式在处理形如 ∑ k·xᵏ 的求和时非常有用。

2.5 调和数：没有闭合形式的求和

定义

调和数（Harmonic Numbers）定义为：

$$H_n = \sum_{k=1}^{n} \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$$

调和数之所以重要，是因为它频繁出现在算法分析中（如快速排序的平均情况分析），但它没有简单的闭合形式。

基本性质

递推关系：

$$H_n = H_{n-1} + \frac{1}{n}, \quad H_1 = 1$$

与其他求和的关系：

$$\sum_{k=1}^{n} \frac{H_k}{k} = \frac{H_n^2 + H_n^{(2)}}{2}$$

其中 $H_n^{(2)} = \sum_{k=1}^{n} \frac{1}{k^2}$ 是广义调和数。

渐近近似

虽然 H_n 没有精确的闭合形式，但有非常好的渐近近似：

$$H_n = \ln n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + O\left(\frac{1}{n^4}\right)$$

其中 γ ≈ 0.5772156649 是欧拉-马斯刻若尼常数（Euler-Mascheroni constant）。

通俗地说，对于大的 n，H_n ≈ ln n + γ。

直观理解：调和级数与自然对数的联系可以通过积分近似理解：

$$H_n = \sum_{k=1}^{n} \frac{1}{k} \approx \int_1^n \frac{1}{x} dx = \ln n$$

更精确的近似需要考虑曲线下的面积与矩形和的差异。

在算法分析中的应用

示例 1：快速排序的平均比较次数

快速排序的平均比较次数约为 2n ln n ≈ 1.386 n log₂ n。

示例 2：优惠券收集问题

假设有 n 种不同的优惠券，每次随机获得一种，问平均需要多少次才能集齐所有种类？

答案是 n·H_n ≈ n(ln n + γ)。

示例 3：随机排列中的记录数

在一个随机排列中，"记录"是指比前面所有元素都大的元素。n 个元素的随机排列中，记录的期望数量是 H_n。

三、程序员的视角

3.1 在算法分析中的应用

求和技术在算法分析中无处不在。以下是几个典型场景：

算术级数求和

冒泡排序的比较次数：

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

几何级数求和

某些分治算法的工作量：

$$\sum_{i=0}^{\log n} \frac{n}{2^i} = n \sum_{i=0}^{\log n} \left(\frac{1}{2}\right)^i < 2n = O(n)$$

调和级数

如前所述，快速排序、优惠券收集等问题都涉及调和数。

双重求和

某些矩阵算法的复杂度：

$$\sum_{i=1}^{n} \sum_{j=1}^{i} O(1) = \sum_{i=1}^{n} O(i) = O(n^2)$$

3.2 常见陷阱与误区

陷阱 1：忽略求和边界

$$\sum_{k=1}^{n} k \neq \sum_{k=0}^{n} k$$

前者是 n(n+1)/2，后者是 n(n+1)/2 + 0 = n(n+1)/2（碰巧相同，但对于其他被加项可能不同）。

避免方法：仔细检查求和的上下限。

陷阱 2：错误地交换无穷级数的求和顺序

对于有限求和，交换顺序总是合法的；但对于无穷级数，交换顺序可能改变结果。

示例：Grandi 级数 1 - 1 + 1 - 1 + ... 可以"证明"等于 0、1 或 1/2，取决于如何分组。

避免方法：对于无穷级数，确保绝对收敛后再交换顺序。

陷阱 3：混淆 ∑ k 和 ∑ k²

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

两者相差一个因子 (2n+1)/3。

避免方法：记住常用公式，或在不确定时用小规模案例验证。

陷阱 4：忽视数值精度

在计算机中计算浮点数求和时，累积误差可能显著。

示例：计算 H_{10⁶} 时，从小到大相加和从大到小相加可能得到不同的结果。

避免方法：使用 Kahan 求和算法或其他高精度技术。

3.3 与其他层级的联系

求和与计算机科学的多个领域紧密相关：

算法分析：时间复杂度的精确计算
概率论：期望值的定义本身就是求和
数值分析：数值积分、级数展开
信号处理：离散傅里叶变换涉及复数求和
机器学习：损失函数的计算、梯度下降

四、代码实战

4.1 示例一：求和计算器

实现一个通用的求和计算器，支持多种求和模式：

python

class SummationCalculator:
    """求和计算器"""
    
    @staticmethod
    def arithmetic_sum(n):
        """等差数列求和: 1 + 2 + ... + n"""
        return n * (n + 1) // 2
    
    @staticmethod
    def geometric_sum(x, n):
        """等比数列求和: 1 + x + x^2 + ... + x^n"""
        if x == 1:
            return n + 1
        return (x ** (n + 1) - 1) // (x - 1)
    
    @staticmethod
    def sum_of_squares(n):
        """平方和: 1^2 + 2^2 + ... + n^2"""
        return n * (n + 1) * (2 * n + 1) // 6
    
    @staticmethod
    def sum_of_cubes(n):
        """立方和: 1^3 + 2^3 + ... + n^3"""
        s = n * (n + 1) // 2
        return s * s
    
    @staticmethod
    def harmonic_number(n):
        """调和数: H_n = 1 + 1/2 + 1/3 + ... + 1/n"""
        return sum(1.0 / k for k in range(1, n + 1))
    
    @staticmethod
    def weighted_power_sum(x, n):
        """加权幂求和: S = sum(k * x^k, k=0..n)"""
        if x == 1:
            return n * (n + 1) // 2
        # 使用公式: S = (x - (n+1)*x^(n+1) + n*x^(n+2)) / (1-x)^2
        numerator = x - (n + 1) * x ** (n + 1) + n * x ** (n + 2)
        denominator = (1 - x) ** 2
        return numerator / denominator
    
    @staticmethod
    def double_sum_product(n):
        """双重求积: sum(sum(i*j, j=1..n), i=1..n)"""
        s = n * (n + 1) // 2
        return s * s

# 测试
calc = SummationCalculator()
n = 10

print(f"等差数列求和 (n={n}): {calc.arithmetic_sum(n)}")
print(f"等比数列求和 (x=2, n={n}): {calc.geometric_sum(2, n)}")
print(f"平方和 (n={n}): {calc.sum_of_squares(n)}")
print(f"立方和 (n={n}): {calc.sum_of_cubes(n)}")
print(f"调和数 (n={n}): {calc.harmonic_number(n):.6f}")
print(f"加权幂求和 (x=2, n={n}): {calc.weighted_power_sum(2, n):.0f}")
print(f"双重求积 (n={n}): {calc.double_sum_product(n)}")

# 验证
print("\n验证:")
print(f"  2^{n+1} - 1 = {2**(n+1) - 1} (等比数列)")
print(f"  (n(n+1)/2)^2 = {(n*(n+1)//2)**2} (立方和)")

4.2 示例二：扰动法验证

验证扰动法推导的公式：

python

def verify_perturbation():
    """验证扰动法推导的公式"""
    
    print("验证: sum(k * 2^k, k=0..n) = (n-1) * 2^(n+1) + 2")
    print("-" * 60)
    
    for n in range(1, 15):
        # 直接计算
        direct_sum = sum(k * 2**k for k in range(n + 1))
        
        # 公式计算
        formula_result = (n - 1) * 2**(n + 1) + 2
        
        match = "✓" if direct_sum == formula_result else "✗"
        print(f"n={n:2d}: 直接={direct_sum:8d}, 公式={formula_result:8d} {match}")

verify_perturbation()

print("\n验证: sum(k * x^k, k=0..n) 的一般公式")
print("-" * 60)

def general_weighted_sum(x, n):
    """一般加权幂求和"""
    if abs(x - 1) < 1e-10:
        return n * (n + 1) / 2
    numerator = x - (n + 1) * x**(n + 1) + n * x**(n + 2)
    denominator = (1 - x) ** 2
    return numerator / denominator

for x in [0.5, 1.5, 2.0, 3.0]:
    print(f"\nx = {x}:")
    for n in [5, 10, 15]:
        direct = sum(k * x**k for k in range(n + 1))
        formula = general_weighted_sum(x, n)
        error = abs(direct - formula)
        print(f"  n={n:2d}: 直接={direct:.4f}, 公式={formula:.4f}, 误差={error:.2e}")

4.3 示例三：数值精度实验

比较不同求和方法的数值精度：

python

import math

def compute_harmonic_direct(n):
    """直接计算调和数"""
    return sum(1.0 / k for k in range(1, n + 1))

def compute_harmonic_reversed(n):
    """反向计算调和数（从大到小）"""
    return sum(1.0 / k for k in range(n, 0, -1))

def compute_harmonic_kahan(n):
    """使用 Kahan 求和算法"""
    total = 0.0
    compensation = 0.0
    for k in range(1, n + 1):
        y = 1.0 / k - compensation
        t = total + y
        compensation = (t - total) - y
        total = t
    return total

def harmonic_approximation(n):
    """渐近近似"""
    gamma = 0.57721566490153286060651209008240243104215933593992
    return math.log(n) + gamma + 1.0 / (2 * n) - 1.0 / (12 * n**2)

# 实验
print("调和数计算的数值精度实验")
print("=" * 70)
print(f"{'n':>10} {'直接':>18} {'反向':>18} {'Kahan':>18} {'近似':>18}")
print("-" * 70)

for n in [100, 1000, 10000, 100000, 1000000]:
    h_direct = compute_harmonic_direct(n)
    h_reversed = compute_harmonic_reversed(n)
    h_kahan = compute_harmonic_kahan(n)
    h_approx = harmonic_approximation(n)
    
    print(f"{n:>10d} {h_direct:>18.12f} {h_reversed:>18.12f} {h_kahan:>18.12f} {h_approx:>18.12f}")

# 比较差异
print("\n与 Kahan 方法的差异:")
print(f"{'n':>10} {'直接-Kahan':>18} {'反向-Kahan':>18} {'近似-Kahan':>18}")
print("-" * 70)

for n in [10000, 100000, 1000000]:
    h_direct = compute_harmonic_direct(n)
    h_reversed = compute_harmonic_reversed(n)
    h_kahan = compute_harmonic_kahan(n)
    h_approx = harmonic_approximation(n)
    
    diff_direct = abs(h_direct - h_kahan)
    diff_reversed = abs(h_reversed - h_kahan)
    diff_approx = abs(h_approx - h_kahan)
    
    print(f"{n:>10d} {diff_direct:>18.2e} {diff_reversed:>18.2e} {diff_approx:>18.2e}")

五、深入思考

5.1 历史背景

求和的历史可以追溯到古代文明。巴比伦人已经知道等差数列求和公式，而高斯在童年时期就发现了 1 + 2 + ... + n = n(n+1)/2 的巧妙方法。

雅各布·伯努利（Jacob Bernoulli, 1654-1705）在《猜度术》（Ars Conjectandi, 1713）中系统地研究了幂和公式，引入了伯努利数。莱昂哈德·欧拉（Leonhard Euler, 1707-1783）进一步发展了求和技术，建立了有限微积分的框架。

罗纳德·葛立恒（Ronald Graham）、唐纳德·克努特（Donald Knuth）和奥伦·帕塔许尼克（Oren Patashnik）在《具体数学》中将求和技术系统化，使其成为计算机科学家的标准工具。

5.2 未解决的问题

尽管求和理论已经非常成熟，但仍有一些开放问题：

特殊求和的闭合形式：某些求和（如涉及素数的求和）是否存在的闭合形式仍是未知数

多重求和的高效计算：对于高维多重求和，是否有比逐项计算更高效的算法？

符号求和的自动化：虽然 Gosper 算法和 Zeilberger 算法可以处理许多超几何求和，但完全自动化的符号求和仍然是研究热点

5.3 延伸阅读

《具体数学》第 2 章 - Graham, Knuth, Patashnik

本章内容的详细源头，包含更多技巧和练习。

《Concrete Mathematics: A Foundation for Computer Science》

英文原版，有更丰富的注释和历史背景。

"A = B" - Petkovšek, Wilf, Zeilberger

介绍超几何求和的自动化方法，展示了计算机如何"发现"求和公式。

《算法导论》附录 A - Cormen et al.

算法分析中常用的求和公式和技巧。

"The Art of Computer Programming, Vol. 1" 第 1.2.10 节 - Donald Knuth

Knuth 对求和技术的深入讨论。

六、实验笔记

实验一：求和方法的性能比较

目标：比较不同求和方法的计算效率和数值精度。

步骤：

实现以下求和方法：

- 直接逐项求和

- 使用闭合公式

- 使用扰动法推导的公式

- 使用有限微积分方法

对于每种方法，测量计算 H_n、∑k²、∑k³ 的时间

比较数值精度（与高精度参考值对比）

分析时间复杂度和空间复杂度

预期结果：

闭合公式最快（O(1)），但仅适用于特定求和
直接求和最慢（O(n)），但最通用
Kahan 求和在精度上优于直接求和

思考题：

在什么情况下应该优先使用闭合公式？
如何处理无法求得闭合形式的求和？

实验二：多重求和的可视化

目标：可视化双重求和的过程，理解交换求和顺序的等价性。

步骤：

选择一个 n × n 的矩阵 A，其中 A[i][j] = i × j

绘制矩阵，用颜色深浅表示元素大小

演示先按行求和再按列求和的过程

演示先按列求和再按行求和的过程

验证两种方法的结果相同

代码框架：

python

import numpy as np
import matplotlib.pyplot as plt

def visualize_double_sum(n):
    """可视化双重求和"""
    # 创建矩阵
    A = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            A[i][j] = (i + 1) * (j + 1)
    
    # 绘制热力图
    plt.figure(figsize=(10, 8))
    plt.imshow(A, cmap='viridis')
    plt.colorbar(label='Value')
    plt.title(f'Matrix A[i][j] = (i+1)(j+1), n={n}')
    plt.xlabel('j')
    plt.ylabel('i')
    plt.savefig('double_sum_matrix.png', dpi=150, bbox_inches='tight')
    plt.show()
    
    # 计算两种顺序的求和
    sum_row_first = sum(sum(A[i][j] for j in range(n)) for i in range(n))
    sum_col_first = sum(sum(A[i][j] for i in range(n)) for j in range(n))
    
    print(f"先按行求和: {sum_row_first}")
    print(f"先按列求和: {sum_col_first}")
    print(f"差异: {abs(sum_row_first - sum_col_first)}")

visualize_double_sum(10)

思考题：

对于无穷矩阵，交换求和顺序是否仍然合法？
如何可视化三重求和？

七、本章小结

本章系统介绍了求和的各种技巧和应用。

关键公式：

等差数列：$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$
等比数列：$\sum_{k=0}^{n} x^k = \frac{x^{n+1}-1}{x-1}$
平方和：$\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$
立方和：$\sum_{k=1}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2$
加权幂：$\sum_{k=0}^{n} k \cdot x^k = \frac{x-(n+1)x^{n+1}+nx^{n+2}}{(1-x)^2}$

核心技术：

扰动法：通过 S + a_{n+1} 或 cS 的变换求解复杂求和

交换求和顺序：简化多重求和的有力工具

有限微积分：将连续微积分的概念推广到离散域

下降幂：简化差分运算的特殊记号

重要概念：

调和数 H_n 没有闭合形式，但有渐近近似 H_n ≈ ln n + γ
有限求和可以任意交换顺序，无穷级数需要谨慎
求和是算法分析的基础工具，必须熟练掌握

八、习题

基础题

习题 2.1：计算 $\sum_{k=1}^{100} k$ 和 $\sum_{k=1}^{100} k^2$。

习题 2.2：用扰动法推导 $\sum_{k=0}^{n} k \cdot 3^k$ 的闭合形式。

习题 2.3：计算双重求和 $\sum_{i=1}^{5} \sum_{j=1}^{5} (i+j)$。

习题 2.4：证明 $\sum_{k=1}^{n} k^3 = (\sum_{k=1}^{n} k)^2$。

进阶题

习题 2.5：[ME] 使用有限微积分计算 $\sum_{k=0}^{n-1} k^{\underline{3}}$，并将结果转换为普通幂的形式。

习题 2.6：[ME] 计算 $\sum_{1 \leq i < j \leq n} ij$。提示：考虑 $(\sum_{k=1}^{n} k)^2$ 的展开。

习题 2.7：证明调和数的递推恒等式：$\sum_{k=1}^{n} \frac{H_k}{k} = \frac{H_n^2 + H_n^{(2)}}{2}$，其中 $H_n^{(2)} = \sum_{k=1}^{n} \frac{1}{k^2}$。

挑战题

习题 2.8：[HM25] 推导 $\sum_{k=0}^{n} k^2 \cdot x^k$ 的闭合形式。

习题 2.9：[HM30] 考虑求和 $S_n = \sum_{k=1}^{n} \frac{1}{k(k+1)}$。

(a) 使用部分分式分解求闭合形式
(b) 计算 $\lim_{n \to \infty} S_n$
(c) 推广到 $\sum_{k=1}^{n} \frac{1}{k(k+1)(k+2)}$

习题 2.10：[HM40] 研究 Gosper 算法：

(a) 解释 Gosper 算法的基本思想
(b) 用 Gosper 算法计算 $\sum_{k} \binom{n}{k}$
(c) 为什么 Gosper 算法不能处理所有超几何求和？

本章完

第2章 求和 (Summation)

一、导读

2.1 本章学习目标

2.2 为什么本章如此重要

2.3 核心问题引导

二、核心概念详解

2.1 求和符号与基本规则

求和符号的定义

基本运算规则

常见求和公式

2.2 扰动法：求和的巧妙变换

基本原理

示例 1：等比数列求和

示例 2：求 ∑ k·2ᵏ

示例 3：求 ∑ k·xᵏ（一般情况）

扰动法的通用策略

2.3 多重求和与交换顺序

双重求和的定义

交换求和顺序

示例 1：计算 ∑∑ ij

示例 2：三角形区域的求和

示例 3：算法分析中的应用

2.4 有限微积分：离散的微积分

差分算子

下降幂

普通幂到下降幂的转换

不定和与定和

分部求和

2.5 调和数：没有闭合形式的求和

定义

基本性质

渐近近似

在算法分析中的应用

三、程序员的视角

3.1 在算法分析中的应用

算术级数求和

几何级数求和

调和级数

双重求和

3.2 常见陷阱与误区

陷阱 1：忽略求和边界

陷阱 2：错误地交换无穷级数的求和顺序

陷阱 3：混淆 ∑ k 和 ∑ k²

陷阱 4：忽视数值精度

3.3 与其他层级的联系

四、代码实战

4.1 示例一：求和计算器

4.2 示例二：扰动法验证

4.3 示例三：数值精度实验

五、深入思考

5.1 历史背景

5.2 未解决的问题

5.3 延伸阅读

六、实验笔记

实验一：求和方法的性能比较

实验二：多重求和的可视化

七、本章小结

八、习题

基础题

进阶题

挑战题

第2章求和 (Summation)