第42章 数学归纳法原理

数学归纳法原理

命题序列

关于自然数的命题常可以看作命题序列 \(P_{n}\)。

例 42.1 命题”前 \(n\) 个自然数之和等于 \(\dfrac{n(n+1)}{2}\)“可写为

\[P_{n}:\quad 1+2+3+\cdots+n=\frac{n(n+1)}{2}\qquad\text{即}\qquad P_{n}:\quad\sum_{k=1}^{n}k=\frac{n(n+1)}{2}\]

则 \(P_{1}\) 为命题 \(1=\dfrac{1\cdot2}{2}\)，\(P_{2}\) 为命题 \(1+2=\dfrac{2\cdot3}{2}\)，以此类推。

例 42.2 命题”对每个自然数 \(n\)，\(n^{2}-n+41\) 是质数”可写为 \(P_{n}:\ n^{2}-n+41\) 是质数。

数学归纳法原理（PMI）

对于关于自然数的命题序列 \(P_{n}\)，如果以下条件成立：

1. \(P_{1}\) 为真。
2. 只要 \(P_{k}\) 为真，则 \(P_{k+1}\) 也为真。

则 \(P_{n}\) 对所有 \(n\) 都成立。

数学归纳法证明步骤

要对命题序列 \(P_{n}\) 应用数学归纳法：

1. 写出 \(P_{1}\)、\(P_{k}\)、\(P_{k+1}\) 的具体形式。
2. 证明 \(P_{1}\) 为真。
3. 假设 \(P_{k}\) 为真（归纳假设，无需证明），从该假设出发，证明 \(P_{k+1}\) 也为真（归纳步骤）。
4. 结论：\(P_{n}\) 对所有 \(n\) 成立。

归纳法证明失败的情形

命题序列可能只对部分 \(n\) 值成立，或对所有 \(n\) 均不成立，此时数学归纳法不适用，证明将会失败。

例 42.3 在例 42.2 中，\(P_{1}\) 至 \(P_{40}\) 均为真，但 \(P_{41}\) 为”\(41^{2}-41+41=41^{2}\) 是质数”，这显然为假。故该命题序列一般为假，尽管部分命题为真。

扩展数学归纳法原理

若存在自然数 \(m\)，使命题序列 \(P_{n}\) 对所有 \(n \geq m\) 均可能成立，则可使用扩展数学归纳法：若以下条件成立：

1. \(P_{m}\) 为真。
2. 只要 \(P_{k}\) 为真，则 \(P_{k+1}\) 也为真。

则 \(P_{n}\) 对所有 \(n \geq m\) 成立。

例 42.4 设 \(P_{n}\) 为命题 \(n! \geq 2^{n}\)。\(P_{1}\)，\(P_{2}\)，\(P_{3}\) 均为假，但 \(P_{4}\) 为真（\(24 \geq 16\)），由扩展数学归纳法可证 \(P_{n}\) 对所有 \(n \geq 4\) 成立。

已解例题

42.1 用数学归纳法证明 \(P_{n}:\ 1+2+3+\cdots+n=\dfrac{n(n+1)}{2}\)。

• \(P_{1}\)：\(1=\dfrac{1\cdot2}{2}=1\)，为真。
• 假设 \(P_{k}\)：\(1+2+\cdots+k=\dfrac{k(k+1)}{2}\) 成立。
• 要证 \(P_{k+1}\)：\(1+2+\cdots+k+(k+1)=\dfrac{(k+1)(k+2)}{2}\)。
• 由 \(P_{k}\) 两边加 \((k+1)\)：

\[1+2+\cdots+k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+1)(k+2)}{2}\]

这正是 \(P_{k+1}\)，故由数学归纳法，\(P_{n}\) 对所有 \(n\) 成立。

42.2 用数学归纳法证明 \(P_{n}:\ 1+3+5+\cdots+(2n-1)=n^{2}\)。

• \(P_{1}\)：\(1=1^{2}\)，为真。
• 假设 \(P_{k}\)：\(1+3+\cdots+(2k-1)=k^{2}\) 成立。
• 要证 \(P_{k+1}\)：\(1+3+\cdots+(2k-1)+(2k+1)=(k+1)^{2}\)。
• 由 \(P_{k}\) 两边加 \((2k+1)\)：

\[k^{2}+(2k+1)=(k+1)^{2}\]

这正是 \(P_{k+1}\)，故 \(P_{n}\) 对所有 \(n\) 成立。

42.3 用数学归纳法证明 \(P_{n}:\ 1+2+2^{2}+\cdots+2^{n-1}=2^{n}-1\)。

• \(P_{1}\)：\(1=2^{1}-1=1\)，为真。
• 假设 \(P_{k}\) 成立，由 \(P_{k}\) 两边加 \(2^{k}\)：

\[1+2+\cdots+2^{k-1}+2^{k}=(2^{k}-1)+2^{k}=2\cdot2^{k}-1=2^{k+1}-1\]

这正是 \(P_{k+1}\)，故 \(P_{n}\) 对所有 \(n\) 成立。

42.4 用数学归纳法证明 \(P_{n}:\ \displaystyle\sum_{j=1}^{n}j^{2}=\dfrac{n(n+1)(2n+1)}{6}\)。

