证明方法全集 — 从直接证明到无穷递降

证明方法全集 — 从直接证明到无穷递降 (A Compendium of Proof Methods)

这份讲义要教会你什么

这是一份证明方法的总纲。它把你最近这串对话里出现的全部 21 种证明手法收进来，不是简单罗列，而是按”逻辑灵魂”归成七大家族，让你看清它们之间的血缘关系。读完之后你应该能:

• 拿到一道证明题时，先判断它属于哪一类，再调出对应的方法模板;
• 对每一种方法，能说出它的核心思想、逻辑骨架、一个完整例子、什么时候该用;
• 理解一个贯穿全篇的元洞察:几乎所有”硬”证明，本质都是在利用某个量的”有限性”或”良序性”;
• 把这些方法和你的去向(CMU 15-151 / 15-251、竞赛、数论、密码学)对应起来。

覆盖范围:正向构造派、反向否定派、命题形状派、良序归纳大家族、计数派、对角线、数论专精(Vieta 跳跃 / p-adic 赋值)。

怎么用这份讲义

• 标 ★ 的是必须吃透的主力方法(竞赛和 15-151 高频)。
• 标 ➕ 的是进阶/专精(超出基础课，但对你的竞赛和未来数论课有价值)。
• 每个方法都配了 > [!example] 完整例子——别只看结论，要看**“为什么这一步能这么走”**。
• > [!question] 是自测题，答案是可折叠 callout(在 Obsidian 里点开)，请先自己挑方法、自己写，再看解答。
• 读的时候在脑子里装一个问题:“这个方法的’灵魂’是什么？它靠什么制造结论或矛盾？“

---

0. 先建立心态:证明到底在干什么

一句话:证明就是把”我相信它对”升级成”任何人按逻辑都无法反驳”。

数学和其它学科最大的不同，在于它的断言是永久成立、无可辩驳的。而把”直觉上对”变成”逻辑上铁”的那座桥，就是证明。学会写证明，本质上是学会一种极度诚实的思维方式:每一步都要有依据，不许偷偷塞进”显然”。

这份讲义最核心的元洞察(请先记住)

表面上这 21 种方法五花八门，但它们的”灵魂”其实只有几种。其中最大的一族——良序归纳大家族——共享同一个底层原理:

”${\mathbb{Z}}^{+}$ 的每个非空子集都有最小元。“(良序原理 Well-Ordering Principle)

归纳法正着用它(从小往大造)，无穷递降反着用它(从大往小拆)，最小反例静态地用它，极值原理在几何/组合里用它。一旦你养成”这道题里什么量是良序的？“的条件反射，你就握住了一整族方法的总开关。

0.1 七大家族地图 ★

先把全景看一遍。下面每一行是一个”家族”，共享同一种逻辑灵魂:

家族	灵魂(一句话)	包含的方法	攻击什么形状的命题
一 · 正向构造	顺着定义往前推	直接证明、分情况、构造性存在	”如果…那么…”、“存在…”
二 · 反向否定	从”假设它不成立”借力	逆否、反证、非构造性存在	难以正面下手的命题
三 · 命题形状	拆解命题的逻辑结构	双向(iff)、唯一性	”当且仅当”、“唯一”
四 · 良序归纳 ★	利用某个量的良序性	弱/强/结构归纳、良序原理、最小反例、无穷递降、极值原理	”对所有 $n$…”、“无解”、“必存在”
五 · 计数派	用”数数”和有限性逼出结论	鸽巢、双重计数、容斥	”必有两个…”、计数等式
六 · 对角线	造一个”自我否定”的对象	对角线论证	”不可数”、“不可判定”
七 · 数论专精 ➕	给四/五族装上数论引擎	Vieta 跳跃、p-adic 赋值	丢番图方程、整除/平方判定

怎么读这张表

第四族是整张表的心脏——你那道 $a^2+2b^2=5c^2$ 用的”无穷递降”就住在这里，而且它和”归纳法”是同一个原理的两面。我们会在第 4 节重点展开。其余六族围绕它展开。

---

第一族 · 正向构造 (Forward / Direct)

这一族的灵魂

顺着已知条件，沿着定义和逻辑，一步一步往前推到结论。 不绕弯、不假设反面、不偷换。这是所有证明的”默认模式”，也是其它一切方法的底座。

1.1 直接证明 (Direct Proof) ★

核心思想:要证 $P\Rightarrow Q$，就假设 $P$ 成立，然后用定义、已知定理、代数运算，直接推出 $Q$。

逻辑骨架:

$$\text{假设 }P⟶\text{(一连串有依据的推导)}⟶Q.$$

例:奇数的平方模 8 余 1

命题:若 $n$ 是奇数，则 $n^2\equiv 1(\mathrm{mod}8)$。
证明:$n$ 为奇数，写成 $n=2k+1$（$k\in \mathbb{Z}$）。直接平方:
$n^2=(2k+1{)}^2=4k^2+4k+1=4k(k+1)+1.$
关键观察:$k(k+1)$ 是两个连续整数之积，必为偶数，记 $k(k+1)=2m$。代回:
$n^2=4\cdot 2m+1=8m+1\equiv 1(\mathrm{mod}8).■$

为什么这一步能走:“连续两整数必有一个偶数”是直接证明里最常用的小引理之一。整个过程没有任何假设反面，就是把定义($n$ 奇)代进去硬算。

什么时候用直接证明

永远先试它。 只有当”正面推”明显很别扭(比如结论是”不存在”、“无理”、“无限多”)时，才考虑换成反向或归纳。

1.2 分情况讨论 (Proof by Cases / Exhaustion) ★

核心思想:把论域切成若干互不遗漏的情况，每种情况单独证明。只要每种情况都成立，且情况穷尽了所有可能，命题就成立。

逻辑骨架:

$$(\text{情况 }1\Rightarrow Q)\wedge (\text{情况 }2\Rightarrow Q)\wedge \cdots \wedge (\text{所有情况已穷尽})⟹Q.$$

例:整数的平方模 4 只能余 0 或 1

命题:对任意整数 $n$，$n^2\equiv 0\text{ 或 }1(\mathrm{mod}4)$。
证明:按 $n$ 的奇偶分两种情况(已穷尽所有整数)。

• 情况一($n$ 偶):$n=2k$，则 $n^2=4k^2\equiv 0(\mathrm{mod}4)$。
• 情况二($n$ 奇):$n=2k+1$，则 $n^2=4k^2+4k+1\equiv 1(\mathrm{mod}4)$。

两种情况覆盖了全部整数，故 $n^2\mathrm{mod}4\in \{0,1\}$。$■$

分情况最容易犯的错

漏掉情况(没穷尽)，或者情况重叠还不自知。写完一定要自问:“我的情况加起来真的等于全集吗？” 比如分”正/负”漏了零，分”奇/偶”对实数无效。

1.3 构造性存在证明 (Constructive Existence) ★

核心思想:要证”存在满足某性质的对象”，最干脆的办法就是直接把它造出来(或给出造它的方法)，并验证它确实满足要求。

逻辑骨架:

$$\text{给出具体对象 }{x}_0⟶\text{验证 }{x}_0\text{ 满足性质 }P⟹\exists x:P(x).$$

例:存在任意长的"连续合数串"

