5.1 数学归纳法

数学归纳法的原理

为证明对所有的正整数 \(n\)，\(P(n)\) 为真，其中 \(P(n)\) 是一个命题函数，需要完成两个步骤：

  • 基础步骤：证明命题 \(P(1)\) 为真。
  • 归纳步骤：证明对每个正整数 \(k\) 来说，蕴含式 \(P(k) \rightarrow P(k+1)\) 为真。

其中，\(P(k)\) 为真的假设叫作 归纳假设

奇数馅饼战斗

命题：在奇数馅饼战斗中，至少有一个人幸存下来。

这个命题的意思是，在有 \(2n + 1\) 个人（其中 \(n \geq 1\) ）的情况下，每个人向他们最近的邻居扔馅饼并击中对方，最终至少会有一个人没有被击中，从而幸存下来。

证明思路（数学归纳法）：

  1. 基础情况（Base Case）：

    当 \(n = 1\) 时，总共有 \(2(1) + 1 = 3\) 个人。这三个人之间的距离互不相同，因此每个人都有一个唯一的最近邻居。

    • 假设其中两个人互相是彼此的最近邻居（即他们互相攻击），那么这两个人会被击中并出局。
    • 第三个人的最近邻居只能是这两个人中的一个，因此他不会被击中，成为幸存者。

    因此，当 \(n = 1\) 时，命题成立。

  2. 归纳假设（Inductive Hypothesis）：

    假设当人数为 \(2k + 1\)（其中 \(k \geq 1\)）时，命题成立，即至少有一个人幸存下来。

  3. 归纳步骤（Inductive Step）：

    考虑人数为 \(2(k + 1) + 1 = 2k + 3\) 的情况。

    • 在这 \(2k + 3\) 个人中，总能找到一对互相是彼此最近邻居的人（因为他们互相攻击）。
    • 这两个人会被击中并出局，剩下 \(2k + 1\) 个人。
    • 根据归纳假设，剩下的 \(2k + 1\) 个人中至少有一个人幸存下来。
      因此，在 \(2k + 3\) 个人的情况下，命题也成立。

通过数学归纳法，可以证明对于所有 \(n \geq 1\)，奇数馅饼战斗中至少有一个人幸存下来。

固定规范：

  1. 将要证明的命题表达为形式：

"对于所有 \(n \geq b\)，\(P(n)\)"，其中 \(b\) 是一个固定的整数。

  1. 写出“基础步骤”：

然后证明 \(P(b)\) 是正确的，注意使用正确的 \(b\) 值。这完成了证明的第一部分。

  1. 写出“归纳步骤”：

  2. 陈述并明确指出归纳假设：

以形式 "假设对于任意固定的整数 \(k \geq b\)，\(P(k)\) 是正确的"。

  1. 陈述需要证明的内容：

在归纳假设成立的前提下，写出 \(P(k + 1)\) 的内容。

  1. 证明 \(P(k + 1)\)：

利用归纳假设 \(P(k)\) 来证明 \(P(k + 1)\)。确保证明对所有整数 \(k \geq b\) 有效，特别是对于较小的 \(k\) 值（包括 \(k = b\)）。

  1. 明确指出归纳步骤的结论：

例如，通过说明 "这完成了归纳步骤"。

  1. 完成基础步骤和归纳步骤后，陈述结论：

即通过数学归纳法，可以得出对于所有整数 \(n \geq b\)，\(P(n)\) 是正确的。