查看“︁数学归纳法”︁的源代码

{{expand|time=2013-10-18T17:40:34+00:00}}
{{NoteTA
|G1=Math
}}

'''数学归纳法'''（{{lang-en|mathematical induction}}，縮寫：'''MI'''）是一种[[数学证明]]方法，通常被用于[[數學證明|证明]]某个给定[[命题]]在整个或者局部[[自然数]]范围内成立。除了[[自然数]]以外，[[广义化|广义]]上的数学归纳法也可以用于证明一般[[良基关系|良基]]结构，例如：[[集合论]]中的[[树 (集合论)|树]]。这种广义的数学归纳法应用于[[数学逻辑]]和[[计算机科学]]领域，称作[[结构归纳法]]。

虽然数学归纳法名字中有“归纳”，但是数学归纳法并非[[逻辑]]上[[严谨性 (数学)|不严谨]]的[[归纳推理|归纳推理法]]，它属于完全[[严谨]]的[[演绎推理|演绎推理法]]。<ref>{{cite web|last=Suber|first=Peter|title=Mathematical Induction|url=http://www.earlham.edu/~peters/courses/logsys/math-ind.htm|publisher=Earlham College|accessdate=2011-03-26|language=en|archive-date=2011-05-24|archive-url=https://web.archive.org/web/20110524104121/http://www.earlham.edu/~peters/courses/logsys/math-ind.htm|dead-url=no}}</ref>[[事實]]上，所有[[數學證明]]都属于[[演繹推理]][[方法学|方法]]。

== 定义 ==
最简单和常见的[[数学]]归纳法是证明当<math>n</math>等于任意一个[[自然数]]时某[[命题]]成立。[[數學證明|证明]]分下面两步：
[[File:Dominoeffect.png|thumb|right|200px|骨牌一个接一个倒下，就如同一个值到下一个值的过程]]
# 证明 “当<math>n=1</math>时命题成立。”（选择数字1因其作为自然数[[集合 (数学)|集合]]中的最小值）
# 证明 “若'''[[假设]]'''在<math>n=m</math>时命题成立，'''可推導'''出在<math>n=m+1</math>时命题成立。（<math>m</math>代表任意自然数）” 

这种方法的原理在于：首先证明在某个起点值时命题成立，然后证明从一个值到下一个值的'''过程'''有效。当这两点都已经证明，那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成[[多米诺骨牌效应]]也许更容易理解一些。<ref>{{cite web|author=Matt DeVos|title=Mathematical Induction|url=https://www.sfu.ca/~mdevos/notes/graph/induction.pdf}|publisher=[[西門菲莎大學]]|language=en}}</ref><ref>{{cite web|author=Gerardo con Diaz|url=http://www.math.harvard.edu/archive/23a_fall_05/Handouts/induction.pdf|title=Mathematical Induction|publisher=[[哈佛大學]]|language=en|access-date=2019-02-10|archive-url=https://web.archive.org/web/20130502163438/http://www.math.harvard.edu/archive/23a_fall_05/Handouts/induction.pdf|archive-date=2013-05-02|dead-url=yes}}</ref>例如：你有一列很长的直立着的多米诺骨牌，如果你可以：
# 证明 「第一张[[骨牌]]会倒。」
# 证明 「只要任意一张骨牌倒了，其下一张骨牌也会'''因為'''前面的骨牌倒'''而'''跟著倒。」

则可下结论：所有的骨牌都会倒下。

== 例子 ==
=== 例子1 ===
证明下-{面}-这个给定[[公式]]（[[命题]]）'''为真'''：

<math>1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}</math>

其中''<math>n</math>''为任意自然数。这是用于计算前''n''个自然数的和的简单公式。

==== 证明 ====
===== 第一步-起始步骤 =====
第一步是验证这个公式在<math>n=1</math>时成立。左边<math>=1</math>，而右边<math>=\frac{1(1+1)}{2}=1</math>，所以这个公式在<math>n=1</math>时成立。第一步完成。

===== 第二步-推递步骤 =====
第二步证明'''假设'''<math>n=m</math>时公式成立，'''则可[[推理]]'''出<math>n=m+1</math>时[[公式]]也成立。 证明步骤如下。

假设<math>n=m</math>时公式成立。即

<math>1 + 2 + \cdots + m = \frac{m(m + 1)}{2}</math>【等式<math>P(m)</math>】

然后在[[等式]][[等号]]两边分别加上<math>m+1</math>得到
<math>1 + 2 + \cdots + m + (m + 1) = \frac{m(m + 1)}{2} + (m+ 1)</math>【等式<math>P(m+1)</math>】
这就是<math>n=m+1</math>时的等式。

现在需要'''根据'''等式等式<math>P(m+1)</math>'''[[演绎]]'''出等式<math>P(m)</math>的'''[[符号]][[形式]]'''。（需要注意的是如果给定公式不为真，则做不到）通过[[因式]]分解合并([[形式]][[变换]]/[[字符]][[操纵]])，等式<math>P(m+1)</math>的右手边

<math>
= \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}.
</math>

也就是说

<math>1 + 2 + \cdots + (m + 1) = \frac{(m + 1)[(m + 1) + 1]}{2} </math>

这样便证明了从等式<math>P(m)</math>成立可[[推理]]出等式<math>P(m+1)</math>也成立。证明至此完成，结论：对于任意自然数<math>n</math>，<math>P(n)</math>均成立。

==== 解释 ====
在这个[[數學證明|证明]]中，[[推理]]的过程如下：
# 首先证明[[命题]]<math>P(1)</math>成立，即[[公式]]在<math>n=1</math>时成立。
# 然后证明从命题<math>P(m)</math>成立可以推演出命题<math>P(m+1)</math>也成立。【此部实际属于演绎推理法。'''技术方法'''是基于命题<math>P(m+1)</math>的[[符号]][[形式]]变换出命题<math>P(m)</math>的符号形式。】
# 根据上两条从命题<math>P(1)</math>成立可以推理出命题<math>P(1+1)</math>，也就是命题<math>P(2)</math>成立。
# 继续推理，可以知道命题<math>P(3)</math>成立。
# 从命题<math>P(3)</math>成立可以推导出命题<math>P(4)</math>也成立。
# 不断的重复推導下一命題成立的步驟。（这就是所谓“归纳”推理的地方）
# 我们便可以下结论：对于任意[[自然数]]<math>n</math>，命题<math>P(n)</math> 成立。

=== 例子2 ===
证明对于[[Fibonacci数列]]，定義<math>F_n=F_{n-1}+F_{n-2}</math>，且<math>F_0=0,F_1=1</math>，則<math>F_0+F_1+F_2+ \cdots +F_n=F_{n+2}-1</math>。

==== 证明 ====
首先，我们先使得<math>n=0</math>的情况成立，<math>F_{0}=F_{2}-1 ,0=1-1=0</math>
然后，我们假定<math>n=k</math>的情况下的成立的，<math>F_{0}+F_{1}+...+F_{k}=F_{k+2}-1</math>
然后我们使得<math>n=k+1</math>的情况也成立，（这是为了表明，如果有任意数k使得其成立，则有其+1也成立）
<math>
F_{0}+F_{1}+...+F_{k}+F_{k+1}
=F_{k+2}-1+F_{k+1}
=F_{k+3}-1
</math>
于是我们得证，即从<math>n=0</math>，到<math>n=0+1,1+1,2+1</math>到所有正实数都成立，就像多米诺骨牌的第一块<math>n=0</math>成立而且每一块的下一块都成立（<math>k,k+1</math>)

== 数学归纳法的变体 ==
在应用中，[[数学]]归纳法常常需要采取一些变化来适应实际的需求。下面介绍一些常见的数学归纳法变体。

=== 从0以外的自然数开始 ===

第一种情况：
如果欲证明的命题并不是针对全部自然数，而只是针对所有大于等于某个数字''b''的自然数，那么证明的步骤需要做如下修改：

# 第一步，证明当<math>n=b</math>时命题成立。
# 第二步，证明如果<math>n=m</math>（<math>m\geq b</math>） 成立，那么可以推导出<math>n=m+1</math>也成立。

用这个方法可以证明诸如“当<math>n\geq 5</math>时，<math>2^n>n^2</math>这一类命题。

第二种情况：
如果欲证明的命题针对全部自然数，但仅当大于等于某个数字''b''时比较容易证明，则可参考如下步骤：

# 第一步，证明当<math>n=0,1,2,\cdots, b</math>时命题成立。
# 第二步，证明如果<math>n=m</math>（<math>m\geq b</math>）成立，那么可以推导出<math>n=m+1</math>也成立。

用这种方法可以证明一些需要通过放缩来证明的不等式。

=== 只針對偶数或只針對奇数 ===
如果我们想证明的命题并不是针对全部[[自然数]]，而只是针对所有[[奇数]]或[[偶数]]，那么证明的步骤需要做如下修改：

奇数方面：

# 第一步，证明当<math>n=1</math>时命题成立。
# 第二步，证明如果<math>n=m</math>成立，那么可以推导出<math>n=m+2</math>也成立。

偶数方面：

# 第一步，证明当<math>n=0</math>或<math>n = 2</math>时命题成立。
# 第二步，证明如果<math>n=m</math>成立，那么可以推导出<math>n=m+2</math>也成立。

或調整命題表述，使之變為對所有正整數成立，例如
:證明「<math>1+3+5+7+ \cdots +a=\frac{(a+1)^2}{4}</math>對所有正奇數<math>a</math>成立」等價於證明「<math>1+3+5+7+ \cdots +(2b-1)=b^2</math>對所有正整數<math>b</math>成立」。

=== 遞迴歸納法 ===
又名'''递降归纳法'''。数学归纳法并不是只能应用于形如“对任意的<math>n</math>”这样的命题。对于形如“对任意的<math>n=0,1,2,\cdots,m</math>”这样的命题，如果对一般的<math>n</math>比较复杂，而<math>n=m</math>比较容易验证，并且我们可以实现从<math>k</math>到<math>k-1</math>的递推，<math>k=1,\cdots,m</math>的话，我们就能应用归纳法得到对于任意的<math>n=0,1,2,\cdots,m</math>，原命题均成立。

=== 完整归纳法 ===
另一个一般化的方法叫完整归纳法（也称第二数学归纳法或强归纳法），在第二步中我们假定式子不仅当<math>n=m</math>时成立，当''<math>n</math>''小于或等于<math>m</math>时也成立。这样可以设计出这样两步:
# 证明当<math>n=0</math>时式子成立.
# 证明当<math>n\leq m</math>时成立，那么当<math>n=m+1</math>时式子也成立.

例如，这种方法被用来证明：

:<math>\mathrm{fib}(n)=\frac{\Phi^n-\left(-\Phi\right)^{-n}}{5^{\frac{1}{2}}}</math> 

其中 <math>\mathrm{fib}(n)</math>是第''<math>n</math>''个[[斐波纳契数]]和<math>\Phi =\frac{1+5^{\frac{1}{2}}}{2}</math>（即[[黄金分割]]）。如果我们可以假设式子已经在当<math>n=m</math>和<math>n=m-1</math>时成立，从<math>\mathrm{fib}(m+1)=\mathrm{fib}(m)+\mathrm{fib}(m-1)</math>之后可以直截了当地证明当<math>n=m+1</math>时式子成立.

这种方法也是第一种形式的特殊化：
# 定义<math>\mathrm{P}(n)</math>是我们将证的式子,
# <math>\mathrm{P}(0)</math>'''和'''<math>\mathrm{P}(1)</math>成立
# <math>\mathrm{P}(m+1)</math>在<math>\mathrm{P}(m)</math>和<math>\mathrm{P}(m-1)</math>成立时成立。
结论：<math>\mathrm{P}(n)</math>对一切自然数''<math>n</math>''成立。

=== 超限归纳法 ===
{{main|超限歸納法}}
最后两步可以用这样一步表示：
:证明如果式子在所有的<math>n<m</math>成立，那么式子在当<math>n=m</math>时也成立。

实际上这是数学归纳法的大多数通式，可以知道他不仅对表达自然数的式子有效，而且对于任何在[[良基集合|良基集]]（也就是一个[[偏序]]的集合，包括有限降链）中元素的式子也有效（这里"<math><</math>"被定义为<math>a<b</math> [[当且仅当]]<math>a\leq b</math>和<math>a\neq b</math>）。

这种形式的归纳法当运用到[[序数]]（以[[良序]]的和一些的良基类的形式）时被称为[[超限归纳法]]，它在[[集合论]]、[[拓扑学]]和其他领域是一種重要的方法。

要区别用超限归纳法证明的命题的三种情况：
# <math>m</math>是一个极小元素，也就是没有一个元素小于''<math>m</math>''
# ''<math>m</math>''有一个直接的前辈，比''<math>m</math>''小的元素有一个大的元素
# ''<math>m</math>''没有任何前辈，也就是''<math>m</math>''是一个界限序数.

参见数学归纳法的三种形式。

==形式寫法==
===使用二階邏輯===
[[二階邏輯]]可捕捉數學歸納法這概念，表達成如下邏輯式：
: <math>\displaystyle\forall P\Bigl( P(0) \land \forall k \bigl( P(k) \Rightarrow P(k+1)\bigr ) \Rightarrow \forall n \bigl(P(n)\bigr)\Bigr)</math>，
<math>P(.)</math>是容納一[[自然數]]的述詞變元，遍歷所有述詞而非個別數字，為二階量詞（是故此式與二階邏輯有關），<math>k</math>與<math>n</math>則是自然數變元，遍歷所有自然數。

白話解釋此式，此式說：起始步驟<math>P(0)</math>與推遞步驟（即歸納假設，<math>P(k)</math>蘊涵 <math>P(k+1)</math>） 兩步成立會導出對任一自然數<math>n</math>， <math>P(n)</math>成立之結論。通常，我們為了證明第二步，會假設<math>P(n)</math>成立（歸納假設），再進一步證明<math>P(n+1)</math>。此牽涉到[[條件證明|條件證法]]，將條件句之前件作為假設，假定其正確以便於證明。

===使用一階邏輯===
若用[[一階邏輯]]將數學歸納法[[公設]]化，則須採用[[公理模式|公設模式]]，替每一個可能存在的述詞設下針對其的獨立公設。舉例而言，我們僅允許三個一階述詞存在，分別名為<math>P_1</math>、<math>P_2</math>、<math>P_3</math> ，則原先以二階邏輯描述的公設可改寫為：
: <math>\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)</math>，
: <math>\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)</math>，
: <math>\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)</math>，
。然而其強度與以二階邏輯描述之邏輯式不同，前者較後者弱。理由為一階邏輯述詞之數量為可數，而二階邏輯量限所迭代的集合為不可數。