• \(P_{1}\)：\(1^{2}=\dfrac{1\cdot2\cdot3}{6}=1\)，为真。
• 假设 \(P_{k}\) 成立，由 \(P_{k}\) 两边加 \((k+1)^{2}\)：

\[\begin{aligned}\frac{k(k+1)(2k+1)}{6}+(k+1)^{2}&=\frac{k(k+1)(2k+1)+6(k+1)^{2}}{6}\\&=\frac{(k+1)[k(2k+1)+6(k+1)]}{6}\\&=\frac{(k+1)(2k^{2}+7k+6)}{6}\\&=\frac{(k+1)(k+2)(2k+3)}{6}\end{aligned}\]

这正是 \(P_{k+1}\)，故 \(P_{n}\) 对所有 \(n\) 成立。

42.5 用数学归纳法证明对任意正整数 \(n\)，有 \(n < 2^{n}\)。

• \(P_{1}\)：\(1 < 2\)，为真。
• 假设 \(P_{k}\)：\(k < 2^{k}\) 成立，两边乘以 2：\(2k < 2^{k+1}\)。
• 由于 \(2k = k+k \geq k+1\)，故 \(2^{k+1} > 2k \geq k+1\)，即 \(P_{k+1}\) 成立。

42.6 用扩展数学归纳法证明对任意整数 \(n \geq 4\)，有 \(n! > 2^{n}\)。

• \(P_{4}\)：\(4! = 24 > 16 = 2^{4}\)，为真。
• 假设 \(P_{k}\) 成立，两边乘以 \(k+1\)：\(1\cdot2\cdots k\cdot(k+1) > 2^{k}(k+1)\)。
• 由于 \(k > 1\)，故 \(k+1 > 2\)，从而 \(2^{k}(k+1) > 2^{k}\cdot2 = 2^{k+1}\)，即 \(P_{k+1}\) 成立。

42.7 用数学归纳法证明对任意正整数 \(n\)，\((x-y)\) 是 \(x^{n}-y^{n}\) 的因子。

• \(P_{1}\)：\(x-y\) 是 \(x-y\) 的因子，为真。
• 假设 \(P_{k}\) 成立：\(x^{k}-y^{k}=(x-y)Q(x)\)。则

\[\begin{aligned}x^{k+1}-y^{k+1}&=x^{k+1}-xy^{k}+xy^{k}-y^{k+1}\\&=x(x^{k}-y^{k})+y^{k}(x-y)\\&=x(x-y)Q(x)+y^{k}(x-y)\\&=(x-y)[xQ(x)+y^{k}]\end{aligned}\]

这正是 \(P_{k+1}\)，故 \(P_{n}\) 对所有正整数 \(n\) 成立。

42.8 用数学归纳法证明 De Moivre 定理：若 \(z=r(\cos\theta+i\sin\theta)\) 是三角形式的复数，则对任意正整数 \(n\)，

\[z^{n}=r^{n}(\cos n\theta+i\sin n\theta)\]

• \(P_{1}\) 显然为真。
• 假设 \(P_{k}\) 成立，两边乘以 \(z=r(\cos\theta+i\sin\theta)\)：

\[z^{k+1}=r\cdot r^{k}(\cos\theta+i\sin\theta)(\cos k\theta+i\sin k\theta)\]

由复数三角形式的乘法规则：

\[(\cos\theta+i\sin\theta)(\cos k\theta+i\sin k\theta)=\cos(k+1)\theta+i\sin(k+1)\theta\]

故 \(z^{k+1}=r^{k+1}[\cos(k+1)\theta+i\sin(k+1)\theta]\)，即 \(P_{k+1}\) 成立。

补充练习

42.9 用数学归纳法证明：\(2+4+6+\cdots+2n=n(n+1)\)。

42.10 用数学归纳法证明：\(3+7+11+\cdots+(4n-1)=n(2n+1)\)。

42.11 用数学归纳法证明：\(1+3+3^{2}+\cdots+3^{n-1}=\dfrac{3^{n}-1}{2}\)。

42.12 用数学归纳法证明：\(1^{3}+2^{3}+3^{3}+\cdots+n^{3}=\dfrac{n^{2}(n+1)^{2}}{4}\)。

42.13 由第 42.1 和 42.12 题推出 \(\displaystyle\sum_{k=1}^{n}k^{3}=\left(\sum_{k=1}^{n}k\right)^{2}\)。

42.14 用数学归纳法证明：\(\dfrac{1}{1\cdot3}+\dfrac{1}{3\cdot5}+\dfrac{1}{5\cdot7}+\cdots+\dfrac{1}{(2n-1)(2n+1)}=\dfrac{n}{2n+1}\)。

42.15 用扩展数学归纳法证明：\(\dfrac{1}{\sqrt{1}}+\dfrac{1}{\sqrt{2}}+\dfrac{1}{\sqrt{3}}+\cdots+\dfrac{1}{\sqrt{n}}>\sqrt{n}\)，\(n\geq2\)。

42.16 用数学归纳法证明：对任意正整数 \(n\)，\((x+y)\) 是 \(x^{2n-1}+y^{2n-1}\) 的因子。