CS 70 Disc 01A

1. 自然数归纳法证明不等式

命题：如果 $ n $ 且 $ x > 0 $，则 \((1+x)^n \geq 1 + nx\)。

证明过程：

  • 基础案例：当 $ n = 0 $ 时，\((1+x)^0 \geq 1 + 0x\) 成立。

  • 归纳假设：假设对于某个 $ n = k $（其中 $ k \(），\)(1+x)^k + kx$ 成立。

  • 归纳步骤：对于 $ n = k + 1 \(：\) (1+x)^{k+1} = (1+x)^k (1+x) $ 根据归纳假设： $ (1+kx)(1+x) $ 展开右侧： $ + kx + x + kx^2 $ 整理得： $ + (k + 1)x + kx^2 $ 由于 $ kx^2 \(，可以得出：\) (1+x)^{k+1} + (k + 1)x $

由归纳法，我们证明了对于所有 $ n \(，\)(1+x)^n + nx$ 成立。

2. 使其更强

命题：考虑数列 $ a_1, a_2, $，定义为 $ a_1 = 1 $ 且 $ a_{n+1} = 3a_n^2 $ 对于 $ n $。我们想证明 $ a_n (2^n) $ 对于所有正整数 $ n $。

(a) 使用归纳法尝试证明 $ a_n (2^n) $

基础案例：对于 $ n = 1 $，有 $ a_1 = 1 (2^1) = 6 $。

归纳步骤：假设对于某个 $ n $ ，假设 $ a_n (2^n) $。

现在考虑 $ n + 1 \(：\) a_{n+1} = 3a_n^2 (3(2n))2 = 3 ^n = 27 ^{2n} $ 我们希望得到的是 $ a_{n+1} (2^{n+1}) $，但这里得到了 $ 27 ^{2n} $，这比所需的 $ 6 ^{n+1} $ 要强，因此这种归纳假设失败了。

(b) 尝试证明 $ a_n (2^{n-1}) $

基础案例：对于 $ n = 1 $，有 $ a_1 = 1 (2^{0}) = 3 $。

归纳步骤：假设对于某个 $ n $ 有 $ a_n (2^{n-1}) $。

考虑 $ n + 1 \(：\) a_{n+1} = 3a_n^2 (3(2{n-1}))2 = 3 ^{n-1} = 27 ^{2(n-1)} $ 我们希望证明： $ a_{n+1} (2^n) $ 从而得到： $ 27 ^{2(n-1)} = 27 ^{n-1} ^{n-1} ^n $ 这样就可以证明了。

(c) 解释为什么 (b) 的假设蕴含了整体的命题

对于所有 $ n $，我们有 $ 2^{n-1} ^n $，因此 $ 3 ^{n-1} ^n $。所以我们证明的修改假设确实蕴含了我们想要证明的命题。

3. 二进制数

命题：证明每个正整数 $ n $ 都可以用二进制表示。也就是说，对于任意正整数 $ n \(，我们可以写成：\) n = c_k ^k + c_{k-1} ^{k-1} + + c_1 ^1 + c_0 ^0 $ 其中 $ k $，且对于所有 $ i k \(，\) c_i {0, 1} $。

证明过程：采用强归纳法。

  • 基础案例：对于 $ n = 1 $，可以写作 $ 1 ^0 $。

  • 归纳步骤：假设对所有 $ 1 m n $ 的 $ n $ 该命题成立，现在考虑 $ n + 1 $。如果 $ n + 1 $ 是偶数，则我们可以应用归纳假设。

    如果 $ n + 1 $ 是偶数，那么 $ n + 1 = 2 $。

  • 如果 $ n + 1 $ 是奇数，那么 $ n + 1 $ 可表示为 $ n + 1 = 2 () + 1 $。

通过强归纳法，我们可以推导出所有正整数都有二进制表示。

4. 斐波那契数列

命题：证明每第三个斐波那契数是偶数。斐波那契数递归定义为 $ F_1 = 1 \(，\) F_2 = 1 \(，\) F_n = F_{n-2} + F_{n-1} $。

证明过程：

  • 基础案例：对于 $ k = 1 $，有 $ F_3 = 2 $ 是偶数。

  • 归纳假设：假设对于某个固定值 $ k \(，\) F_{3k} $ 是偶数。

  • 归纳步骤： $ F_{3k+3} = F_{3k+2} + F_{3k+1} = 2F_{3k+1} + F_{3k} $ 根据归纳假设，$ F_{3k} = 2q \(，因此：\) F_{3k+3} = 2(F_{3k+1} + q) $ 这表明 $ F_{3k+3} $ 也是偶数。

通过归纳法，我们证明了所有 $ F_{3k} $ 都是偶数。