四卷总复习：从公式到随机算法

按前四卷40个原始章节复习数列与生成函数、费马大定理、哥德尔不完备性和随机算法，并用表示、构造、条件与证明证据建立跨卷连接。

学习目标

能解释前四卷各自的问题链，并把一个公式放回对象、前提、动作与结论四格中
能推导生成函数、调和数或随机快速排序中的一个关键关系，并指出每一步使用的条件
能比较表示、构造和概率保证三种跨卷方法，说明它们何时能迁移、何时会误导
能回答：给定一个新问题，我会选择哪种表示、保留哪条前提、保存什么证据来证明结论可复查？

从一张“复习地图”开始

复习四卷时最容易出现一种错觉：把页面数量当成原书章节数量，或把公式背诵当成理解。这个总复习解决的是“怎样从一个具体对象走到可检查的结论”，而不是再列一遍标题。没有这条路径，读者会把生成函数、无穷递降、矩阵和随机算法看成互不相干的技巧。

先预测：如果只保留一个公式的最后一行，删除对象、适用条件和中间证据，另一位读者能否复算它？不能。下面的复习路线把四卷压缩成四条问题链，再用三个小实验检查迁移是否真的发生。

四卷各有连续问题链：从表示与结构，到证明方法、形式系统边界，再到概率化算法保证。

四卷的对象—动作—结论

第1卷：用表示把局部规律变成结构

第1卷从有限样例出发，先问“这个规则能否被稳定地表示”，再选择合适的。以斐波那契数列为例，设 $F_0=0,F_1=1$ ，递推是

F_{n+2}=F_{n+1}+F_n.

这个式子在说：下一个数由前两个状态共同决定；它还没有告诉我们如何快速计算很大的 $n$ 。把数列编码成 $F(x)=\sum_{n\ge 0}F_nx^n$ ，移项后得到

F(x)=\frac{x}{1-x-x^2}.

这个式子在说：递推关系被转成了一个代数对象，系数提取可以把结论翻回数列。若两个对象由左右两部分拼接，系数乘法进一步给出卷积：

[x^n]A(x)B(x)=\sum_{k=0}^{n}a_kb_{n-k}.

这个式子在说：总大小为 $n$ 的对象，要枚举左半部分大小 $k$ ，再配上右半部分大小 $n-k$ 。这里必须区分形式幂级数与解析函数：前者关注系数恒等式，后者还要说明收敛范围。

调和数把第1卷的表示工具连接到第4卷的复杂度分析：

H_n=\sum_{k=1}^{n}\frac{1}{k}=\Theta(\log n).

这个式子在说：增长速度与对数同阶，而不是逐项等于某个对数函数。用积分比较时，必须先声明 $n\ge 1$ 和正项条件。

第2卷：用构造把定义与引理串成长证明

第2卷常从一个“不存在”或“不能同时满足”的命题开始。先写对象的定义，再找一个能制造矛盾的构造。勾股数、互质、模运算和无穷递降都服务于这条链，但它们的证据不能互相替代。

在无穷递降中，先假设存在一个反例，再按良序性选出某个最小量，构造出更小的同类反例。真正需要的是“仍属于同一类”和“严格变小”两份证据；只写“可以继续下降”不算完成证明。

费马大定理的陈述是：当 $n$ 大于 2 时， $x^n+y^n=z^n$ 没有正整数解。前九章提供整数结构和证明方法的阶梯，但本章不把这些工具冒称为怀尔斯证明的完整替代。复习时应把“本章能推出什么”和“本章明确没有推出什么”同时写下。

第3卷：用形式语言标出证明边界

第3卷训练的是把“显然接近”改写成可检查的量词顺序。极限的定义写成

\forall\varepsilon>0\;\exists\delta>0\;\forall x, \quad 0<|x-a|<\delta\Longrightarrow |f(x)-L|<\varepsilon.

这个式子在说：先给定误差 $\varepsilon$ ，再找到可以依赖它的 $\delta$ ，最后对所有满足邻域条件的 $x$ 保证输出误差。交换量词会改变命题，不是排版差异。

对角论证、形式系统和哥德尔不完备性继续追问“一个系统能否在自身内部完整描述并证明所有相关事实”。结论不是“数学不可信”，而是：给定足够表达能力、一致性和有效公理化等前提，系统的可证明范围存在严格边界。必须同时说明目标集合、假设列表和逐位不同的构造。

第4卷：用概率给出可量化的算法保证

第4卷把“随机”从感觉改成概率空间、随机变量和失败事件。分析随机算法时，先写随机性发生在输入模型还是算法内部，再写成功率、重复次数和确定性验证的边界。

