当可用的表示随奇偶、正负或其他有限分类而改变时，分类证明就派上用场。每个分支在原条件上增加一个分类假设，证明同一个目标。关键义务是覆盖全部允许的输入，而不是只讨论计算方便的情形 [1][1] Z. Abel, B. Chapman, and E. Demaine, “Lecture 03: Casework and Strong Induction,” 2024. MIT 6.1200J/18.062J, Mathematics for Computer Science; revised February 14, 2024. https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec03.pdf。

一次分类需要完成什么

设原题条件保证 C1,…,CrC_1,\ldots,C_r 至少有一个成立。如果在每个相应的分类假设下都能证明目标 QQ，就能在原条件下得到 QQ。完整证明因此需要说明分类为什么穷尽，完成每个分支，再合并结论。

各类不一定互斥。把实数分成 x≥0x\ge0 与 x≤0x\le0，虽然在零处重叠，仍然穷尽；分成 x>0x>0 与 x<0x<0 则漏掉了零。若证明的是条件命题，每个分支还要保留原题条件。例如，原题已要求 x≠0x\ne0 时，只讨论正、负两种情形就足够。

每个分支内部可以使用直接证明、反证，或者继续细分，但不能变成几个结论互不相关的问题。有限分类也可以覆盖无限多个对象，因为“nn 是偶数”这一类本身就代表了全部偶整数。

完整例子：奇偶性决定哪个因子有用

命题相邻整数的乘积为偶数

对每个整数 nn，乘积 n(n+1)n(n+1) 都是偶数。

证明

每个整数不是偶数就是奇数，所以下面两类穷尽全部情形。

若 nn 是偶数，写成 n=2kn=2k，其中 k∈Zk\in\mathbb Z。于是

n(n+1)=2(k(2k+1)).n(n+1)=2\bigl(k(2k+1)\bigr).

若 nn 是奇数，写成 n=2k+1n=2k+1，其中 k∈Zk\in\mathbb Z。于是

n(n+1)=2((2k+1)(k+1)).n(n+1)=2\bigl((2k+1)(k+1)\bigr).

两种情况的括号内都是整数，因此乘积为偶数。分类同时包含零和负整数。

这里分类有用，是因为它确定了哪个因子提供因子 22。练习时可以改变目标，并检查每次新的分类为什么没有遗漏。

余数分类也覆盖负整数

对任意整数 nn 和正整数 dd，带余除法给出 n=dk+rn=dk+r，其中 k,rk,r 为整数，且 0≤r<d0\le r<d。因此，dd 个余数类覆盖全部整数，包括负数。例如，−1=3(−1)+2-1=3(-1)+2 属于除以 33 余 22 的一类。

n−1,n,n+1n-1,n,n+1 中至少有一个数能被 33 整除：nn 余 00 时是 nn，余 11 时是 n−1n-1，余 22 时是 n+1n+1。这就补上了直接证明中使用的辅助事实。

不过，不是所有整除题都值得分类。三个连续整数之和直接等于

n+(n+1)+(n+2)=3(n+1).n+(n+1)+(n+2)=3(n+1).

一个统一恒等式已经覆盖全部输入，分类虽然也能证明，却没有带来有用的信息。应当在各分支确实揭示不同结构时使用分类。

边界与对称性

例绝对值的定义在零处分段

证明对每个实数 xx，都有 ∣x∣≥x|x|\ge x。若 x≥0x\ge0，则 ∣x∣=x|x|=x；若 x<0x<0，则 ∣x∣=−x>x|x|=-x>x，因为 −2x>0-2x>0。两类覆盖所有实数，且等号恰在 x≥0x\ge0 时成立。

“不妨设”需要保持题设与目标的对称性支持。例如，已知整数 a,ba,b 至少一个为偶数，要证 abab 为偶数，可以把偶数因子叫作 aa，因为交换名称不改变假设和乘积。但面对 a<ba<b 这样的非对称条件，不能不检查条件如何变化就直接交换名称。

