数学归纳法

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

故此,所有都为真

 

骨牌效应

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

故此。。。。。。所有多米诺骨牌都会倒下!

这就是数学归纳法的精髓

在数字领域上,我们说:

怎样做

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

第二步最好这样做:

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

例如:

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

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

 

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

31−1 = 3−1 = 2

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

31−1 成立!

 

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

3k−1 成立

(慢着!我们怎么知道这是真的? 对,我们不知道!
这是个假设。。。。。。接下来,在这例子里我们以此为
事实

 

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

数学归纳法 a

 

3k+1 也是 3×3k

拆开为

每项都是 2 的倍数

 

因为:

所以:

命题:3k+1−1 是 2 的倍数――成立!

大功告成!

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

。。。。。。我们其实在问:"任何一个多米诺骨牌倒下,下一个会不会也倒下?

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

窍门

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

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

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

例子:奇数相加

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 成立

功德圆满!

讲完了!