随机快速排序固定任意输入，只在每次划分时随机选择枢纽。对排名 $j<k$ 的元素定义指示器 $X_{j,k}$ ，表示它们是否被比较，则总比较次数为

X=\sum_{j<k}X_{j,k}, \qquad \mathbb E[X]=\sum_{j<k}\mathbb E[X_{j,k}].

这个式子在说：期望的线性法则不要求这些比较事件彼此独立。最先成为枢纽的元素若是区间两端之一， $j,k$ 才会比较，因此

\Pr(X_{j,k}=1)=\frac{2}{k-j+1}, \qquad \mathbb E[C_n]=2(n+1)H_n-4n=\Theta(n\log n).

这个式子在说：概率解释、求和恒等式和调和数界共同支撑复杂度结论；只背最后的 $\Theta$ 不能说明随机源在哪里。

三次跨卷复习实验

下面的 Stepper 是本章的主复习 Demo。每一步都保留一张结构图：先把对象换成表示，再把证明写成证据链，最后把随机性写成保证。改变一格后，要说明哪条结论失效以及为什么。

分步1 / 3

1. 表示：把对象换成可运算的形式

猜一猜：把“数列”改写成生成函数或状态向量后，哪些运算会变得更容易？请先说出原对象、编码方式和回译方式，再观察图中的三段箭头。

跨卷迁移：公式不能脱离条件

表示选择

生成函数适合把卷积变成乘法，矩阵适合把重复的线性状态变成矩阵幂，形式编码适合把语法和证明变成可操作对象。三者共享“换一种表示以暴露结构”，但输入对象和可执行的运算不同。迁移时先写出回译步骤，防止把编码误当成原对象。

构造方法

卷积构造一个整体对象，无穷递降构造更小反例，对角论证构造列表之外的对象。它们都在“造东西”，但证明目标分别是计数、矛盾和不可列。若不能指出构造对象属于哪一个集合，证明就缺了关键桥梁。

条件审计

每条公式都用四格记录：对象是什么，前提是什么，动作如何进行，结论能推出什么。例如 $\mathbb E[X+Y]=\mathbb E[X]+\mathbb E[Y]$ 不要求独立；方差直接相加通常还要处理协方差。描述增长级别，不是对每个输入给出相同的精确值。

四卷目录边界与复习证据

权威范围是前四卷各 10 个原始章节，共 40 章；学习地图、专题导读和本总复习属于编辑页，不增加原始章节数。目录核对以作者页面的卷表为准：《数学女孩》系列前四卷目录。技术事实仍需结合本章公式、图示和练习独立复核，不能仅凭目录标题推导结论。

卷	主问题	复习时必须留下的证据
第1卷	规律如何变成结构	一个递推、一个表示和一次回译
第2卷	反例如何被构造并排除	定义、最小量、严格变小和矛盾
第3卷	证明能力的边界在哪里	量词顺序、系统前提和对角构造
第4卷	随机性如何变成保证	概率空间、随机变量、失败事件和重复策略

本章回顾

四卷共同训练“对象—表示或构造—条件—可检查结论”的往返。
第1卷以递推、生成函数和卷积发现结构；第2卷以构造组织长证明。
第3卷用量词和形式系统标出边界；第4卷用概率和期望量化不确定性。
40 个原始章节与编辑页必须分开统计，不能用页面数量替代目录范围。
复习完成的标志是能独立推导、指出反例，并保存别人可以复查的证据。

练习

问题 1：表示回译。 从 $F_{n+2}=F_{n+1}+F_n$ 出发，写出生成函数表达式，并说明系数提取怎样回到原数列。

问题 2：证明反例。 为什么无穷递降必须同时证明“仍是同类反例”和“严格变小”？请给出缺一项时的失败方式。

问题 3：概率边界。 随机快速排序的随机性放在哪里？为什么平均随机输入不能直接替代随机枢纽选择？

问题 4：改 Demo 代码。 在 Stepper 的第三步增加一个“把输入模型误写成算法随机”的错误开关，并写出一条会使结论分叉的测试。

名词解释

本章出现的专业名词，用大白话再讲一遍。

表示: 给同一个数学对象换一套更方便计算或证明的记录方式，例如把数列写成生成函数。
生成函数: 把数列各项放在幂级数系数里的编码；做乘法时会自然产生卷积。
无穷递降: 假设有一个最小反例，再造出更小的同类反例，用最小性制造矛盾。
对角论证: 逐位改变假设列表中的对象，构造一个不可能出现在完整列表里的新对象。
渐近阶: 只描述规模变大时的增长速度等级，不承诺每个具体输入都有同一个精确值。