知识焦点
先建立概念地图
- 数学归纳法
- 强归纳法
- 伯努利不等式
- 二进制表示
- 斐波那契数列
CS70 · 讨论课 01a
本讨论课围绕数学归纳法，包含四道题目：伯努利不等式的归纳证明、通过加强归纳假设完成数列不等式证明、用强归纳法证明任意正整数存在二进制表示，以及证明斐波那契数列中每第三个数为偶数。
知识焦点
建议顺序
先完整作答，再按需展开提示；最后才展开官方参考解答并逐步核对证明与计算。
本地来源
题面与解答均由本地一手资料整理：discussion/dis01a.pdf、solutions/discussion/dis01a-sol.pdf
本地一手资料完整提取 · 讨论课
本节按本地一手资料完整整理，共 4 道大题。本地官方解答已完整收录并默认折叠；建议先独立完成，再逐题核对推导。
discussion/dis01a.pdf、solutions/discussion/dis01a-sol.pdf证明：若 \(n \in \mathbb{N}\) 且 \(x > 0\)，则 \((1 + x)^n \geq 1 + nx\)。
考虑对 \(n\) 使用数学归纳法。在归纳步骤中，将 \((1+x)^{k+1}\) 拆分为 \((1+x)^k(1+x)\)，然后利用归纳假设放缩，并注意 \(x>0\) 时 \(kx^2 \geq 0\)。自检：基础情形是否覆盖了 \(n=0\)？
解答：
• 基础情形（Base Case）：当 \(n = 0\) 时，\((1 + x)^0 = 1 \geq 1 + 0 \cdot x = 1\)，命题成立。
• 归纳假设（Inductive Hypothesis）：假设当 \(n = k\)（其中 \(k \in \mathbb{N}\)）时命题成立，即 \((1 + x)^k \geq 1 + kx\)。
• 归纳步骤（Inductive Step）：当 \(n = k + 1\) 时， \[ \begin{aligned} (1 + x)^{k+1} &= (1 + x)^k(1 + x) \\ &\geq (1 + kx)(1 + x) \\ &= 1 + kx + x + kx^2 \\ &= 1 + (k + 1)x + kx^2 \\ &\geq 1 + (k + 1)x. \end{aligned} \]
由数学归纳法可知，对任意 \(n \in \mathbb{N}\)，均有 \((1 + x)^n \geq 1 + nx\)。
解答来源：solutions/discussion/dis01a-sol.pdf · 1 · confidence: high
题面来源：discussion/dis01a.pdf · 1 · confidence: high
设数列 \(a_1, a_2, \ldots\) 满足 \(a_1 = 1\)，且对 \(n \geq 1\) 有 \(a_{n+1} = 3a_n^2\)。我们希望证明：对每个正整数 \(n\)，都有 \(a_n \leq 3^{(2^n)}\)。
(a) 若想用数学归纳法证明原命题，能否直接取归纳假设为 \(a_n \leq 3^{(2^n)}\)？尝试用这个假设完成一次归纳推理，说明为什么它行不通。
(b) 改用归纳法证明加强命题 \(a_n \leq 3^{(2^n - 1)}\)。
(c) 第 (b) 部分的结论为什么能推出原命题？
(a) 将递推关系 \(a_{n+1} = 3a_n^2\) 代入假设后，比较所得结果与目标在指数上的差距，思考为何归纳步骤无法闭合。(b) 若原假设过弱无法闭合，尝试寻找一个更强的命题，使归纳步骤恰好能递推下去。自检：比较 \(3^{(2^n - 1)}\) 与 \(3^{(2^n)}\) 的大小关系，思考加强后的命题为何能推出原命题。
(a) 尝试用归纳法证明：对每个 \(n \geq 1\)，有 \(a_n \leq 3^{2^n}\)。
基础情形：当 \(n = 1\) 时，\(a_1 = 1 \leq 3^{2^1} = 9\)，成立。
归纳步骤：对某个 \(n \geq 1\)，假设 \(a_n \leq 3^{2^n}\)。考虑 \(n + 1\)： \[a_{n+1} = 3a_n^2 \leq 3(3^{2^n})^2 = 3 \times 3^{2 \times 2^n} = 3 \times 3^{2^{n+1}} = 3^{2^{n+1} + 1}.\] 然而我们希望得到的是 \(a_{n+1} \leq 3^{2^{n+1}}\)。所推结果的指数上多了一个 \(+1\)，归纳步骤无法闭合。
(b) 这次归纳成立。
基础情形：当 \(n = 1\) 时，\(a_1 = 1 \leq 3^{2^1 - 1} = 3^1 = 3\)，成立。
归纳步骤：对某个 \(n \geq 1\)，假设 \(a_n \leq 3^{2^n - 1}\)。考虑 \(n + 1\)： \[a_{n+1} = 3a_n^2 \leq 3 \times (3^{2^n - 1})^2 = 3 \times 3^{2(2^n - 1)} = 3 \times 3^{2^{n+1} - 2} = 3^{2^{n+1} - 1}.\] 这恰好是 \(n + 1\) 对应的归纳命题。
(c) 对每个 \(n \geq 1\)，有 \(2^n - 1 \leq 2^n\)，因此 \(3^{2^n - 1} \leq 3^{2^n}\)。这说明第 (b) 部分证明的加强假设确实能推出第 (a) 部分想证的原命题。
解答来源：solutions/discussion/dis01a-sol.pdf · 1 · confidence: high
题面来源：discussion/dis01a.pdf · 1 · confidence: high
证明：每个正整数 \(n\) 都可以写成二进制形式。换言之，证明我们可以将 \(n\) 写成 \[ n = c_k \cdot 2^k + c_{k-1} \cdot 2^{k-1} + \cdots + c_1 \cdot 2^1 + c_0 \cdot 2^0, \] 其中 \(k \in \mathbb{N}\)，且对所有 \(i \leq k\) 有 \(c_i \in \{0, 1\}\)。
本题适合用强归纳法（strong induction）。关键观察：若 \(n+1\) 是偶数，可先对 \((n+1)/2\) 使用归纳假设再整体乘以 2；若 \(n+1\) 是奇数，则 \(n\) 为偶数，可在 \(n\) 的二进制末尾将 0 改为 1。自检：两种情形是否都恰好得到 \(n+1\) 的二进制表示？
对 \(n\) 使用强归纳法证明。
核心思路：若 \(n\) 能被 2 整除，则由 \(n\) 的二进制可方便地得到 \(n+1\) 的二进制；若 \(n\) 不能被 2 整除，则 \(n+1\) 能被 2 整除，此时由 \((n+1)/2\) 的二进制更方便推出 \(n+1\) 的二进制。具体地：
• 基础情形：\(n = 1\) 可写成 \(1 \times 2^0\)。
• 归纳步骤：假设命题对所有 \(1 \leq m \leq n\) 成立，其中 \(n\) 任意。考虑 \(n+1\)：
若 \(n+1\) 能被 2 整除，则对 \((n+1)/2\) 使用归纳假设： \[(n+1)/2 = c_k \cdot 2^k + c_{k-1} \cdot 2^{k-1} + \cdots + c_1 \cdot 2^1 + c_0 \cdot 2^0,\] 两边同乘 2 得 \[n+1 = c_k \cdot 2^{k+1} + c_{k-1} \cdot 2^k + \cdots + c_1 \cdot 2^2 + c_0 \cdot 2^1 + 0 \cdot 2^0.\]
否则 \(n\) 能被 2 整除，故 \(c_0 = 0\)，由 \(n\) 的表示可得： \[n = c_k \cdot 2^k + c_{k-1} \cdot 2^{k-1} + \cdots + c_1 \cdot 2^1 + 0 \cdot 2^0,\] \[n+1 = c_k \cdot 2^k + c_{k-1} \cdot 2^{k-1} + \cdots + c_1 \cdot 2^1 + 1 \cdot 2^0.\]
因此命题成立。
另解（模拟十进制转二进制算法）：
• 基础情形：\(n = 1\) 可写成 \(1 \times 2^0\)。
• 归纳步骤：假设命题对所有 \(1 \leq m \leq n\) 成立。设 \(2^m\) 是满足 \(n+1 \geq 2^m\) 的 2 的最大幂次，则 \(n+1 < 2^{m+1}\)。考察 \((n+1) - 2^m\)。由于 \((n+1) - 2^m < n+1\)，由归纳假设它有二进制表示；又因为 \(n+1 < 2^{m+1}\)，所以 \((n+1) - 2^m < 2^m\)，其表示中 2 的最高幂次为 \(2^{m-1}\)。因此 \[(n+1) - 2^m = c_{m-1} \cdot 2^{m-1} + c_{m-2} \cdot 2^{m-2} + \cdots + c_1 \cdot 2^1 + c_0 \cdot 2^0,\] 两边加上 \(2^m\) 得 \[n+1 = 2^m + c_{m-1} \cdot 2^{m-1} + c_{m-2} \cdot 2^{m-2} + \cdots + c_1 \cdot 2^1 + c_0 \cdot 2^0,\] 即为 \(n+1\) 的二进制表示。归纳完成。
注：在简单归纳法中，我们仅用 \(P(n)\) 来证明 \(P(n+1)\)。这里简单归纳之所以受阻，是因为在归纳步骤中，特别是在 \(n+1\) 能被 2 整除的情形下，仅凭 \(P(n)\) 不易直接得到 \(P(n+1)\) 的表示。因此我们假设命题对 \(1, 2, \ldots, n\) 全部成立，以证明 \(P(n+1)\)。
解答来源：solutions/discussion/dis01a-sol.pdf · 2 · confidence: high
题面来源：discussion/dis01a.pdf · 2 · confidence: high
回顾斐波那契数列（Fibonacci numbers）的定义：\(F_1 = 1\)，\(F_2 = 1\)，且 \(F_n = F_{n-2} + F_{n-1}\)。
证明：每第三个斐波那契数都是偶数。例如，\(F_3 = 2\) 是偶数，\(F_6 = 8\) 是偶数。
目标是证明对所有 \(k \geq 1\)，\(F_{3k}\) 为偶数。在归纳步骤中，将 \(F_{3k+3}\) 逐步展开为 \(F_{3k}\) 与 \(F_{3k+1}\) 的组合，利用归纳假设 \(F_{3k} = 2q\) 提取公因子 2。自检：展开后系数是否保证了结果必为偶数？
我们要证明：对所有自然数 \(k \geq 1\)，\(F_{3k}\) 是偶数。
基础情形 \(k = 1\)：\(F_3 = 2\) 是偶数，显然成立。
归纳步骤：由 \[F_{3k+3} = F_{3k+2} + F_{3k+1} = 2F_{3k+1} + F_{3k}.\] 由归纳假设，\(F_{3k} = 2q\)（\(q\) 为某整数），于是 \[F_{3k+3} = 2(F_{3k+1} + q),\] 这表明 \(F_{3k+3}\) 是偶数。由数学归纳法知，所有 \(F_{3k}\) 均为偶数。
解答来源：solutions/discussion/dis01a-sol.pdf · 3 · confidence: high
题面来源：discussion/dis01a.pdf · 2 · confidence: high
discussion/dis01a.pdfsolutions/discussion/dis01a-sol.pdf