命题:对任意正整数 $N$，存在 $N$ 个连续的合数(中间夹不进素数)。
证明(构造):考虑下面这 $N$ 个数:
$(N+1)!+2,(N+1)!+3,\dots ,(N+1)!+(N+1).$
对其中第 $j$ 个数 $(N+1)!+j$（$2\le j\le N+1$）:因为 $2\le j\le N+1$，所以 $j\mid (N+1)!$，又显然 $j\mid j$，故
$j\left|\right((N+1)!+j).$
而 $(N+1)!+j>j>1$，所以它有真因子 $j$，是合数。这 $N$ 个数连续排列，全是合数。$■$

妙在哪:它把”素数之间的空隙可以任意大”这个抽象命题，变成了一个能写下来的具体例子。阶乘 $(N+1)!$ 是”一口气塞进 $2$ 到 $N+1$ 所有因子”的魔法。

构造 vs 非构造

构造性证明真的告诉你东西长什么样，所以在 CS 里特别值钱——一个构造性存在证明往往直接对应一个算法。它的反面是”非构造性证明”(只证存在、不告诉你是谁)，见 §2.3，那是另一种味道的优雅。

---

第二族 · 反向否定 (Negation-based)

这一族的灵魂

当正面推太难时，假设”结论不成立”，然后从这个假设里榨出矛盾或可用信息。 否定一个命题，常常比肯定它更容易动手——这是数学最深刻的策略之一。

2.1 逆否命题证明 (Proof by Contrapositive) ★

核心思想:$P\Rightarrow Q$ 和它的逆否命题 $\neg Q\Rightarrow \neg P$ 逻辑等价。如果正面证 $P\Rightarrow Q$ 别扭，就改证 $\neg Q\Rightarrow \neg P$。

逻辑骨架:

$$(P\Rightarrow Q)\equiv (\neg Q\Rightarrow \neg P).$$

例:若 $n^2$ 是偶数，则 $n$ 是偶数

命题:$n^2$ 偶 $\Rightarrow$ $n$ 偶。
难点:正面假设”$n^2$ 偶”，很难直接说出 $n$ 的结构(从平方反推根很别扭)。
改证逆否:”$n$ 奇 $\Rightarrow$ $n^2$ 奇”。这个正面就好走:$n=2k+1\Rightarrow n^2=4k^2+4k+1=2(2k^2+2k)+1$，是奇数。
逆否成立，故原命题成立。$■$

关键直觉:正向是”从平方往回看”(难)，逆否是”从根往前算”(易)。逆否把因果方向翻过来，常常把难走的路换成好走的路。

别和"逆命题"混

$P\Rightarrow Q$ 的逆命题是 $Q\Rightarrow P$(不等价，证它没用)；逆否命题是 $\neg Q\Rightarrow \neg P$(等价，证它有效)。15-151 第一个月就会反复敲打这个区别，很多人栽在这。

2.2 反证法 (Proof by Contradiction / Reductio ad Absurdum) ★★

核心思想:要证命题 $S$，先假设 $\neg S$(它的反面)，然后推出一个逻辑矛盾(比如 $1=0$、或同时 $a$ 又非 $a$)。既然反面导致荒谬，原命题必真。

逻辑骨架:

$$\text{假设 }\neg S⟶\cdots ⟶(\text{矛盾}\to \leftarrow )⟹S.$$

例:素数有无穷多个(Euclid 的经典反证)

命题:素数有无穷多个。
证明:假设反面——素数只有有限个，全部列出为 $p_1,p_2,\dots ,p_n$。构造
$N=p_1{p}_2\cdots p_n+1.$
$N>1$，所以它必有某个素因子 $p$。这个 $p$ 一定在我们的清单里(因为清单号称是全部素数)，即 $p=p_i$ 对某个 $i$。于是 $p_i\mid N$，又 $p_i\mid p_1\cdots p_n$，两式相减得
$p_i\left|\right(N-p_1\cdots p_n)=1,$
即 $p_i\mid 1$，但素数 $\ge 2$，不可能整除 $1$。矛盾。所以素数无穷多。$■$

灵魂:我们没有去”造出所有素数”(造不出)，而是假设它们有限，然后造一个清单外的素因子，逼出矛盾。

反证法是第二族的"母方法"

注意:逆否、非构造性存在、甚至下一族里的最小反例、无穷递降，骨子里都是反证法的特例——它们都先假设结论为假，再推出荒谬。反证法是它们共同的祖先；后面那些方法只是”反证 + 一个特定的矛盾来源(最小性 / 计数 / 良序)“。

2.3 非构造性存在证明 (Non-constructive Existence) ➕

核心思想:证明”存在满足某性质的对象”，但不指出它具体是谁——往往通过反证(假设它不存在导致矛盾)，或通过”二选一必有其一”的论证。

例:存在两个无理数 $a,b$ 使得 $a^b$ 是有理数

命题:$\exists$ 无理数 $a,b$ 使 $a^b\in \mathbb{Q}$。
证明(漂亮的”二选一”):考虑数 ${\sqrt{2}}^{\sqrt{2}}$。它要么有理，要么无理:

• 若 ${\sqrt{2}}^{\sqrt{2}}$ 有理:取 $a=b=\sqrt{2}$(都是无理数)，则 $a^b={\sqrt{2}}^{\sqrt{2}}$ 有理，命题成立。
• 若 ${\sqrt{2}}^{\sqrt{2}}$ 无理:取 $a={\sqrt{2}}^{\sqrt{2}}$(此时无理)，$b=\sqrt{2}$(无理)，则
  $a^b=({\sqrt{2}}^{\sqrt{2}}{)}^{\sqrt{2}}={\sqrt{2}}^{(\sqrt{2}\cdot \sqrt{2})}={\sqrt{2}}^2=2\in \mathbb{Q},$
  命题成立。

两种情况必居其一，无论哪种，所要的 $a,b$ 都存在。$■$

诡异之处:证明结束了，我们却不知道到底是哪种情况成立——也就是说，我们证明了 $a,b$ 存在，却说不出 $a$ 究竟是 $\sqrt{2}$ 还是 ${\sqrt{2}}^{\sqrt{2}}$！(事实上由 Gelfond–Schneider 定理可知 ${\sqrt{2}}^{\sqrt{2}}$ 是无理的，但这个证明根本不需要知道这一点——这正是它的魅力。)

我的点评:为什么这个例子让人着迷

它第一次让人意识到:“存在”和”能找到”是两回事。这个区别在 CS 理论里会变得尖锐——很多复杂度/可计算性结论都是”存在但找不到/算不出”。15-151 会用这个例子给你一次思维冲击，值得细品。

---

第三族 · 命题形状 (Statement Shape)

这一族的灵魂

不靠新技巧，而是看清命题本身的逻辑结构，把它拆成更小的、能分别处理的部分。 “当且仅当”拆成两个方向，“唯一”拆成”假设有两个，证它们相等”。

3.1 双向证明 (Iff / Biconditional Proof) ★

核心思想:$P\iff Q$ 意思是”$P$ 成立当且仅当 $Q$ 成立”，它等价于两个单向命题之和:

$$(P\iff Q)\equiv (P\Rightarrow Q)\wedge (Q\Rightarrow P).$$

所以证 iff 必须分别证两个方向(俗称”⟹ 方向”和”⟸ 方向”)，缺一不可。

