定义
例子
例子1
证明下面这个给定公式(命题)为真:
其中 为任意自然数。这是用于计算前n个自然数的和的简单公式。
证明
第一步-起始步骤
第一步是验证这个公式在 时成立。左边 ,而右边 ,所以这个公式在 时成立。第一步完成。
第二步-推递步骤
第二步证明假设 时公式成立,则可推理出 时公式也成立。 证明步骤如下。
假设 时公式成立。即
【等式 】
然后在等式等号两边分别加上 得到 【等式 】 这就是 时的等式。
现在需要根据等式等式 演绎出等式 的符号形式。(需要注意的是如果给定公式不为真,则做不到)通过因式分解合并(形式变换/字符操纵),等式 的右手边
也就是说
这样便证明了从等式 成立可推理出等式 也成立。证明至此完成,结论:对于任意自然数 , 均成立。
解释
在这个证明中,推理的过程如下:
- 首先证明命题 成立,即公式在 时成立。
- 然后证明从命题 成立可以推演出命题 也成立。【此部实际属于演绎推理法。技术方法是基于命题 的符号形式变换出命题 的符号形式】
- 根据上两条从命题 成立可以推理出命题 ,也就是命题 成立。
- 继续推理,可以知道命题 成立。
- 从命题 成立可以推导出命题 也成立。
- 不断的重复推導下一命題成立的步驟。(这就是所谓“归纳”推理的地方)
- 我们便可以下结论:对于任意自然数 ,命题 成立。
例子2
证明对于Fibonacci数列,定義 ,且 ,則 。
证明
首先,我们先使得 的情况成立, 然后,我们假定 的情况下的成立的, 然后我们使得 的情况也成立,(这是为了表明,如果有任意数k使得其成立,则有其+1也成立) 于是我们得证,即从 ,到 到所有正实数都成立,就像多米诺骨牌的第一块 成立而且每一块的下一块都成立( )
数学归纳法的变体
在应用中,数学归纳法常常需要采取一些变化来适应实际的需求。下面介绍一些常见的数学归纳法变体。
从0以外的自然数开始
第一种情况: 如果欲证明的命题并不是针对全部自然数,而只是针对所有大于等于某个数字b的自然数,那么证明的步骤需要做如下修改:
- 第一步,证明当 时命题成立。
- 第二步,证明如果 ( ) 成立,那么可以推导出 也成立。
用这个方法可以证明诸如“当 时, 这一类命题。
第二种情况: 如果欲证明的命题针对全部自然数,但仅当大于等于某个数字b时比较容易证明,则可参考如下步骤:
- 第一步,证明当 时命题成立。
- 第二步,证明如果 ( )成立,那么可以推导出 也成立。
用这种方法可以证明一些需要通过放缩来证明的不等式。
只針對偶数或只針對奇数
如果我们想证明的命题并不是针对全部自然数,而只是针对所有奇数或偶数,那么证明的步骤需要做如下修改:
奇数方面:
- 第一步,证明当 时命题成立。
- 第二步,证明如果 成立,那么可以推导出 也成立。
偶数方面:
- 第一步,证明当 或2时命题成立。
- 第二步,证明如果 成立,那么可以推导出 也成立。
或調整命題表述,使之變為對所有正整數成立,例如
- 證明「 對所有正奇數 成立」等價於證明「 對所有正整數 成立」。
遞迴歸納法
又名递降归纳法。数学归纳法并不是只能应用于形如“对任意的 ”这样的命题。对于形如“对任意的 ”这样的命题,如果对一般的 比较复杂,而 比较容易验证,并且我们可以实现从 到 的递推, 的话,我们就能应用归纳法得到对于任意的 ,原命题均成立。
完整归纳法
另一个一般化的方法叫完整归纳法(也称第二数学归纳法或强归纳法),在第二步中我们假定式子不仅当 时成立,当 小于或等于 时也成立。这样可以设计出这样两步:
- 证明当 时式子成立.
- 证明当 时成立,那么当 时式子也成立.
例如,这种方法被用来证明:
-
其中 是第 个斐波纳契数和 (即黄金分割)。如果我们可以假设式子已经在当 和 时成立,从 之后可以直截了当地证明当 时式子成立.
这种方法也是第一种形式的特殊化:
- 定义 是我们将证的式子,
- 和 成立
- 在 和 成立时成立。
结论: 对一切自然数 成立。
超限归纳法
最后两步可以用这样一步表示:
- 证明如果式子在所有的 成立,那么式子在当 时也成立。
实际上这是数学归纳法的大多数通式,可以知道他不仅对表达自然数的式子有效,而且对于任何在良基集(也就是一个偏序的集合,包括有限降链)中元素的式子也有效(这里" "被定义为 当且仅当 和 )。
这种形式的归纳法当运用到序数(以有序的和一些的良基类的形式)时被称为超限归纳法,它在集合论、拓扑学和其他领域是一種重要的方法。
要区别用超限归纳法证明的命题的三种情况:
- 是一个极小元素,也就是没有一个元素小于
- 有一个直接的前辈,比 小的元素有一个大的元素
- 没有任何前辈,也就是 是一个界限序数.
参见数学归纳法的三种形式。
形式寫法
数学归纳法的合理性
參見
參考文獻
外部链接
This article uses material from the Wikipedia 中文 article 数学归纳法, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). 除非另有声明,本网站内容采用CC BY-SA 4.0授权。 Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki 中文 (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.