分类讨论证明把假设拆成若干个覆盖全部可能性的情形，然后在每个情形中分别证明结论。每个分支内部仍然可以使用直接证明、反证法或其他方法。

关键要求是完备性：所有允许的输入都必须落在至少一个情形中。情形之间有重叠并不致命，但遗漏可能性会让证明不完整。

例三个连续整数

证明任意三个连续整数之和都能被 33 整除。

证明

把三个整数写成 n,n+1,n+2n,n+1,n+2。任意整数都具有 3k3k、3k+13k+1 或 3k+23k+2 的形式。

  • 若 n=3kn=3k，总和为 9k+3=3(3k+1)9k+3=3(3k+1)。
  • 若 n=3k+1n=3k+1，总和为 9k+6=3(3k+2)9k+6=3(3k+2)。
  • 若 n=3k+2n=3k+2，总和为 9k+9=3(3k+3)9k+9=3(3k+3)。

三种情形都得到 33 的倍数，因此结论成立。

练习相邻整数的乘积

证明对任意整数 nn，n(n+1)n(n+1) 都是偶数。

解

如果 nn 是偶数，乘积含有偶因子。如果 nn 是奇数，那么 n+1n+1 是偶数。这两种情形覆盖所有整数，所以 n(n+1)n(n+1) 总是偶数。

注先检查命题本身

原项目还提出过“当 n>1n>1 时，n2+4n^2+4 不可能是素数”。这个命题是假的，因为 n=3n=3 时 n2+4=13n^2+4=13，而 1313 是素数。草稿中的分解

(2k+1)2+4=(2k+1)(2k+3)(2k+1)^2+4=(2k+1)(2k+3)

也不成立。这说明发表证明前，应先检查代数变形，并用小规模例子测试命题。

当分类来自定义本身时，分类讨论最自然，例如奇偶性或模某个整数的剩余类。