例: $\gcd (a,b)=1⟺\exists x,y\in \mathbb{Z}:ax+by=1$

(⟹ 方向) 设 $\gcd (a,b)=1$。由 Bézout 定理(裴蜀定理):两个整数的最大公约数总能写成它们的整系数线性组合，且是能取到的最小正值。既然 $\gcd =1$，就存在 $x,y$ 使 $ax+by=1$。
(⟸ 方向) 设存在 $x,y$ 使 $ax+by=1$。令 $d=\gcd (a,b)$，则 $d\mid a$ 且 $d\mid b$，于是 $d\mid (ax+by)=1$，故 $d=1$。
两个方向都成立，得证。$■$

注意:两个方向用了不同的工具——⟹ 靠 Bézout(较深)，⟸ 靠整除性质(很浅)。这很典型:iff 的两半往往难度不对称。

iff 的头号陷阱

只证了一个方向就以为证完了。 尤其当一个方向”太显然”时，人会偷懒跳过。判分时这是直接腰斩的错误。养成习惯:写 iff 证明，先画两行”(⟹)""(⟸)“占位，逼自己两边都填。

3.2 唯一性证明 (Uniqueness Proof) ★

核心思想:要证”满足某性质的对象唯一”，标准套路是:假设有两个(记作 $x_1,x_2$)都满足性质，然后证明它们必然相等 $x_1=x_2$。

逻辑骨架:

$$(P(x_1)\wedge P(x_2))⟹x_1=x_2.$$

例:带余除法的商和余数唯一

命题:给定整数 $a$ 和正整数 $b$，满足 $a=bq+r,0\le r<b$ 的整数对 $(q,r)$ 唯一。
证明:假设有两组都满足:
$a=b{q}_1+r_1,a=b{q}_2+r_2,0\le r_1,r_2<b.$
两式相减:$0=b(q_1-q_2)+(r_1-r_2)$，即
$b(q_1-q_2)=r_2-r_1.$
所以 $b\mid (r_2-r_1)$。但由 $0\le r_1,r_2<b$ 知 $|r_2-r_1|<b$。一个绝对值小于 $b$ 的数若被 $b$ 整除，只能是 $0$。于是 $r_2=r_1$，代回得 $b(q_1-q_2)=0$，因 $b>0$ 故 $q_1=q_2$。两组相同，唯一性成立。$■$

套路提炼:”$b$ 整除一个绝对值小于 $b$ 的数 ⟹ 那个数是 0”是唯一性/整除证明里反复出现的杀招，请记住。

存在 + 唯一 = 良定义