练习

练习平方除以三的余数

证明整数的平方除以 33，余数只能是 00 或 11。

查看解析
解

写成 n=3k+rn=3k+r，其中 r∈{0,1,2}r\in\{0,1,2\}。于是 n2=3(3k2+2kr)+r2n^2=3(3k^2+2kr)+r^2。三个 rr 对应的 r2r^2 为 0,1,40,1,4，余数分别为 0,1,10,1,1。分类的穷尽性来自带余除法。

练习先检查命题，再尝试证明

原笔记要求按奇偶分类证明：对每个整数 n>1n>1，n2+4n^2+4 都是合数。判断真假；若为假，给出一个成立的受限版本。

查看解析
解

n=3n=3 时结果为素数 1313，所以原断言为假。若限制 n>1n>1 为偶数，写成 n=2kn=2k，其中 k≥1k\ge1，则 n2+4=4(k2+1)n^2+4=4(k^2+1)，是两个大于一的整数之积，因而是合数。原来的奇数情形还使用了错误分解：(2k+1)2+4=4k2+4k+5(2k+1)^2+4=4k^2+4k+5，但 (2k+1)(2k+3)=4k2+8k+3(2k+1)(2k+3)=4k^2+8k+3。

练习区分多个证明目标与输入分类

证明对每个整数 nn，都有 30∣n5−n30\mid n^5-n。可使用“两两互素的 2,3,52,3,5 都整除一个整数，则其乘积也整除该整数”这一事实。三个整除要求都是需要完成的目标，不是三种择一讨论的输入情形。

查看解析
解

对除数 22，余数代表 r=0,1r=0,1 都使 r5−rr^5-r 被 22 整除。对除数 33，使用代表 r=0,1,−1r=0,1,-1，均有 r5−r=0r^5-r=0。对除数 55，使用 r=0,1,−1,2,−2r=0,1,-1,2,-2，对应值为 0,0,0,30,−300,0,0,30,-30，都能被 55 整除。

这些检查可以从代表 rr 转到原整数 nn，因为只要 d∣n−rd\mid n-r，恒等式

n5−r5=(n−r)(n4+n3r+n2r2+nr3+r4)n^5-r^5=(n-r)(n^4+n^3r+n^2r^2+nr^3+r^4)

就说明 d∣n5−r5d\mid n^5-r^5。因此 n5−nn^5-n 与 r5−rr^5-r 同余。三个整除目标都已建立，再由题目给出的互素事实得到 30∣n5−n30\mid n^5-n。非互素除数不能直接这样相乘，例如 2∣42\mid4、4∣44\mid4，却没有 8∣48\mid4。

练习写清分段表达式

对实数 xx，在绝对值内部表达式变号的位置分类，求出 ∣x−1∣+∣x+1∣|x-1|+|x+1|。

查看解析
解

分成 x<−1x<-1、−1≤x≤1-1\le x\le1、x>1x>1 三类，对应结果分别为 −2x-2x、22、2x2x：

∣x−1∣+∣x+1∣={−2x,x<−1,2,−1≤x≤1,2x,x>1.|x-1|+|x+1|= \begin{cases} -2x,&x<-1,\\ 2,&-1\le x\le1,\\ 2x,&x>1. \end{cases}

中间一类包含两个边界点，相邻公式在边界上也一致。各分支按内部表达式的正负去掉绝对值即可得到。

接下来怎样选方法

好的分类有明确的穷尽理由，并为每个分支提供有用的新信息。如果结论的否定比原输入的分类更容易使用，可以进入间接证明；如果命题按自然数规模排列，小规模结论能支持更大规模，就需要数学归纳法的原理。

参考文献

  1. [1] Z. Abel, B. Chapman, and E. Demaine, “Lecture 03: Casework and Strong Induction,” 2024. MIT 6.1200J/18.062J, Mathematics for Computer Science; revised February 14, 2024. https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec03.pdf ↩