Mixing
数学归纳法
 | 本條目需要擴充。 (2013年10月18日) |
数学归纳法（Mathematical Induction、MI、ID）是一种数学证明方法，通常被用于证明某个给定命题在整个（或者局部）自然数范围内成立。除了自然数以外，广义上的数学归纳法也可以用于证明一般良基结构，例如：集合论中的树。这种广义的数学归纳法应用于数学逻辑和计算机科学领域，称作结构归纳法。
虽然数学归纳法名字中有“归纳”，但是数学归纳法并非不严谨的归纳推理法，它属于完全严谨的演绎推理法。[1]事實上，所有數學證明都是演繹法。
目录
1 定义
2 例子
2.1 证明
2.1.1 第一步-起始步骤
2.1.2 第二步-推递步骤
2.2 解释
3 数学归纳法的变体
3.1 从0以外的自然数开始
3.2 只針對偶数或只針對奇数
3.3 递降归纳法 又名 遞迴歸納法
3.4 完整归纳法
3.5 超限归纳法
4 形式寫法
5 数学归纳法的合理性
6 參見
7 參考文獻
8 外部链接
定义
最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步：
骨牌一个接一个倒下，就如同一个值到下一个值的过程
- 证明当n = 1时命题成立。
- 证明如果在n = m时命题成立，那么可以推导出在n = m+1时命题也成立。（m代表任意自然数）
这种方法的原理在于：首先证明在某个起点值时命题成立，然后证明从一个值到下一个值的过程有效。当这两点都已经证明，那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成多米诺效应也许更容易理解一些。[2][3]例如：你有一列很长的直立着的多米诺骨牌，如果你可以：
- 证明第一张骨牌会倒。
- 证明只要任意一张骨牌倒了，那么其下一张骨牌也会因為前面的骨牌倒而跟著倒。
那么便可以下结论：所有的骨牌都会倒下。
例子
假设我们要证明下面这个公式（命题）：
1+2+3+⋯+n=n(n+1)2{displaystyle 1+2+3+cdots +n={frac {n(n+1)}{2}}}
其中n为任意自然数。这是用于计算前n个自然数的和的简单公式。证明这个公式成立的步骤如下。
证明
第一步-起始步骤
第一步是验证这个公式在n = 1时成立。我们有左边 = 1，而右边 =1(1+1)2=1{displaystyle {frac {1(1+1)}{2}}=1}
第二步-推递步骤
第二步我们需要证明如果假设n = m时公式成立，那么可以推导出n = m+1时公式也成立。证明步骤如下。
我们先假设n = m时公式成立。即
1+2+⋯+m=m(m+1)2{displaystyle 1+2+cdots +m={frac {m(m+1)}{2}}}
然后在等式等号两边分别加上m + 1得到
1+2+⋯+m+(m+1)=m(m+1)2+(m+1){displaystyle 1+2+cdots +m+(m+1)={frac {m(m+1)}{2}}+(m+1)}
这就是n = m+1时的等式。我们现在需要根据等式1证明等式2成立。通过因式分解合并，等式2的右手边
=m(m+1)2+2(m+1)2=(m+2)(m+1)2=(m+1)(m+2)2=(m+1)[(m+1)+1]2.{displaystyle ={frac {m(m+1)}{2}}+{frac {2(m+1)}{2}}={frac {(m+2)(m+1)}{2}}={frac {(m+1)(m+2)}{2}}={frac {(m+1)[(m+1)+1]}{2}}.}
![={frac {m(m+1)}{2}}+{frac {2(m+1)}{2}}={frac {(m+2)(m+1)}{2}}={frac {(m+1)(m+2)}{2}}={frac {(m+1)[(m+1)+1]}{2}}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d257b49479295ce7d579e239735a22cbe435337)
也就是说
1+2+⋯+(m+1)=(m+1)[(m+1)+1]2{displaystyle 1+2+cdots +(m+1)={frac {(m+1)[(m+1)+1]}{2}}}
![1+2+cdots +(m+1)={frac {(m+1)[(m+1)+1]}{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/328bb76c33c74d0cae042af939966bf339b40214)
这样便证明了从P（m） 成立可以推导出P（m+1） 也成立。证明至此完成，结论：对于任意自然数n，P（n） 均成立。
解释
在这个证明中，归纳推理的过程如下：
- 首先证明P(1)成立，即公式在n = 1时成立。
- 然后证明从P（m） 成立可以推导出P（m+1） 也成立。（这里实际应用的是演绎推理法）
- 根据上两条从P(1)成立可以推导出P（1+1），也就是P(2)成立。
- 继续推导，可以知道P（3）成立。
- 从P(3)成立可以推导出P(4)也成立。
- 不断不断不断的重复推導下一命題成立的步驟。（这就是所谓“归纳”推理的地方）
- 我们便可以下结论：对于任意自然数n，P（n） 成立。
数学归纳法的变体
在应用中，数学归纳法常常需要采取一些变化来适应实际的需求。下面介绍一些常见的数学归纳法变体。
从0以外的自然数开始
第一种情况：
如果欲证明的命题并不是针对全部自然数，而只是针对所有大于等于某个数字b的自然数，那么证明的步骤需要做如下修改：
- 第一步，证明当n = b时命题成立。
- 第二步，证明如果n = m（m ≥ b） 成立，那么可以推导出n = m+1也成立。
用这个方法可以证明诸如“当n ≥ 3时，n2 > 2n”这一类命题。
第二种情况：
如果欲证明的命题针对全部自然数，但仅当大于等于某个数字b时比较容易证明，则可参考如下步骤：
- 第一步，证明当n =0，1，2，… b时命题成立。
- 第二步，证明如果n = m（m ≥ b） 成立，那么可以推导出n = m+1也成立。
用这种方法可以证明一些需要通过放缩来证明的不等式。
只針對偶数或只針對奇数
如果我们想证明的命题并不是针对全部自然数，而只是针对所有奇数或偶数，那么证明的步骤需要做如下修改：
奇数方面：
- 第一步，证明当n = 1时命题成立。
- 第二步，证明如果n = m成立，那么可以推导出n = m+2也成立。
偶数方面：
- 第一步，证明当n = 0或2时命题成立。
- 第二步，证明如果n = m成立，那么可以推导出n = m+2也成立。
递降归纳法 又名 遞迴歸納法
数学归纳法并不是只能应用于形如“对任意的n”这样的命题。对于形如“对任意的n=0,1,2,...,m”这样的命题，如果对一般的n比较复杂，而n=m比较容易验证，并且我们可以实现从k到k-1的递推，k=1,...,m的话，我们就能应用归纳法得到对于任意的n=0,1,2,...,m，原命题均成立。
完整归纳法
另一个一般化的方法叫完整归纳法（也称第二数学归纳法或强归纳法），在第二步中我们假定式子不仅当n = m时成立，当n小于或等于m时也成立.这样可以设计出这样两步:
- 证明当n = 0时式子成立.
- 证明当n ≤ m时成立，那么当n = m + 1时式子也成立.
例如，这种方法被用来证明：
- fib(n)=Φn−(−1Φ)512{displaystyle mathrm {fib} (n)={frac {Phi ^{n}-left({frac {-1}{Phi }}right)}{5^{frac {1}{2}}}}}
其中fib（n） 是第n个斐波纳契数和Φ = (1 + 51/2) / 2 (即黄金分割).如果我们可以假设式子已经在当n = m和n = m − 1时成立，从fib（m + 1） = fib(m) + fib（m − 1）之后可以直截了当地证明当n=m + 1时式子成立.
这种方法也是第一种形式的特殊化：
- 定义P（n） 是我们将证的式子,
P（0）和P（1）成立
P（m + 1）在P（m）和P（m − 1）成立时成立。
结论：P（n）对一切自然数n成立。
超限归纳法
最后两步可以用这样一步表示：
- 证明如果式子在所有的n < m成立，那么式子在当n = m时也成立.
实际上这是数学归纳法的大多数通式，可以知道他不仅对表达自然数的式子有效，而且对于任何在良基集（也就是一个偏序的集合，包括有限降链） 中元素的式子也有效（这里"<"被定义为a < b 当且仅当a ≤ b和a ≠ b）.
这种形式的归纳法当运用到序数（以有序的和一些的良基类的形式）时被称为超限归纳法.它在集合论，拓扑学和其他领域是一種重要的方法.
要区别用超限归纳法证明的命题的三种情况：
m是一个极小元素，也就是没有一个元素小于m
m有一个直接的前辈，比m小的元素有一个大的元素
m没有任何前辈，也就是m是一个界限序数.
参见数学归纳法的三种形式。
形式寫法
二階邏輯可捕捉數學歸納法這概念，表達成如下邏輯式：
∀P(P(0)∧∀k(P(k)→P(k+1))→∀n(P(n))){displaystyle displaystyle forall P{Bigl (}P(0)land forall k{bigl (}P(k)to P(k+1){bigr )}to forall n{bigl (}P(n){bigr )}{Bigr )}}，
P(.) 是容納一自然數的述詞變元，遍歷所有述詞而非個別數字，為二階量詞（是故此式與二階邏輯有關），k 與 n 則是自然數變元，遍歷所有自然數。
白話解釋此式，此式說：起始步驟 P(0) 與推遞步驟（即歸納假設，P(k) 蘊涵 P(k + 1)） 兩步成立會導出對任一自然數 n， P(n) 成立之結論。通常，我們為了證明第二步，會假設P(n)成立（歸納假設），再進一步證明P(n+1)。此牽涉到條件證法，將條件句之前件作為假設，假定其正確以便於證明。
若用一階邏輯將數學歸納法公設化，則須採用公設模式，替每一個可能存在的述詞設下針對其的獨立公設。舉例而言，我們僅允許三個一階述詞存在，分別名為 P1、P2、P3 ，則原先以二階邏輯描述的公設可改寫為：
P1(0)∧∀k(P1(k)→P1(k+1))→∀n(P1(n)){displaystyle displaystyle P_{1}(0)land forall k{bigl (}P_{1}(k)to P_{1}(k+1){bigr )}to forall n{bigl (}P_{1}(n){bigr )}}，
P2(0)∧∀k(P2(k)→P2(k+1))→∀n(P2(n)){displaystyle displaystyle P_{2}(0)land forall k{bigl (}P_{2}(k)to P_{2}(k+1){bigr )}to forall n{bigl (}P_{2}(n){bigr )}}，
P3(0)∧∀k(P3(k)→P3(k+1))→∀n(P3(n)){displaystyle displaystyle P_{3}(0)land forall k{bigl (}P_{3}(k)to P_{3}(k+1){bigr )}to forall n{bigl (}P_{3}(n){bigr )}}，
皮亞諾公設之歸納公設便採用此方法。
一階ZFC集合論不允許述詞被遍歷， 但我們可以藉由遍歷集合，繞過一階邏輯之限制，描述歸納法：
- ∀A(0∈A∧∀k∈N(k∈A→(k+1)∈A)→N⊆A){displaystyle forall A{Bigl (}0in Aland forall kin mathbb {N} {bigl (}kin Ato (k+1)in A{bigr )}to mathbb {N} subseteq A{Bigr )}}
A{displaystyle A}
数学归纳法的合理性
皮亞諾公理視數學歸納法不證自明，設作公設，而於ZFC集合論，數學歸納法可从良序原則（well-ordering principle）推导出来。[4]
參見
- 归纳推理
- 演绎推理
- 结构归纳法
參考文獻
^ Suber, Peter. Mathematical Induction. Earlham College. [2011-03-26] （英语）.
^ Matt DeVos. Mathematical Induction (PDF). 西門菲莎大學 （英语）.
^ Gerardo con Diaz. Mathematical Induction (PDF). 哈佛大學 （英语）.
^ Well Ordering Principle and the Principle of Mathematical Induction (PDF). [2019-02-03] （英语）.
外部链接
Mathematical Induction, Examples（英文）
Comments
Post a Comment