数学归纳法

数学归纳法

数学归纳法是一个特别的证明方法。它只有两步：

• 一、证明首个为真
• 二、证明若任何一个为真，则下一个亦为真
  故此，所有都为真

听过"多米诺骨牌效应"吗？

• 一、第一个多米诺骨牌倒下
• 二、当任何多米诺骨牌倒下，下一个骨牌亦会倒下
  故此。。。。。。所有多米诺骨牌都会倒下！

这就是数学归纳法的精髓

在数字领域上，我们说：

• 一、说明当n=1时为真
• 二、说明若当n=k时为真，则当n=k+1时亦为真

怎样做

第一步通常是容易的，我们只需证明命题（我们要证明的东西）在n=1时成立

第二步最好这样做：

• 假设当n=k时命题成立
• 证明当n=k+1时命题成立（以当n=k时命题成立为事实。）

第二步有时候不好做。。。。。。因为时常要用到高明的诀窍！

例如：

例子：3n−1 是 2 的倍数

这是真的吗？我们来看看。

一、证明当n=1时命题成立

31−1 = 3−1 = 2

对了，2 是 2 的倍数。易如反掌。

31−1 成立！

二、.假设在n=k时也成立

3k−1 成立

（慢着！我们怎么知道这是真的？ 对，我们不知道！

这是个假设。。。。。。接下来，在这例子里我们以此为

事实）

现在来证明3k+1−1是 2 的倍数

把3×拆开为2×和1×

每项都是 2 的倍数

因为：

• 2×3k是 2 的倍数（乘以 2）
• 3k−1 也是 2 的倍数（这是我们的假设）

所以：

命题：3k+1−1 是 2 的倍数――成立！

大功告成！

你看到我们怎样利用 "当3k−1时命题成立"为假设？那是允许的，因为我们依赖多米诺骨牌效应。。。。。。

。。。。。。我们其实在问："若任何一个多米诺骨牌倒下，下一个会不会也倒下？

我们假设（暂时）"n=k"的骨牌倒下（当3k−1时命题成立），然后看看这能否导致 "n=k+1" 的骨牌也倒下。

窍门

上面我说通常我们需要用到高明的诀窍。

一个常用的诀窍是把n=k+1的例子分拆为2个部分：

• 一部分是n=k（我们假设成立）
• 然后看看另一部分是否也成立

上面我们就是这样做了。再看一个例子：

例子：奇数相加

1 + 3 + 5 + ... + (2n−1) = n2

一、证明当n=1时这是对的

1 = 12是对的

2.假设当n=k时这也是对的

1 + 3 + 5 + ... + (2k−1) = k2是对的

（一个假设！）

现在来证明 "k+1" 是对的

1 + 3 + 5 + ... + (2k−1) + (2(k+1)−1) = (k+1)2 ？

我们知道1 + 3 + 5 + ... + (2k−1) = k2（我们的假设），所以我们可以用 k2来代替除了最后一项外所有的项：

k2+ (2(k+1)−1) = (k+1)2

展开所有的项：

k2+ 2k + 2 − 1 = k2+ 2k+1

简化：

k2+ 2k + 1 = k2+ 2k + 1

它们相等！所以当 n=k+1 时，这也是对的。

故此：

1 + 3 + 5 + ... + (2(k+1)−1) = (k+1)2成立

功德圆满！

讲完了！