此外，二階邏輯所表示的歸納公設綜合其它[[皮亞諾公設]]為同疇(categorical)，且所得之自然數[[結構 (數理邏輯)|模型]]無限大。根據[[勒文海姆-斯科倫定理]]，用一階邏輯表達的[[數理邏輯|理論]]若有可數無限大的模型，則其有不可數大的模型，是故無法前頭將所述的模型公設化<ref>{{Cite book|author=Derek Goldrei|title=Propositional and predicate calculus: a model of argument|url=https://archive.org/details/propositionalpre00gold|publisher=Springer-Verlag London|date=2005|pages=[https://archive.org/details/propositionalpre00gold/page/n291 286]-287|ISBN=1-85233-921-7|language=en}}</ref>。亦即，用二階邏輯表達的公設僅允許一群模型彼此[[同構]]，而一階邏輯模型則因前述定理，並非每個模型都同構。

===使用一階ZFC集合論===
一階[[ZFC|ZFC集合論]]不允許述詞被遍歷， 但我們可以藉由遍歷集合，繞過一階邏輯之限制，描述歸納法：
: <math>\forall A \Bigl( 0 \in A \land \forall k \in \mathbb{N} \bigl( k \in A \to (k+1) \in A \bigr) \to \mathbb{N}\subseteq A\Bigr)</math>
<math>A</math> 本身是集合，但可視作命題——只要命題在這數下成立，數字就會收入集合。別於皮亞諾公設，將數學歸納法定為公設，ZFC集合論直接定義自然數，使得歸納法本身是[[定理]]而非公設。

== 数学归纳法的合理性 ==

[[皮亞諾公理]]視數學歸納法不證自明，設作[[公理]]，而於[[策梅洛-弗兰克尔集合论]]，數學歸納法可从[[良序定理]]推导出来。<ref>{{cite web|title=Well Ordering Principle and the Principle of Mathematical Induction|url=https://nptel.ac.in/courses/111104026/lecture2.pdf|language=en|accessdate=2019-02-03|archive-url=https://web.archive.org/web/20171119023627/http://nptel.ac.in/courses/111104026/lecture2.pdf|archive-date=2017-11-19|dead-url=yes}}</ref> 需要注意的是数学归纳法只能判定'''给定'''命题的'''真'''，而不能'''证伪'''，因为在[[形式]]变换这一过程需要一定技巧与[[灵感]]。[[抽象与具体|抽象]]的[[概念]]如[[自然数]]，可通过抽象的工具去处理。通过[[有限]]的步骤处理[[无限]]的[[对象 (哲学)|对象]]如证明[[质数]]的无穷。

== 參見 ==
* [[归纳推理]]
* [[演绎推理]]
* [[结构归纳法]]
* [[完整归纳法]]

== 參考文獻 ==
{{reflist}}
== 外部链接 ==
* [http://www.cut-the-knot.org/induction.shtml Mathematical Induction, Examples] {{Wayback|url=http://www.cut-the-knot.org/induction.shtml |date=20060404100052 }}{{en}}

[[Category:初等數學]]
[[Category:數學哲學]]
[[Category:數學推理]]