归纳法的魅力在于,它允许我们在存在无限多个情况的情况下证明一个定理是正确的,而无需单独考察每个情况。归纳法类似于一排无限长的多米诺骨牌,每个骨牌都立着。如果你想让所有的多米诺骨牌都倒下,你可以:
- 推倒第一个骨牌,等待结果,然后逐个检查后面的骨牌(如果骨牌数量无限多,这可能需要很长时间!)
- 或者你可以证明,如果任何一个骨牌倒下,它就会导致它后面的骨牌倒下。(即,如果第一个倒下,那么第二个就会倒下,如果第二个倒下,那么第三个就会倒下,等等。)
归纳法本质上是第二点中概述的方法。
归纳法由三个部分组成
- 基本情况(在多米诺骨牌的类比中,这表明第一个骨牌会倒下)
- 归纳假设(在多米诺骨牌的类比中,我们假设某个特定骨牌会倒下)
- 归纳步骤(在多米诺骨牌的类比中,我们证明我们假设会倒下的骨牌会使下一个骨牌倒下)
弱归纳法用于证明给定的性质对可数归纳集中的所有成员成立,这通常用于自然数集。
弱归纳法用于证明一个陈述
(它取决于
)依赖于两个步骤
对某个基本情况成立。通常基本情况是
或
。也就是说,如果
成立,那么
也成立。
如果这两个性质成立,那么就可以推断该性质对该集合中的所有元素都成立。回到例子中,如果你确定你给你的邻居打了电话,并且你知道每个接到电话的人都会给他们的邻居打电话,那么你就能保证这个街区上每个人都接到了电话(假设你的街区是直线形的,或者曲线很好看)。
归纳法证明的第一个例子总是“前n项的和:”
- 定理 2.4.1. 对于任何固定的

- 证明
- 基本情况:
,因此基本情况成立。
- 假设
。考虑
。

因此,归纳步骤成立。现在通过归纳法,我们看到该定理是正确的。
逆向归纳法是一种使用归纳步骤中负数的归纳方法。它是弱归纳法的一个小变种。该过程仍然只适用于可数集,通常是全数集或整数集,并且通常会在 1 或 0 处停止,而不是适用于所有正数。
逆向归纳法在以下情况下有效。
- 该性质对于一个给定值成立,比如
。
- 假设该性质对于一个给定情况成立,比如
,证明该性质对于
成立。
那么该性质对于所有值
成立。
逆向归纳法也适用于一般情况[1]: “为了建立命题序列
的有效性,只需建立以下几点
(a)
对于无限多个
成立。
(b) 如果
成立,那么
也成立。
我们可以很容易地证明
,并且如果
对
成立,那么
对
也成立。在这种情况下,我们有(a)对于无穷多个
。
在弱归纳法中,对于归纳步骤,我们只需要对于给定的
,其直接前驱
满足定理(即
为真)。在强归纳法中,我们要求不仅直接前驱,而且
的所有前驱都满足定理。归纳步骤的变动是
- 如果
对所有
成立,那么
为真。
这种方法被称为强归纳法的原因相当明显——归纳步骤中的假设比弱归纳法中的假设要强得多。当然,对于有限归纳法,它最终是相同的假设,但在超限集的情况下,弱归纳法甚至没有定义,因为一些集合存在没有直接前驱的元素。
用于证明涉及超限基数的定理。这种技术在集合论中用于证明基数的性质,因为很少有其他方法可以做到这一点。
我们首先定义*良序*集的概念。一个集合
是*良序*的,如果存在一个全序
在
上,并且只要
是非空的,
中存在一个*最小元素*。也就是说,
使得
。
*归纳集*是一个集合
,满足以下条件
(其中
是
的最小元素)
- 如果
,那么
,使得
当然,你会看到这一点并说:“等等。这意味着
!” 当然,你说得对。这正是归纳法起作用的原因。归纳原理是这个定理:它说
- 定理 2.4.2. 如果
是一个非空的良序集,并且
是
的归纳子集,那么
。
这个定理的证明留作一个非常简单的练习。这里我们注意到自然数集显然是良序的,具有您所熟悉的正常顺序,因此
是一个归纳集。如果您接受选择公理,那么每个集合都可以被良序化。
证明对于每个正整数:

首先,我们证明当
时成立。

假设该等式对某个数
成立,那么

我们的目标是证明

由此得出

这就是我们要证明的。由于该等式对 1 成立,它也对 2 成立,并且由于它对 3 成立,依此类推。
证明对于每个正整数:

首先,我们证明当
时成立。

假设该等式对
成立。那么

我们的目标是证明

