§1
数学命题的价值在于它被证明。离散数学是训练证明技术最合适的场地：对象有限可数，推理链条清晰，各类证明范式在这里都能找到最朴素的例子。本章系统整理五种基本方法——直接证明、反证法、数学归纳法（第一与第二形式）、构造法与鸽笼法，并强调"什么时候该用哪一种"。
一、命题的形态与证明目标
绝大多数待证命题形如
$$\forall x\in D,\ P(x)\to Q(x),$$
即"在论域 $D$ 中，只要前提 $P$ 成立，结论 $Q$ 就成立"。证明就是给出一条从公理、定义与已知定理出发、逐步合乎逻辑的推理链，最终抵达 $Q$。
反过来，否定一个全称命题只需一个反例：$\lnot\forall x\,P(x)\equiv\exists x\,\lnot P(x)$。例如"所有素数都是奇数"被 $2$ 一举推翻。
二、直接证明
方法. 假设 $P(x)$ 成立，展开定义、代数变形，直到导出 $Q(x)$。
例. 若 $n$ 为奇数，则 $n^{2}$ 为奇数。
证：由定义存在整数 $k$ 使 $n=2k+1$，于是
$$n^{2}=(2k+1)^{2}=4k^{2}+4k+1=2(2k^{2}+2k)+1,$$
括号内为整数，故 $n^{2}$ 形如 $2m+1$，为奇数。
直接证明的关键动作只有两个：把定义写成等式、把等式凑成目标形状。
三、反证法与逆否证明
逆否证明. 利用 $p\to q\equiv\lnot q\to\lnot p$，改证"若结论不成立则前提不成立"。当 $\lnot q$ 比 $p$ 更容易展开时特别有效。例如证"若 $n^{2}$ 为偶数则 $n$ 为偶数"，直接从 $n^2$ 偶不好下手，改证"$n$ 奇 $\Rightarrow n^2$ 奇"即上一节结论。
反证法（归谬）. 欲证 $S$，先假设 $\lnot S$，推出矛盾，从而 $\lnot S$ 不成立、$S$ 成立。
定理. $\sqrt2$ 是无理数。
证：假设 $\sqrt2=p/q$，其中 $p,q$ 为互素整数、$q\ne0$。两边平方得 $p^{2}=2q^{2}$，故 $p^{2}$ 为偶数，由上段结论 $p$ 为偶数，设 $p=2r$，代入得 $4r^{2}=2q^{2}$，即 $q^{2}=2r^{2}$，于是 $q$ 也是偶数。这与 $p,q$ 互素矛盾。故假设不成立，$\sqrt2$ 无理。
四、数学归纳法
第一数学归纳法. 设 $P(n)$ 是关于正整数 $n$ 的命题。若
1. 基础步：$P(n_{0})$ 成立；
2. 归纳步：对任意 $k\ge n_{0}$，由 $P(k)$ 可推出 $P(k+1)$，
则对一切 $n\ge n_{0}$，$P(n)$ 成立。
直观上这是多米诺骨牌：第一张倒下，且每一张倒下都会推倒下一张。
第二数学归纳法（强归纳）. 把归纳假设加强为"$P(n_{0}),P(n_{0}+1),\dots,P(k)$ 全部成立"，再推 $P(k+1)$。当 $P(k+1)$ 依赖的不只是紧邻的前一项时必须用它。
应用. 每个大于 $1$ 的整数都能写成素数之积。证：设 $n>1$，若 $n$ 是素数则本身即为乘积；否则 $n=ab$，$1形式 归纳假设 典型场景 第一归纳 仅 $P(k)$ 求和公式、不等式、递推一阶依赖 第二归纳 $P(n_0)$ 到 $P(k)$ 全部 素因子分解、斐波那契、良基递归
五、构造法与鸽笼法
构造法. 证明"存在某对象"最直接的方式是把它造出来。例如"存在任意长的连续合数段"：取
$$(n+1)!+2,\ (n+1)!+3,\ \dots,\ (n+1)!+(n+1),$$
第 $i$ 个数被 $i$ 整除且大于 $i$，故全为合数，长度为 $n$。
鸽笼原理（抽屉原理）. 把 $n+1$ 只鸽子放进 $n$ 个笼子，必有一个笼子装了至少两只。推广形式：把 $N$ 个物体放入 $k$ 个盒子，必有盒子含至少 $\lceil N/k\rceil$ 个物体。它是非构造性存在证明的典范——断言存在却不指出是哪一个。第三章还会详细展开。
六、例题与解答
例题1（归纳法证求和公式）
证明对一切正整数 $n$，
$$1+2+\cdots+n=\frac{n(n+1)}{2}.$$
解： 记 $S(n)$ 为左端。
基础步. $n=1$ 时左端 $=1$，右端 $=\dfrac{1\cdot2}{2}=1$，成立。
归纳步. 设 $n=k$ 时成立，即 $S(k)=\dfrac{k(k+1)}{2}$。则
$$ \begin{align*} S(k+1)&=S(k)+(k+1)\\ &=\frac{k(k+1)}{2}+(k+1)\\ &=(k+1)\left(\frac{k}{2}+1\right)\\ &=\frac{(k+1)(k+2)}{2}, \end{align*} $$
恰为公式在 $n=k+1$ 时的形式。由归纳原理，对一切 $n\ge1$ 成立。
数值校验：$n=10$ 时左端 $1+2+\cdots+10=55$，右端 $\dfrac{10\cdot11}{2}=55$。✓
例题2（归纳法证不等式）
证明对一切正整数 $n$ 有 $2^{n}>n$。
解：
基础步. $n=1$：$2^{1}=2>1$，成立。
归纳步. 设 $2^{k}>k$（$k\ge1$）。则
$$2^{k+1}=2\cdot2^{k}>2k=k+k\ge k+1,$$
最后一步用到 $k\ge1$。故 $2^{k+1}>k+1$。
由归纳原理结论对一切 $n\ge1$ 成立。数值校验：$n=5$ 时 $32>5$，$n=10$ 时 $1024>10$。✓ 注意归纳步中"$k\ge1$"这个条件不可省，否则 $k+k\ge k+1$ 不成立。
练习
1. 用直接证明说明两个奇数之和为偶数；再用反证法证明不存在最大的素数。
2. 用归纳法证明 $1^{2}+2^{2}+\cdots+n^{2}=\dfrac{n(n+1)(2n+1)}{6}$。
3. 说明为什么"每个大于 $1$ 的整数可分解为素数之积"需要第二归纳法而非第一归纳法。
参考答案.
1. 设 $m=2a+1,\ n=2b+1$，则 $m+n=2(a+b+1)$，为偶数。反证：假设素数只有有限个 $p_{1},\dots,p_{r}$，令 $N=p_{1}p_{2}\cdots p_{r}+1$，$N$ 被任一 $p_{i}$ 除余 $1$，故其素因子不在列表中，与"列举完毕"矛盾。
2. 基础步 $n=1$：左 $=1$，右 $=\dfrac{1\cdot2\cdot3}{6}=1$。归纳步：$\dfrac{k(k+1)(2k+1)}{6}+(k+1)^{2}=\dfrac{(k+1)(2k^{2}+7k+6)}{6}=\dfrac{(k+1)(k+2)(2k+3)}{6}$，正是 $n=k+1$ 的形式。
3. 因为 $n=ab$ 中的因子 $a,b$ 一般远小于 $n-1$，归纳假设必须覆盖 $2$ 到 $k$ 的全部整数，只假设 $P(k)$ 无法使用。
本章小结
- 直接证明：展开定义、代数变形、凑出目标形状。
- 逆否证明与反证法适用于结论的否定更易操作的场合，$\sqrt2$ 无理是经典范例。
- 第一归纳法有基础步与归纳步两部分，缺一不可。
- 第二归纳法把假设加强到全部前项，适用于分解型、递归依赖多项的命题。
- 构造法给出显式对象；鸽笼法给出非构造性的存在保证。
- 否定全称命题只需一个反例。
本章互动演示见页面底部交互图（归纳求和过程可视化 inductionViz）。
互动演示
拖动下方控件观察动态过程。