很多定义(如"$a\mathrm{mod}b$""逆元""最简分数”)要成立，必须既存在又唯一。所以”存在性证明 + 唯一性证明”经常成对出现，合起来叫良定义性 (well-definedness)。这是 15-151 的高频考点。

---

第四族 · 良序与归纳大家族 (Well-Ordering & Induction) ★★★

这一族的灵魂(全篇最重要)

利用”某个量是良序的”——即它取值于一个”每个非空子集都有最小元”的集合(典型是 ${\mathbb{Z}}^{+}$)。 这一族有七个成员，看起来各异，其实是同一个原理穿了七件衣服。你那道 $a^2+2b^2=5c^2$ 就活在这一族里。

三位一体:归纳 = 强归纳 = 良序

下面三条命题在逻辑上完全等价(可以互相证明)，这是 15-151 的核心定理:

1. 数学归纳法(弱归纳)成立;
2. 强归纳法成立;
3. 良序原理(${\mathbb{Z}}^{+}$ 每个非空子集有最小元)成立。

它们是”同一枚硬币的三面”。理解这一点，你就懂了为什么归纳和递降是对偶的:归纳从最小元出发往上造，递降假设有反例却往下拆到撞穿最小元。

4.1 弱归纳法 (Weak / Ordinary Induction) ★

核心思想:要证”对所有 $n\ge n_0$，$P(n)$ 成立”，只需:

1. 基础步 (base case):证 $P(n_0)$;
2. 归纳步 (inductive step):假设 $P(n)$ 成立(归纳假设)，证 $P(n+1)$ 成立。

像多米诺骨牌:第一张倒(基础)，且每张倒会推倒下一张(归纳步)，则全倒。

例:前 $n$ 个奇数之和等于 $n^2$

命题:$1+3+5+\cdots +(2n-1)=n^2$。
证明(对 $n$ 归纳):

• 基础步 $n=1$:左边 $=1$，右边 $=1^2=1$，成立。
• 归纳步:假设 $1+3+\cdots +(2n-1)=n^2$。则加上第 $n+1$ 个奇数 $2(n+1)-1=2n+1$:
  $\underset{=n^2\text{(归纳假设)}}{\underbrace{1+3+\cdots +(2n-1)}}+(2n+1)=n^2+2n+1=(n+1{)}^2.$
  这正是 $P(n+1)$。由归纳法，命题对所有 $n\ge 1$ 成立。$■$

几何彩蛋:这个等式有个无字证明——把 $n^2$ 的方格按”L 形”一层层剥开，每层恰好是 $1,3,5,\dots$ 个格子。这也预告了第五族的”双重计数”。

4.2 强归纳法 (Strong / Complete Induction) ★

核心思想:归纳步里，不只假设 $P(n)$，而是假设”直到 $n$ 为止全部成立” $P(n_0),P(n_0+1),\dots ,P(n)$，再证 $P(n+1)$。

什么时候非用强归纳不可:当证 $P(n+1)$ 需要回头用到比 $n$ 小得多的、不确定的某一项时，弱归纳(只给你 $P(n)$)就不够了。

例:每个整数 $n\ge 2$ 都能写成素数之积(算术基本定理的存在性)

命题:每个 $n\ge 2$ 是若干素数的乘积。
证明(强归纳):

• 基础步 $n=2$:$2$ 本身是素数，是”一个素数的积”。
• 归纳步:假设所有 $2\le k\le n$ 都能写成素数之积。考虑 $n+1$:
• 若 $n+1$ 是素数，它本身就是素数之积，完成。
• 若 $n+1$ 是合数，则 $n+1=ab$，其中 $1<a,b<n+1$，即 $2\le a,b\le n$。由强归纳假设，$a$ 和 $b$ 各自都是素数之积，于是 $n+1=ab$ 也是素数之积。

由强归纳法，命题对所有 $n\ge 2$ 成立。$■$

为什么弱归纳在这里会失败:$n+1$ 分解出的 $a,b$ 可能是 $3$ 和 $\frac{n+1}{3}$ 这种”跳得很远”的数，不是 $n$。弱归纳只攥着 $P(n)$，够不着 $a,b$;强归纳一次攥住”全部小于它的”，才接得住。这是判断”该用强归纳”的金标准:分解出的子问题大小不可控。

4.3 结构归纳法 (Structural Induction) ★➕

核心思想:把归纳从”自然数”推广到任何递归定义的结构(字符串、列表、树、表达式、语法……)。证明分两步:

1. 基础步:对递归定义里的基本对象(原子情形)证性质;
2. 归纳步:假设性质对组成部分成立，证它对由这些部分组装出的更大结构也成立。

例:满二叉树的叶子数 = 内部节点数 + 1

递归定义(“满二叉树”):

• (基本) 单个叶子节点是一棵满二叉树;
• (递归) 取一个根节点，给它接上两棵满二叉树作为左右子树，就得到一棵更大的满二叉树(此时根是内部节点)。

命题:对任意满二叉树 $T$，记 $L(T)$ 为叶子数、$I(T)$ 为内部节点数，则 $L(T)=I(T)+1$。
证明(结构归纳):

• 基础步:$T$ 是单个叶子。$L(T)=1,I(T)=0$，确有 $1=0+1$。✓
• 归纳步:$T$ 由根 $+$ 左子树 $T_1+$ 右子树 $T_2$ 组成。叶子全在子树里，内部节点是两棵子树的内部节点加上新根:
  $L(T)=L(T_1)+L(T_2),I(T)=I(T_1)+I(T_2)+1.$
  由归纳假设 $L(T_1)=I(T_1)+1$、$L(T_2)=I(T_2)+1$，代入:
  $L(T)=(I(T_1)+1)+(I(T_2)+1)=(I(T_1)+I(T_2)+1)+1=I(T)+1.■$

为什么这是"CS 味最重"的方法

竞赛几乎不练它，但它在 CMU 15-150(函数式编程)、15-251(理论 CS) 里无处不在——因为程序里的数据结构(列表、树、AST)和语言的语法都是递归定义的，要证”程序对所有输入正确""所有合法表达式满足某性质”，靠的就是结构归纳。提前练熟它，你后面会省下大量痛苦。 这是我特别建议你重视的方向。

4.4 良序原理 (Well-Ordering Principle) ★

核心思想:${\mathbb{Z}}^{+}$(或任何非负整数集)的每个非空子集都有最小元。 用法:把”反例集合”或”满足某条件的集合”拿出来，取它的最小元，再利用”它是最小的”这个性质做文章。

例:不存在严格介于 $0$ 与 $1$ 之间的整数

命题:不存在整数 $n$ 满足 $0<n<1$。
证明(良序):假设这样的整数存在，令
$S=\{n\in \mathbb{Z}:0<n<1\}.$
由假设 $S\ne \varnothing$，且 $S\subseteq {\mathbb{Z}}^{+}$。由良序原理，$S$ 有最小元 $m$，满足 $0<m<1$。把不等式 $0<m<1$ 同乘正数 $m$:
$0<m^2<m<1.$
于是 $m^2$ 也满足 $0<m^2<1$，即 $m^2\in S$;但 $m^2<m$，比最小元还小——矛盾。所以 $S=\varnothing$。$■$

灵魂:良序原理保证了”最小元存在”，而"$m^2<m$"制造出一个更小的成员，直接捅穿最小性。这个”取最小，再造更小”的套路，就是下面最小反例和无穷递降的雏形。

4.5 最小反例法 (Minimal Counterexample) ★★

核心思想:假设命题为假，则反例集合非空;按某个良序量(大小、位数、解的范数……)取一个”最小的反例”，然后证明:这个最小反例要么自相矛盾，要么能造出一个更小的反例——无论哪样，都和”它最小”矛盾。

逻辑骨架:

$$\text{假设有反例}\to \text{取最小反例 }{x}_{\min }\to \text{造出更小反例 }{x}^{\prime }<x_{\min }\to \to \leftarrow .$$

例:每个正整数都能写成"不同 2 的幂之和"(二进制表示存在性)

命题:每个正整数 $n$ 都能写成若干个互不相同的 $2$ 的幂之和。
证明(最小反例):假设不能，令 $n$ 为最小的无法这样表示的正整数。
取满足 $2^k\le n$ 的最大的 $k$，则 $2^k\le n<2^{k+1}$，于是
$0\le n-2^k<2^{k+1}-2^k=2^k.$
分两种情况:

• 若 $n-2^k=0$:那么 $n=2^k$ 本身就是一个 $2$ 的幂，可表示——与”$n$ 是反例”矛盾。
• 若 $0<n-2^k<2^k$:由于 $n-2^k<n$ 且 $n$ 是最小反例，$n-2^k$ 可以被表示成不同 $2$ 的幂之和。又因 $n-2^k<2^k$，这个表示里用到的幂全都小于 $2^k$，不含 $2^k$。于是给它补上一个 $2^k$，就得到 $n$ 的一个”互不相同的幂之和”表示——与”$n$ 是反例”矛盾。

两种情况都矛盾，故反例不存在。$■$

最小反例 vs 无穷递降:同一灵魂，两种姿态

• 最小反例是静态的:你站在”已经最小”的位置，发现还能更小，一击致命。
• 无穷递降是动态的:你不断造出更小、再更小的解，强调”这个过程能无限进行下去”，而正整数不能无限减小，故矛盾。

两者数学上等价，但写证明时最小反例通常更干净——因为你不必论证”过程真的无限”，只需要一次矛盾。你那道 $a^2+2b^2=5c^2$ 的标准写法(取 $|c|$ 最小)其实就是最小反例的姿态。

4.6 无穷递降 (Infinite Descent) ★★

核心思想(费马的招牌):假设方程有解(或命题有反例)，从一个解构造出一个严格更小的解;但解的”大小”是正整数，不能无限变小，矛盾。因此无解。

逻辑骨架:

$$\text{有解}\to \text{造出更小的解}\to \text{再造更小}\to \cdots (\text{正整数无限下降，不可能})\to \to \leftarrow .$$

例: $a^2+2b^2=5c^2$ 无非平凡整数解(就是我们一起做过的那道)

命题:$a^2+2b^2=5c^2$ 的唯一整数解是 $(0,0,0)$。
证明(无穷递降 / 最小反例):反设存在 $c\ne 0$ 的非平凡解，在所有这样的解里取 $|c|$ 最小的一组 $(a,b,c)$(良序原理保证存在)。

第一步:模 5。 由 $a^2+2b^2=5c^2$ 得 $a^2\equiv 2b^2(\mathrm{mod}5)$。模 5 的二次剩余:
$a^2\mathrm{mod}5\in \{0,1,4\},2b^2\mathrm{mod}5\in \{0,2,3\}.$
要让两边相等，必须落在交集 $\{0,1,4\}\cap \{0,2,3\}=\{0\}$。故 $5\mid a^2$ 且 $5\mid b^2$;因 $5$ 是素数(Euclid 引理)，$5\mid a$ 且 $5\mid b$。

第二步:代入并下降。 写 $a=5a_1,b=5b_1$:
$25a_1^2+50b_1^2=5c^2\Rightarrow 5a_1^2+10b_1^2=c^2\Rightarrow 5\mid c^2\Rightarrow 5\mid c.$
再写 $c=5c_1$:
$5a_1^2+10b_1^2=25c_1^2\Rightarrow a_1^2+2b_1^2=5c_1^2.$

第三步:撞穿最小性。 于是 $(a_1,b_1,c_1)$ 也是解，且因 $c=5c_1,c\ne 0$:
$|c_1|=\frac{|c|}{5}<|c|.$
这与”$|c|$ 最小”矛盾。故非平凡解不存在，唯一解为 $(0,0,0)$。$■$

(已用 Python 在 $|a|,|b|,|c|\le 200$ 范围内暴力确认零非平凡解，与结论一致。)

历史与级别

无穷递降是费马的独门武器，他用它证了 $x^4+y^4=z^4$ 无非平凡解。它属于初等数论与竞赛数学的核心技巧:AIME 偶尔出现，USAMO/IMO 是必备。它”初等但不平凡”——每一步高中生都能懂，但想到”取最小反例”这一起手式需要真正的洞察。

4.7 极值原理 (Extremal Principle) ★➕

核心思想:把”取最小/最大”的思想从数论搬到组合与图论。在一个有限(或良序)结构里，总存在某个极值对象(最长路径、最大集合、最近的两点、面积最小的三角形……);利用这个对象的极值性质(它不能再被改进)推出结论或矛盾。

例:最小度 $\ge 2$ 的图必含圈(经典"最长路径"论证)

命题:若一个有限简单图 $G$ 中每个顶点的度数都 $\ge 2$，则 $G$ 含有一个圈 (cycle)。
证明(极值:取最长路径):由于 $G$ 有限，存在一条最长的路径 $P=v_0{v}_1{v}_2\cdots v_k$。考察端点 $v_0$:

• $v_0$ 的所有邻居都必须落在 $P$ 上。否则，若 $v_0$ 有一个不在 $P$ 上的邻居 $w$，就能把路径延长成 $w{v}_0{v}_1\cdots v_k$，比 $P$ 更长——与”$P$ 最长”矛盾。
• $v_0$ 的度数 $\ge 2$，所以除了 $v_1$，它至少还有另一个邻居 $v_j$(且 $j\ge 2$)，这个 $v_j$ 也在 $P$ 上。

于是 $v_0{v}_1{v}_2\cdots v_j{v}_0$ 构成一个圈(长度 $j+1\ge 3$)。$■$

灵魂:良序量从”整数大小”换成了”路径长度”。“最长路径的端点无处可去”这个张力，正是矛盾的来源——和无穷递降”撞穿最小性”是同一种几何。

把第四族当成"一套思维的多种表达"

对竞赛来说，无穷递降 ↔ 最小反例 ↔ 极值原理 ↔ 良序应当被当作同一套思维的四种说法熟练掌握:它们覆盖了绝大多数”无解 / 必为某形式 / 必存在 / 唯一”类题目。判断信号:题目里有没有一个能取”最小/最大/最长”的量？ 有，就往这一族想。

---

第五族 · 计数派 (Counting-based)

这一族的灵魂

用”数数”和”有限性”直接逼出结论。 有时把同一个东西数两遍得到等式;有时靠”东西比盒子多”得到重合;有时用加加减减算出精确个数。共同的底色是:有限世界里，数量本身就是约束。

5.1 鸽巢原理 (Pigeonhole Principle) ★★

核心思想:把 $n+1$ 只鸽子放进 $n$ 个鸽笼，必有一个笼子装了至少两只。推广:$m$ 只鸽子 $n$ 个笼子，必有一个笼子装了至少 $\lceil m/n\rceil$ 只。

用法关键:难点永远在**“谁是鸽子、谁是鸽笼”** ——一旦设计对了映射，结论往往瞬间出来。

例:任意 $n+1$ 个整数中，必有两个之差被 $n$ 整除

命题:从整数里任取 $n+1$ 个，必存在两个，它们的差是 $n$ 的倍数。
证明(鸽巢):

• 鸽笼:整数模 $n$ 的余数共 $n$ 种,即 $\{0,1,2,\dots ,n-1\}$。
• 鸽子:这 $n+1$ 个整数，每个按”模 $n$ 的余数”放进对应鸽笼。

$n+1$ 只鸽子进 $n$ 个笼，必有两个整数 $x,y$ 落入同一个笼，即 $x\equiv y(\mathrm{mod}n)$。于是 $n\mid (x-y)$。$■$

妙处:我们根本不关心这些整数是什么，只关心它们的余数——把无限的整数压进 $n$ 个抽屉，鸽巢立刻生效。

鸽巢在 CS 里的化身

“从大集合到小集合的函数不可能单射”就是鸽巢的函数版本。它直接解释了哈希冲突 (hash collision) 为什么不可避免(键空间比桶多)，也是无损压缩不可能对所有输入都缩短的根本原因(抽屉装不下)。你做数据科学/算法时会反复撞见它。

5.2 双重计数 (Double Counting / Combinatorial Proof) ★★

核心思想:把同一个集合(或同一个量)用两种不同的方式数，两个结果必相等——于是得到一个恒等式。优雅之处在于:不做任何代数推导，仅靠”换个角度数”就证明了等式。

例:握手引理 $\sum _v\mathrm{deg}(v)=2|E|$

命题:在任意有限图中，所有顶点的度数之和等于边数的两倍。
证明(双重计数):数同一个集合——所有的”关联对” $(v,e)$，其中顶点 $v$ 是边 $e$ 的一个端点。

• 按顶点数:固定一个顶点 $v$，它参与的关联对数等于它的度数 $\mathrm{deg}(v)$。对所有顶点求和:关联对总数 $={\sum }_v\mathrm{deg}(v)$。
• 按边数:固定一条边 $e$，它恰好有 $2$ 个端点，贡献 $2$ 个关联对。对所有边求和:关联对总数 $=2|E|$。

同一批关联对，两种数法结果相等:${\sum }_v\mathrm{deg}(v)=2|E|$。$■$

立得推论:右边是偶数，所以度数为奇的顶点个数必为偶数(否则奇数之和为奇)。这条小结论在图论里用得极多。

双重计数的威力与品味

你组合很强，但我特别建议你专门品味这种”数两次代替硬算”的思维方式。很多看起来要用复杂代数(归纳、二项式展开)才能证的恒等式，比如 ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$(数”$n$ 元集的所有子集”:左边按大小分类数，右边每个元素选或不选 $2^n$)、或 ${\sum }_{k}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n{2}^{n-1}$，用双重计数往往一句话秒杀。这种优雅会反哺你的竞赛直觉。

5.3 容斥原理 (Inclusion-Exclusion) ★

核心思想:数”至少属于某些集合之一”的元素个数时，直接相加会重复计数。修正办法:加上单个集合，减去两两交，加回三三交，减去四四交……正负交替:

$$|A_1\cup \cdots \cup A_n|=\sum |A_i|-\sum _{i<j}|A_i\cap A_j|+\sum _{i<j<k}|A_i\cap A_j\cap A_k|-\cdots$$

例: $\{1,2,\dots ,100\}$ 中能被 $2$、$3$ 或 $5$ 整除的数有几个？

解(容斥):设 $A,B,C$ 分别为能被 $2,3,5$ 整除的集合。用 $\lfloor 100/d\rfloor$ 数倍数:
$|A|=50,|B|=33,|C|=20,$
$|A\cap B|=\lfloor 100/6\rfloor =16,|A\cap C|=\lfloor 100/10\rfloor =10,|B\cap C|=\lfloor 100/15\rfloor =6,$
$|A\cap B\cap C|=\lfloor 100/30\rfloor =3.$
代入容斥:
$|A\cup B\cup C|=(50+33+20)-(16+10+6)+3=103-32+3=\boxed{74}.$
故有 74 个。$■$

(已用 Python 暴力枚举验证 $=74$，与公式一致。)

直觉:被 $6$ 整除的数在 $A$ 和 $B$ 里各数了一次(多数了一次)，所以要减回去;但被 $30$ 整除的数被加三次、减三次正好归零，所以最后要再加回来一次——正负交替正是为了”每个元素净计一次”。

进阶去向

容斥的”高配版本”是默比乌斯反演 (Möbius inversion),它把这套”加加减减”用 $\mu$ 函数统一成一个公式,在你的数论曲线里(尤其是积性函数、欧拉函数求和)会正式登场。错位排列 (derangement) 个数 $D_n=n!{\sum }_{k=0}^n\frac{(-1{)}^k}{k!}$ 也是容斥的经典战果。

---

第六族 · 对角线论证 (Diagonalization)

这一族的灵魂

构造一个”和清单上每一个都不同”的对象——尤其让它在”第 $i$ 位”上故意和”第 $i$ 个候选”作对。 这种”自我否定”的构造能证明某些集合”大到无法列举”，是数学和计算理论最深刻的思想之一。

6.1 对角线论证 (Cantor’s Diagonal Argument) ★★➕

核心思想:要证某个集合不可数(无法和 $\mathbb{N}$ 一一对应)，假设它可数(于是能排成一张清单)，然后沿对角线造一个新元素:让它的第 $i$ 个特征故意不同于清单第 $i$ 个元素的第 $i$ 个特征。这个新元素和清单上每一个都不同，却本应在清单里——矛盾。

例:区间 $[0,1]$ 中的实数不可数(Cantor)

命题:$[0,1]$ 里的实数无法排成一个序列(即不可数)。
证明(对角线 + 反证):假设可数，把 $[0,1]$ 里全部实数排成一张清单，每个写成小数:

$$\begin{array}{rl}{x}_1& =0.d_{11}{d}_{12}{d}_{13}\cdots \\ x_2& =0.d_{21}{d}_{22}{d}_{23}\cdots \\ x_3& =0.d_{31}{d}_{32}{d}_{33}\cdots \\ & ⋮\end{array}$$

其中 $d_{ij}$ 是 $x_i$ 的第 $j$ 位数字。现在沿对角线造一个新数 $y=0.y_1{y}_2{y}_3\cdots$，规则是:
$y_i=\{\begin{array}{ll}5,& \text{若 }{d}_{ii}\ne 5,\\ 6,& \text{若 }{d}_{ii}=5.\end{array}$
(只用 $5,6$ 两个数字，避开 $0.999\dots =1.000\dots$ 的歧义。)
这个 $y\in [0,1]$。但对每个 $i$，$y$ 的第 $i$ 位 $y_i\ne d_{ii}$，所以 $y\ne x_i$。也就是说 $y$ 不在清单上——可清单号称包含了 $[0,1]$ 的全部实数。矛盾。所以 $[0,1]$ 不可数。$■$

灵魂:那个新数 $y$ 是被**专门设计来”和每个候选作对”**的——它在第 $i$ 行第 $i$ 列(对角线)上偏偏不一样。这种自指式的构造是对角线论证的精髓。

我的点评:这是通往计算理论的门户

对角线论证不止证了”实数比自然数多”。同一套自指思想，被图灵 (Turing) 用来证明停机问题 (Halting Problem) 不可判定:假设有个程序能判断”任意程序是否停机”，就能构造一个”专和它作对”的程序导致矛盾。Cantor 的对角线 = 图灵不可判定性 = 哥德尔不完备性，三者共用这一个灵魂。这是 CMU 15-251 的高光内容，竞赛数论碰不到，但它是 CS 理论的根。强烈建议你认真对待这一节——它会重塑你对”计算的极限”的理解。

---

第七族 · 数论专精 (Advanced Number-Theoretic) ➕

这一族的灵魂

把第四族(良序/递降)和第五族(计数)的思想，装上专门的数论引擎。 Vieta 跳跃 = 递降 + 韦达定理;p-adic 赋值 = 把”数素因子”系统化成一种”测量”。这两个是你冲 IMO 级别、以及为 CMU 数论/代数课打底的关键升级。

7.1 Vieta 跳跃 (Vieta Jumping) ➕

核心思想:对付含参数的二次丢番图方程时，把方程看成某个变量的二次方程,利用韦达定理(两根之和、之积已知)从一个解”跳”到另一个解;通常这个新解更小，于是接上无穷递降/最小反例收尾。

例:IMO 1988 第 6 题(传奇"第 6 题")

命题:设正整数 $a,b$ 满足 $ab+1\mid a^2+b^2$，令 $k=\frac{a^2+b^2}{ab+1}$。证明 $k$ 是完全平方数。
证明(Vieta 跳跃):固定这个整数 $k$。在所有满足 $a^2+b^2=k(ab+1)$ 的非负整数对 $(a,b)$ 中，取使 $a+b$ 最小的一组，不妨设 $a\ge b$。

基础情形:若 $b=0$。 方程变成 $a^2=k(0+1)=k$，所以 $k=a^2$ 是完全平方数,结论成立。

归纳/下降:若 $b\ge 1$,导出矛盾。 把方程
$a^2-(kb)a+(b^2-k)=0$
看成关于 $a$ 的二次方程(把 $b,k$ 当常数)。$a$ 是它的一个根，设另一根为 $a^{\prime }$。由韦达定理:
$a+a^{\prime }=kb\Rightarrow a^{\prime }=kb-a\in \mathbb{Z}(\text{整数!}),a\cdot a^{\prime }=b^2-k.$
现在证 $(a^{\prime },b)$ 是一个更小的非负整数解:

• $a^{\prime }$ 是整数:由 $a^{\prime }=kb-a$，✓。
• $a^{\prime }\ge 0$:若 $a^{\prime }<0$，则在 $a^{\prime 2}+b^2=k(a^{\prime }b+1)$ 中，左边 $>0$;而 $a^{\prime }\le -1,b\ge 1$ 使 $a^{\prime }b+1\le 0$，右边 $\le 0$,矛盾。故 $a^{\prime }\ge 0$。
• $a^{\prime }<a$:由 $a\cdot a^{\prime }=b^2-k$ 且 $k\ge 1$,有 $a^{\prime }=\frac{b^2-k}{a}<\frac{b^2}{a}\le \frac{ab}{a}=b\le a$(用了 $b\le a$)。故 $a^{\prime }<a$。

于是 $(a^{\prime },b)$ 也是非负整数解，且 $a^{\prime }+b<a+b$——比我们选的”最小”还小，矛盾。

所以最小解必落在基础情形 $b=0$，从而 $k=a^2$ 是完全平方数。$■$

它和你那道递降题的关系

Vieta 跳跃就是无穷递降的”高配进化版”:同样取最小解、同样往下降、同样用最小性撞矛盾;唯一的新东西是”怎么造出更小的解”——普通递降靠”除以公因子”(像你那道除以 $5$)，Vieta 靠”韦达定理跳到另一个根”。如果你以后打 IMO 级别，这是必须形成肌肉记忆的招。

7.2 p-adic 赋值 (p-adic Valuation) ➕

核心思想:定义 $v_p(n)$ 为整数 $n$ 中素数 $p$ 的幂次(例如 $v_2(24)=3$，因为 $24=2^3\cdot 3$)。它把”数素因子”变成一种测量，满足两条关键性质:

$$v_p(xy)=v_p(x)+v_p(y),v_p(x+y)\ge \min (v_p(x),v_p(y)),$$

且当 $v_p(x)\ne v_p(y)$ 时第二条取等号($v_p(x+y)=\min$，这叫超度量/非阿基米德性质)。很多整除、平方、整数性问题，用 $v_p$ 一比就清楚了。

例:调和级数 $H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}$ 当 $n\ge 2$ 时永远不是整数

命题:对 $n\ge 2$，$H_n={\sum }_{k=1}^n\frac{1}{k}\notin \mathbb{Z}$。
证明($2$-adic 赋值):设 $2^s$ 是满足 $2^s\le n$ 的最大 $2$ 的幂(即 $2^s\le n<2^{s+1}$)。

关键观察:在 $1,2,\dots ,n$ 中，恰好只有一个数的 $v_2$ 等于 $s$，就是 $2^s$ 本身。 因为任何 $v_2=s$ 的数形如 $2^s\cdot (\text{奇数})$，下一个($2^s\cdot 3$)已经 $\ge 3\cdot 2^s>2^{s+1}>n$，超出范围;而 $v_2\ge s+1$ 的数 $\ge 2^{s+1}>n$ 也超范围。所以其余所有 $k\le n$ 都满足 $v_2(k)<s$，从而 $v_2\left(\frac{1}{k}\right)=-v_2(k)>-s$。

于是在 $H_n={\sum }_k\frac{1}{k}$ 这堆 $2$-adic 数里，唯独 $\frac{1}{2^s}$ 的赋值 $-s$ 最小(最”负”)，且独一无二。由超度量的取等性质(最小者唯一时和的赋值等于该最小值):
$v_2(H_n)=-s<0.$
但任何整数 $m$ 都有 $v_2(m)\ge 0$。所以 $H_n$ 不是整数。$■$

(已用精确分数运算验证 $H_n$ 在 $2\le n\le 30$ 内分母均 $\ne 1$，即都非整数，与结论一致。)

把你那道题"翻译"成赋值语言(高回报投资)

我在之前的对话里建议过你:用 p-adic 的眼光重看 $a^2+2b^2=5c^2$。这里说清楚:对乘积型等式，$v_p$ 能一行定胜负(比如用 $v_2$ 证 $\sqrt{2}$ 无理:$a^2=2b^2\Rightarrow 2v_2(a)=1+2v_2(b)$，偶 $=$ 奇，矛盾);但对你那种求和型方程($a^2+2b^2$ 是个和，不是积)，赋值不能直接读出和的值——这正是为什么那道题需要”模 5 + 递降”而不能一行解决。换句话说:对求和型方程，赋值论证本质上就是把递降”形式化”了一遍。 想清楚这个边界，你就真正理解了赋值能做什么、不能做什么。

这个视角的真正价值在未来:学到 Hensel 引理、局部域 (local fields)、$p$-adic 数 时(CMU 的高级数论/代数课、以及椭圆曲线密码学的理论基础)，你会发现”$v_p$ 测量”是无缝衔接的地基。

---

8. 综合:拿到一道证明题，怎么选方法？

选方法的决策流程(背下来)

按顺序自问下面几个问题，第一个命中的就是你的起手方向:

1. 命题是”当且仅当”吗？ → 拆成两个方向(§3.1)，每个方向再单独选方法。
2. 命题说”唯一”吗？ → 假设有两个，证相等(§3.2)。
3. 命题是”对所有 $n$ / 对所有递归结构”吗？ → 归纳大家族:数字上用弱/强归纳(§4.1–4.2)，结构上用结构归纳(§4.3)。分解出的子问题大小不可控 → 强归纳。
4. 命题说”无解 / 不存在 / 唯一解是平凡解”吗？ → 反证 + 无穷递降/最小反例(§4.5–4.6);若是二次丢番图方程，考虑 Vieta 跳跃(§7.1)。
5. 命题说”存在……”吗？ → 先试构造(§1.3，最干脆);构造不出再试非构造/反证(§2.3)。
6. 命题说”必有两个…… / 必然重合”吗？ → 鸽巢(§5.1),关键是设计”鸽子与鸽笼”。
7. 要证一个计数等式吗？ → 试双重计数(§5.2，最优雅);要数”并集大小”用容斥(§5.3)。
8. 要证”不可数 / 不可判定 / 无法枚举”吗？ → 对角线论证(§6.1)。
9. 题里有可取”最大/最小/最长”的量吗(尤其图论组合)？ → 极值原理(§4.7)。
10. 以上都别扭、而题目正面好推吗？ → 老老实实直接证明(§1.1);情况太多就分情况(§1.2)。
11. 整除/平方/整数性问题，且能看素因子幂次吗？ → p-adic 赋值(§7.2)。

一个反复出现的"通用矛盾来源"

你会发现，最强的几族(反证、最小反例、递降、极值、鸽巢、对角线)制造矛盾的方式高度相似:先假设一个”最优/最小/完整”的对象存在，再证明它其实不够最优/还能更小/并不完整。 这种”逼出’比最好还好’的荒谬”是高级证明的通用引擎——看到题目里能定义某种’最’，就该警觉这一招。

---

9. 自测题(先自己挑方法、自己写，再点开)

自测 1(选方法 + 直接/逆否)

证明:对整数 $n$，若 $n^3$ 是偶数，则 $n$ 是偶数。

答案 1(逆否最干净)

方法选择:正面”从 $n^3$ 偶反推 $n$“别扭 → 用逆否(§2.1)。
逆否命题:”$n$ 奇 $\Rightarrow$ $n^3$ 奇”。设 $n=2k+1$，则 $n^3=(2k+1{)}^3=8k^3+12k^2+6k+1=2(4k^3+6k^2+3k)+1$,是奇数。逆否成立，故原命题成立。$■$

教训:凡是”从高次幂/平方反推底数”的整除命题，几乎都该条件反射地换成逆否。

自测 2(无穷递降 / 最小反例,重要)

证明:$x^2+y^2=3z^2$ 没有非平凡整数解。
(提示:模 $3$,$x^2\mathrm{mod}3\in \{0,1\}$。)

答案 2(完全平行于我们做过的那道)

方法:反证 + 无穷递降(§4.6)。反设有 $z\ne 0$ 的非平凡解,取 $|z|$ 最小的一组。
模 3:$x^2+y^2\equiv 0(\mathrm{mod}3)$。由 $x^2,y^2\mathrm{mod}3\in \{0,1\}$，两个 $\{0,1\}$ 里的数相加 $\equiv 0(\mathrm{mod}3)$ 只能是 $0+0$。故 $3\mid x$ 且 $3\mid y$。
写 $x=3x_1,y=3y_1$:$9x_1^2+9y_1^2=3z^2\Rightarrow 3x_1^2+3y_1^2=z^2\Rightarrow 3\mid z^2\Rightarrow 3\mid z$。
写 $z=3z_1$:$3x_1^2+3y_1^2=9z_1^2\Rightarrow x_1^2+y_1^2=3z_1^2$,且 $|z_1|=|z|/3<|z|$,矛盾。故唯一解 $(0,0,0)$。$■$

迁移练习的价值:你应该能感到——这和 $a^2+2b^2=5c^2$ 是同一台机器，只是把模数换成 3、系数换一下。掌握”模 + 递降”的模板后，这类题可以批量解决。

自测 3(强归纳)

邮局只有 $3$ 分和 $5$ 分两种邮票。证明:任何 $\ge 8$ 分的邮资都能用这两种邮票凑出。

答案 3(强归纳,基础步要够多)

方法:强归纳(§4.2)。
基础步(需要连续几个,因为步长是 3):$8=3+5$;$9=3+3+3$;$10=5+5$。三个都能凑。
归纳步:设所有 $8\le k\le n$(其中 $n\ge 10$)都能凑。考虑 $n+1$:因为 $n+1\ge 11$,有 $n+1-3=n-2\ge 8$,落在归纳假设范围内,故 $n-2$ 能凑;给它再贴一张 3 分就凑出 $n+1$。$■$

为什么基础步要 3 个:归纳步靠”减 3 退回已知”,所以必须有连续 3 个($8,9,10$)作地基,才能保证退回去不会掉到 8 以下的空隙。这是强归纳里”基础步要铺几个”的典型判断。

自测 4(鸽巢)

从 $\{1,2,\dots ,2n\}$ 中任取 $n+1$ 个数。证明:其中必有两个数互质(提示:相邻整数互质)。

答案 4(鸽巢,设计鸽笼是关键)

方法:鸽巢(§5.1)。
鸽笼:把 $\{1,\dots ,2n\}$ 配成 $n$ 对相邻整数:$\{1,2\},\{3,4\},\dots ,\{2n-1,2n\}$。
鸽子:取出的 $n+1$ 个数放进这 $n$ 个笼。$n+1>n$,必有两个数落进同一对,即它们是相邻整数 $m,m+1$。
相邻整数互质:若 $d\mid m$ 且 $d\mid (m+1)$,则 $d\mid 1$,故 $\gcd (m,m+1)=1$。得证。$■$

难点全在分笼:把”相邻整数”设计成鸽笼,是这题的灵魂。鸽巢题 90% 的功夫都花在”想出正确的鸽笼”。

自测 5(双重计数)

用双重计数证明组合恒等式 $\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$。

答案 5(数"子集"数两次)

方法:双重计数(§5.2)。数同一个集合——一个 $n$ 元集 $S$ 的所有子集。

• 数法一(按大小分类):大小为 $k$ 的子集有 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 个;$k$ 从 $0$ 到 $n$ 求和,子集总数 $={\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)$。
• 数法二(逐元素决定):构造一个子集,等价于对 $S$ 的每个元素独立决定”选或不选”,每个元素 $2$ 种选法,共 $n$ 个元素,故子集总数 $=2^n$。

同一批子集两种数法,${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$。$■$

对比:这个等式也能用二项式定理(令 $x=y=1$)或归纳证,但双重计数最直击本质——它告诉你这个等式”为什么对”(两边都在数子集),而不只是”算出来相等”。

自测 6(综合,有点难,p-adic 或直接)

证明:对 $n\ge 1$,$\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ 是偶数。(提示:试试 $v_2$,或想想 $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ 和 $\left(\genfrac{}{}{0ex}{}{2n-1}{n-1}\right)$ 的关系。)

答案 6(给两条路,体会方法选择)

路线 A(组合恒等式,最快):由 $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)=\left(\genfrac{}{}{0ex}{}{2n-1}{n-1}\right)+\left(\genfrac{}{}{0ex}{}{2n-1}{n}\right)$,而 $\left(\genfrac{}{}{0ex}{}{2n-1}{n-1}\right)=\left(\genfrac{}{}{0ex}{}{2n-1}{n}\right)$(对称性,因为 $(2n-1)-(n-1)=n$)。所以 $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)=2\left(\genfrac{}{}{0ex}{}{2n-1}{n-1}\right)$,是偶数。$■$
路线 B($2$-adic,练赋值手感):由 Kummer 定理,$v_2\left(\right(\genfrac{}{}{0ex}{}{2n}{n}\left)\right)$ 等于在二进制下 $n+n$ 时发生的进位次数。$n+n$ 至少在最低的非零位会产生一次进位(只要 $n\ge 1$),故进位次数 $\ge 1$,即 $v_2\left(\right(\genfrac{}{}{0ex}{}{2n}{n}\left)\right)\ge 1$,偶数。$■$