由此得出
![{\displaystyle {\begin{aligned}(1^{2}+\cdots +k^{2})+(k+1)^{2}&={\frac {k(k+1)(2k+1)}{6}}+(k+1)^{2}\\&={\frac {k(k+1)(2k+1)+6(k+1)^{2}}{6}}\\&={\frac {(k+1){\big [}k(2k+1)+6(k+1){\big ]}}{6}}\\&={\frac {(k+1)(2k^{2}+k+6k+6)}{6}}\\&={\frac {(k+1)(2k^{2}+7k+6)}{6}}\\&={\frac {(k+1)(k+2)(2k+3)}{6}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/82e1e7fe954a79b3675f1c48d96c884ef212c55a)
这正是我们要证明的。根据数学归纳法,该公式适用于所有正整数。
证明对于每个正整数:

证明对于

,

。
证明对于每个正整数,

首先,我们证明当
时成立。

假设该等式对
成立。那么

我们的目标是证明

由此得出

这正是我们要证明的。根据数学归纳法,该公式适用于所有正整数。
证明对于每个正整数:

首先,我们证明当
时成立。

假设该等式对
成立。那么

我们的目标是证明

由此得出

这正是我们要证明的。根据数学归纳法,该公式适用于所有正整数。
证明对于每个正整数:

首先,我们证明当
时成立。

假设该等式对
成立。那么

我们的目标是证明

由此得出

这正是我们要证明的。根据数学归纳法,该公式适用于所有正整数。
证明对于每个正整数:

首先,我们证明当
时成立。

假设该等式对
成立。那么

我们的目标是证明

由此得出

这正是我们要证明的。根据数学归纳法,该公式适用于所有正整数。
证明对于每个正整数:

首先,我们证明当
时成立。

假设该等式对
成立。那么

我们的目标是证明

由此得出

这正是我们要证明的。根据数学归纳法,该公式适用于所有正整数。
这个问题可以用不使用数学归纳法的方法解决。我们注意到

那么,这个问题可以改写为

化简得到

证明对于所有正整数:

首先,我们证明当
时成立。

假设该等式对
成立。那么

我们的目标是证明

由此得出
![{\displaystyle {\begin{aligned}(a+\cdots +a^{k})+a^{k+1}&={\frac {a(a^{k}-1)}{a-1}}+a^{k+1}\\&={\frac {a(a^{k}-1)+a^{k+1}(a-1)}{a-1}}\\&={\frac {a{\big [}a^{k}-1+a^{k}(a-1){\big ]}}{a-1}}\\&={\frac {a{\big [}a^{k}-1+a\cdot a^{k}-a^{k}{\big ]}}{a-1}}\\&={\frac {a(a^{k+1}-1)}{a-1}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a9d9327b5fce5eb5d78eba168803f0fa090e963)
这正是我们要证明的。根据数学归纳法,该公式适用于所有正整数。
这也可以通过使用几何级数的求和公式证明。
证明对于每个正整数:

首先,我们证明当
时成立。

假设该等式对
成立。那么

我们的目标是证明

由此得出
![{\displaystyle {\begin{aligned}(1+\cdots +k^{5})+(k+1)^{5}+(1+\cdots +k^{7})+(k+1)^{7}&=2\left({\frac {k(k+1)}{2}}\right)^{4}+(k+1)^{5}+(k+1)^{7}\\&={\frac {(k+1)^{4}{\big [}k^{4}+8(k+1)+8(k+1)^{3}{\big ]}}{8}}\\&={\frac {(k+1)^{4}{\big [}k^{4}+8(k+1){\big (}1+(k+1)^{2}{\big )}{\big ]}}{8}}\\&={\frac {(k+1)^{4}{\big [}k^{4}+8(k+1)(k^{2}+2k+2){\big ]}}{8}}\\&={\frac {(k+1)^{4}(k^{4}+8k^{3}+24k^{2}+32k+16)}{8}}\\&={\frac {(k+1)^{4}(k+2)^{4}}{8}}\\&=2\left({\frac {(k+1)(k+2)}{2}}\right)^{4}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52b56fd1aa9dcc381c7430e10e064dc235ecba75)
这正是我们要证明的。根据数学归纳法,该公式适用于所有正整数。
证明对于每个正整数:

(称为伯努利不等式)
证明对于每个正整数:

首先,我们证明该陈述对
成立。

假设不等式对
成立。然后,

我们的目标是证明

我们知道

现在我们需要证明

由此得出

最后一个结论显然成立(
)。因此,

现在我们证明

我们知道

现在我们需要证明

由此得出

最后一个结论显然成立(
)。因此,

结合我们证明的两个不等式,得到归纳步骤中需要的那个不等式。

根据数学归纳法,该公式对所有正整数都成立。
证明对于所有正整数:

(困难)
首先,我们证明当
时成立。
因为 
假设不等式对
成立。然后,

我们的目标是证明

我们知道

现在我们需要证明

由此得出

最后一个语句显然是正确的。所以,

根据数学归纳法,该公式对所有正整数都成立。
证明对于每个正整数: 3 是

的一个因子。
证明对于每个正整数:9 是

的因数。
首先,我们证明这个命题在
时成立。
由于我们已经证明了基本情况成立,我们现在假设该命题在
时成立,其中
。
我们知道
对于某些
,
我们需要证明
对于某些
。
我们尝试证明以上内容
令
,我们有
我们在假设该结论对
成立的情况下,证明了该结论对
成立。因此,根据数学归纳法,该结论对所有正整数都成立。
请注意,也可以使用 9 的整除性规则来证明这一点:
的各位数字之和为
,因此该数字本身可以被 9 整除。
证明对每个正整数:4 是

的一个因子
首先,我们证明该结论对
成立。当 n=1 时,
,4 是 4 的一个因子。
当 n=2 时,
,4 是 24 的一个因子。
因此,基本情况成立。现在我们假设上述方程
对 n=k 成立,并试图证明该方程对 n=k+1 成立。

根据我们上面的归纳假设,4 是 f(k) 的一个因子,4 也是 4 的一个因子,所以我们知道 4 必须也是
的一个因子。根据数学归纳法,该方程对所有正整数都成立。
证明对于任意正整数:

是

的因式。
证明对每个正整数:2304 是

的一个因子。
找到

,使得不等式

对所有

成立,并给出归纳法证明。
- ↑ http://people.math.carleton.ca/~ckfong/hs14a.pdf