2. 直接证明、反证法与归纳法

设 $P(n)$ 是关于整数 $n\ge n_0$ 的陈述，$n_0$ 固定。数学归纳法说明：

1. 证明基础情形 $P(n_0)$。
2. 对任意整数 $k\ge n_0$，假设 $P(k)$，并证明 $P(k+1)$。
3. 得出对每个整数 $n\ge n_0$ 都有 $P(n)$。

第 2 步的假设是归纳假设，它是条件性的，不是预先假设最终定理成立。基础情形启动链条，蕴含则将任意有效一环延伸到下一环。

可用非负整数的最小元素性质说明：若有反例，则存在最小反例 $m\ge n_0$。基础情形排除 $n_0$，于是 $m-1\ge n_0$ 不是反例，归纳步骤迫使 $P(m)$ 成立，矛盾。

对于任意整数起点 $n_0$，将指标平移为 $m-n_0\ge0$，即可用最小元素性质证明上面的最小反例步骤。

反过来，正整数上的普通归纳法蕴含最小元素性质。假设非空集合 $S\subseteq\{1,2,3,\ldots\}$ 没有最小元素。令 $P(n)$ 表示 $1,\ldots,n$ 均不属于 $S$。若 $1\in S$，它就是最小元素，故 $P(1)$ 成立。若 $P(k)$ 成立而 $k+1\in S$，则 $k+1$ 是 $S$ 的最小元素，矛盾。因此 $P(k)\Rightarrow P(k+1)$。归纳法给出每个正整数 $n$ 都满足 $P(n)$，于是 $S$ 为空，与其非空假设矛盾。所以每个非空正整数集合都有最小元素。用 $n\mapsto n-n_0+1$ 平移指标，即得任意整数起点 $n_0$ 的对应归纳版本。

学习目标

写出直接证明、逆否证明及反证；分别证明存在性与唯一性；使用归纳法和最小反例论证。证明解释为何每个允许的情形都由定义和已知事实推出。检查许多实例可以提示定理，但不能代替全称论证。

证明结构

直接证明 $P\Rightarrow Q$ 时，假设 $P$ 并推出 $Q$。使用逆否命题时，假设 $\neg Q$ 并推出 $\neg P$。反证法假设前提及所需结论的否定，从中推出不可能的结果。矛盾必须来自已声明的假设，而不是无关的假命题。

对存在断言 $\exists x\ P(x)$，构造明确见证通常最有力。证明对象唯一时，先证明至少存在一个，再假设两个候选对象满足定义条件并证明它们相同。每个候选对象都必须满足某方程只证明必要性；在代回验证候选值前，还没有证明存在性。

例：奇偶性。 若整数 $n$ 为奇数，写 $n=2k+1$。则 $n^2=4k^2+4k+1=2(2k^2+2k)+1$ 为奇数。取逆否命题可知平方为偶数的整数本身必为偶数。这里没有假设每个整数都在 $\mathbb Z$ 中有平方根。

定理：由良序性推出归纳法

设 $P(n)$ 是整数 $n\ge n_0$ 上的谓词。若 $P(n_0)$ 为真，且对每个 $n\ge n_0$ 有 $P(n)\Rightarrow P(n+1)$，则对所有这样的整数 $P(n)$ 均成立。

证明。 假设不成立的指标集合非空。由良序性，它有最小元素 $m$。由于基础情形成立，$m$ 不等于 $n_0$，故 $m-1\ge n_0$。由最小性，$P(m-1)$ 成立；归纳蕴含推出 $P(m)$，与其不成立矛盾。故失败集合为空。

强归纳在归纳步骤中以从 $n_0$ 到 $n$ 的全部情形代替单独假设 $P(n)$；同样的最小反例证明可为其提供依据。当构造使用多个较小输入而非仅用紧邻前一项时，它很有用。

例题

有限求和。 证明对 $n\ge1$，$1+3+\cdots+(2n-1)=n^2$。当 $n=1$，两边都为一。假设公式在 $n$ 成立，加上下一个项 $2n+1$ 得 $n^2+2n+1=(n+1)^2$，正是下一情形。该步骤使用已知公式，而不是假设所需的下一个等式。

线性方程解的存在性与唯一性。 对实数 $a\ne0,b$，方程 $ax+b=0$ 恰有一个解。$x=-b/a$ 存在，代入可验证。若 $x,y$ 都是解，相减得 $a(x-y)=0$，故 $x=y$。若 $a=0$，则无解（$b\ne0$）或有无穷多个解（$b=0$），说明该假设不可省略。

分层练习

1. 基础。 从定义证明两个奇整数之和为偶数。
2. 核心。 用归纳法证明对 $n\ge1$，$\sum_{k=1}^n k=n(n+1)/2$。
3. 核心。 证明整数 $n\ge0$ 满足 $2^n\ge n+1$，并指出基础情形的作用。
4. 证明。 用强归纳证明每个整数 $n\ge2$ 都是素数的乘积。不要从这一证明声称分解唯一。

详解

1. 若两个整数为 $2r+1$ 和 $2s+1$，其和为 $2(r+s+1)$，是整数的两倍，故为偶数。
2. 当 $n=1$，$1=1\cdot2/2$。若公式在 $n$ 成立，下一项和为 $n(n+1)/2+(n+1)=(n+1)(n+2)/2$。归纳法给出所有 $n\ge1$ 的结论。
3. 当 $n=0$，$1=0+1$。若 $2^n\ge n+1$，则由于 $n\ge0$，有 $2^{n+1}\ge2(n+1)\ge n+2$。因此蕴含成立，而真的基础情形启动了归纳链；仅有蕴含不能证明任何特定情形。
4. 当 $n=2$，该数本身为素数。假设从 $2$ 到 $n-1$ 的所有整数都有该性质。若 $n$ 为素数，它本身是单因子的乘积；否则 $n=ab$，其中整数 $2\le a,b<n$。由假设两因子均为素数乘积，连接两个分解即得 $n$ 的分解。这里只证明存在；唯一性需要额外的整除论证。

总结与术语

见证实现存在性；唯一性排除不同候选对象。归纳假设只在归纳步骤内部用作条件假设。最小反例是良序下最小的不成立整数。选择方法前先写目标。基础情形、例外参数及必要与充分的区别都是论证本身，而非可有可无的说明。