点评:路线 A 用第五族(组合恒等式)一步到位,是考场首选;路线 B 用第七族(赋值 + Kummer)更深刻,但需要更多工具。好的解题者手里有多把锤子,并知道这道题该用哪把。 这正是这份讲义想训练的元能力。

---

10. 一页速记 + 收尾

证明方法速记卡

一 · 正向构造:直接(顺推)、分情况(穷尽切分)、构造性存在(造出来)。
二 · 反向否定:逆否($\neg Q\Rightarrow \neg P$,等价)、反证(假设反面 → 矛盾)、非构造存在(证存在不说是谁)。
三 · 命题形状:双向(拆 ⟹ 和 ⟸)、唯一性(假设两个证相等)。
四 · 良序归纳 ★:弱归纳(多米诺)、强归纳(子问题大小不可控时用)、结构归纳(递归结构,CS 核心)、良序原理(取最小元)、最小反例(静态:最小处还能更小)、无穷递降(动态:无限下降不可能)、极值原理(最长/最大对象的张力)。它们都是”利用良序性”的同一灵魂。
五 · 计数派:鸽巢(鸽子>鸽笼必重合)、双重计数(同一物数两次)、容斥(正负交替去重)。
六 · 对角线:造一个”沿对角线和每个候选作对”的对象 → 不可数/不可判定。
七 · 数论专精 ➕:Vieta 跳跃(递降 + 韦达跳根)、p-adic 赋值($v_p$ 测素因子幂次)。
选方法口诀:iff 拆两半 · 唯一设俩 · 对所有用归纳 · 无解用递降 · 存在先构造 · 必重合用鸽巢 · 等式数两次 · 不可数用对角 · 有”最”用极值 · 整除看赋值。

