第一部分 · 数从哪里来

计数与证明：从"数得清"到"为什么一定对"

数数能验证"3 + 5 = 8"这一个例子，但只要你想说"对所有自然数都成立"，一个一个数就永远数不完。本课要造出的工具，能用有限的几句话，一次性锁死关于无穷多情形的断言。

自然数：数数其实只有一个动作

把数数拆到最细，你会发现它只靠一件事：每个数都有"下一个"。从 1 走到它的后继 2，从 2 走到 3……这个"加一往后走"的动作叫后继。整套自然数

ℕ = {1, 2, 3, 4, …}　（读作：自然数集合，从 1 一直往后）

就是"一个起点 + 反复取后继"生出来的。它很慷慨：任意两个自然数相加、相乘，结果还是自然数——我们说 ℕ 对加法和乘法封闭（算完不会跑出去）。这种封闭让人安心，仿佛自然数自成一个完整的小世界。第 02 课我们会看到这份安心很快被减法打破，但现在先停在这个安稳的世界里，问一个更尖锐的问题。

验证一万个例子，也不是证明

看下面这个式子，它把前 n 个奇数加起来：

1 = 1，　1 + 3 = 4，　1 + 3 + 5 = 9，　1 + 3 + 5 + 7 = 16

结果是 1, 4, 9, 16——全是完全平方数！看起来规律是"前 n 个奇数之和 = n²（读作 n 的平方）"。你可以兴致勃勃地往下验证：n = 5 得 25，n = 100 得 10000，统统对得上。

但这里有一道深渊。哪怕你验证到 n = 一万亿，你检验过的也只是有限多个例子；而"对所有 n 成立"说的是无穷多个。有限永远盖不住无穷——下一个还没验的 n，凭什么保证它不破例？数学史上不乏"前面几十项都对、忽然栽掉"的例子。所以：

归纳法：让多米诺骨牌替你数到底

想象把自然数 1, 2, 3, … 摆成一排无穷长的多米诺骨牌，第 n 张代表"命题对 n 成立"，记作 P(n)（读作"关于 n 的那句话"）。你想让所有骨牌都倒下，但骨牌有无穷多张，你不可能一张张去推。怎么办？只要保证两件事：

• 基础步：P(1) 成立。——你亲手推倒第 1 张。
• 递推步：只要 P(k) 成立，就能推出 P(k+1) 也成立。——每张倒下时，一定砸倒紧挨着的下一张。

这两件事合起来会发生什么？第 1 张倒（基础步）；它砸倒第 2 张（递推步用在 k=1）；第 2 张砸倒第 3 张（k=2）……这股"倒势"会自动、不可阻挡地传遍整排无穷骨牌。你只说了两句话，却让无穷张牌全倒了。这就是数学归纳法。

[ P(1) ]　且　[ 对每个 k，P(k) ⇒ P(k+1) ]　⇒　[ 对所有自然数 n，P(n) 成立 ]

注意它的精妙：递推步并不要求你证明任何具体的一张牌，只要求你证明"任意一张倒了，下一张必倒"这条传递规则。一条规则 + 一个起点，就把无穷管住了。下面这个小实验，让你亲手拨动这两个开关，看无穷怎么被锁住或漏掉。

试金石：高斯的求和公式

有个传说：小学老师罚高斯把 1 加到 100，想让他安静一节课，结果他几秒钟就报出 5050。他看穿的，正是这个对所有 n 都成立的公式：

1 + 2 + 3 + … + n = n(n+1)/2　（读作：从 1 加到 n，等于 n 乘以 n+1 再除以 2）

这是一句关于无穷多个 n 的断言，正好用归纳法来锁。把 P(n) 设成"上面这条等式对 n 成立"：

• 基础步（n = 1）：左边 = 1，右边 = 1·2/2 = 1。相等，P(1) 成立。第 1 张牌推倒。
• 递推步：假设 P(k) 成立，即 1+2+…+k = k(k+1)/2。现在看 P(k+1)，只要在两边加上下一项 (k+1)：

  1+2+…+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2

  而这恰好就是把公式里的 n 换成 k+1 的样子。于是"P(k) 倒下"必然"砸倒 P(k+1)"。

两步齐全，骨牌倒势启动——公式对所有自然数 n 成立。注意递推步里那个不起眼的假设"假设 P(k) 成立"：它不是偷换结论，而是"上一张牌已经倒了"这个既成事实。我们用它去砸倒下一张，再不回头去验它。

反证法：证明"永远不会用完"的素数

归纳法擅长"沿着 1, 2, 3 往前推"。但有些关于无穷的断言不是这种形状，比如那句两千多年前就被欧几里得锁死的话：素数有无穷多个（素数 = 只能被 1 和自身整除的数：2, 3, 5, 7, 11, …）。这里没有"第 n 个"可推，欧几里得用了另一件证明利器——反证法：先假设结论是假的，再把这个假设逼到自相矛盾，从而断定它只能是真的。

• 反设：假设素数只有有限多个，把它们全部列出来：p₁, p₂, …, pₙ（读作 p 下标 1 到 p 下标 n，号称是所有素数）。
• 造一个怪数：把它们全部相乘，再加 1：

  N = (p₁ × p₂ × … × pₙ) + 1

• 逼出矛盾：这个 N 被名单上任何一个 pᵢ 去除，都余 1（因为乘积部分整除得尽，多出来的那个 1 除不掉）。所以名单上没有一个素数能整除 N。可是任何大于 1 的整数，要么自己是素数，要么能被某个素数整除——于是 N 要么本身是个新素数，要么含有一个名单外的质因子。无论哪种，都冒出了一个不在"全部素数"名单里的素数。
• 结论：这和"名单已经列全了所有素数"直接矛盾。错只能错在最初那个反设上。所以素数不可能有限多——它有无穷多个。

请细品这件事的分量：欧几里得既没有、也不可能把无穷多个素数一个个写出来，却用不到一段话，确凿无疑地断定了关于无穷的一桩事实。这正是证明的魔力——也是它和"数数"的本质分野。

常见误解

• "归纳法是循环论证——它用结论来证结论。"
  不是。递推步假设的是 P(k)（上一张牌已倒这个局部事实），证明的是 P(k+1)。我们从不假设"对所有 n 成立"那个总结论；总结论是骨牌倒势跑出来的，不是预设进去的。
• "验证了好几个例子，就算证明了。"
  例子再多也是有限的，盖不住无穷。验证只能证伪、不能证实一个普遍断言。历史上不乏"前几十项都对、忽然破例"的式子——这正是必须用证明的理由。
• "素数越往后越稀疏，迟早会用完。"
  稀疏（变稀）和有限（用完）是两码事。素数确实越来越稀，间隔越来越大，但欧几里得的反证法保证：无论你走多远，前方永远还有素数。稀疏不等于枯竭。