学完这份讲义,确认你能:

• 不看讲义说出七大家族各自的”灵魂”和代表方法;
• 解释为什么归纳法、强归纳、良序原理三者等价,以及归纳与递降为何是”对偶”;
• 对每一种方法,独立写出一个完整例子(哪怕是讲义里的);
• 拿到一道新证明题,用第 8 节的决策流程在 30 秒内选出起手方向;
• 说清 p-adic 赋值对乘积型 vs 求和型方程的不同表现(为什么你那道题不能一行解决);
• 把 结构归纳、对角线论证、双重计数 这三个”CS 味”方法和 15-150/15-251 的去向对应起来。

全部打勾 → 你已经握住了从竞赛到 CMU 证明课的整套”证明工具箱”。

一句话收尾

证明方法看似有几十种,但它们的”灵魂”屈指可数:顺推、假设反面、拆解结构、利用良序、依靠有限性、构造自指。真正的高手不是记住更多招式,而是看一眼命题就知道”该调动哪种灵魂”。 而在所有灵魂里,你最该刻进骨子里的那一句是——“这道题里,什么量是良序的？” 答得出这个问题,你就握住了归纳、递降、极值、最小反例这一整片大陆的钥匙。你那道 $a^2+2b^2=5c^2$ 只是这片大陆上的第一座小山。