數學歸納法為什麼是對的？如何證明其正確性？

12-27

本人高中學生，數學老師上課講了數學歸納法，但是並沒有說明為什麼這個方法是正確的，我感到相當困惑，請問可否有人比較直白的解釋一下數學歸納法為什麼可以用來證明數學問題？第一次在知乎提問，若有不妥之處請告知，我一定改正。

之前有上過一門課叫現代數學與中學數學，老師說到了學生要能夠在認知上接受這個命題 $Q(n):P(n) ightarrow P(n+1)$ ，而這個 $Q(n)$ 是否成立，是由 $P(n) ightarrow P(n+1)$ 這個整體決定的，更簡單的說就是這個 $ightarrow$ 能否成立，然後還有初值的驗證，這樣對數學歸納法的原理的理解才算完整的.
對於高中生而言，要認識到數學歸納法所建立的是一種傳推關係 $P(1) ightarrow P(2) ightarrow ... ightarrow P(n) ightarrow ...$
然後把數學歸納法看成一個過程，而不是結果，這樣理解會比較好……（怎麼感覺還是不好理解啊）

但是我還是覺得老師講起來好難！！！

如果要更為深入的了解數學歸納法之前，就要先看看Peano公理.
這個理論用公理化的方法從順序的角度揭示了自然數的意義，就是我們平常說的自然數1,2,3……理解為第一個，第二個，第三個……
這個公理是這樣子的：

1是自然數；

每一個確定的自然數 $a$ ，都有一個確定的後繼數 $a$ ， $a$ 也是自然數（一個數的後繼數就是緊接在這個數後面的數，例如，1的後繼數是2，2的後繼數是3等等）；

對於每個自然數 $b$ 、 $c$ ， $b=c$ 當且僅當 $b$ 的後繼數= $c$ 的後繼數；

1不是任何自然數的後繼數；

任意關於自然數的命題，如果證明了它對自然數1是對的，又假定它對自然數 $n$ 為真時，可以證明它對 $n$ 也真，那麼，命題對所有自然數都真.（這條公理保證了數學歸納法的正確性）

而第五條一般就是我們所說的歸納公理，設S是正整數集的一個子集，且
（1）1屬於S
（2）如果n屬於S，那麼n+1也屬於S
那麼，S就是正整數集.

我們高中所接觸的數學歸納法是第一數學歸納法：

設 $P(n)$ 是一個與自然數有關的命題，如果：
1° $P(1)$ 成立；
2°假設 $P(k)$ 成立，則 $P(k+1)$ 成立；
那麼 $P(n)$ 對所有自然數都成立.

由歸納公理就可以知道第一數學歸納法的正確性。

因為前面的答案提到了最小數原理，那我就順便再提一提第二數學歸納法：

設 $P(n)$ 是一個與自然數有關的命題，如果：
1° $P(1)$ 成立；
2°假設 $P(n)$ 對於所有滿足 $l<k$ 成立，則 $P(k)$ 成立；
那麼 $P(n)$ 對所有自然數都成立.

它的理論依據是最小數原理——自然數集的任一非空子集必有一個最小數

證明一下下吧：
設 $A$ 為 $N$ 的任一非空子集，由Peano公理2.
假設 $nin N$ 且 $n e 1$ ，則 $n$ 必為某一自然數 $m$ 的後繼，
所以 $n=m$ 1" eeimg="1">，所以自然數集 $N$ 有最小數1
所以當 $1in A$ 時， $A$ 有最小數1,
當 $1 otin A$ 時，假設 $A$ 沒有最小數，構造集合 $T=$ { $x|xin N$ 且對 $forall ain A,x}，則<img src=$ .
假設 $nin T$ ，若 $n+1in A$ ，則 $n+1$ 為 $A$ 中的最小數，與假設矛盾，所以 $n+1in T$
那麼 $1in T$ ， $nin T$ 時， $n+1in T$ ，由歸納公理 $T=N$ .
則 $A$ 為空集，與 $A$ 為非空集合矛盾

第二數學歸納法的證明就是利用最小數原理啦~我簡單寫一下吧：
設 $M$ 是滿足 $P(n)$ 成立的所有自然數 $n$ 的集合，設 $T=N-M$ ，
然後假設 $T$ 不為空集，根據最小數原理， $T$ 有最小數 $t_{0}$ ，
由條件1° $P(1)$ ，就有 $1in M$ ，然後就有 $t_{0} e 1$ ，所以1,2， $t_{0} -1in M$ 成立；
由條件2° $t_{0} in T$ 矛盾了，然後 $T$ 就是空集啦，然後 $M=N$ 啦，然後那麼 $P(n)$ 對所有自然數都成立。

還有幾種數學歸納法我就不說了……我把自己講暈了ToT

其實，數學歸納法不僅僅只能證明與自然數有關的命題，它還能證明那些可以與自然數集建立一一對應的集合的有關的命題，像算術基本定理，輾轉相除法什麼的……它在數論這樣的學科用處也好大，可以證那些與自然數的性質有關的定理……

但是！不是所有的與自然數有關的命題都可以用數學歸納法來證明，Fermat定理（當 $n>2$ 時， $x^{n} +y^{n} =z^{n}$ 沒有正整數解就沒辦法通過 $n$ , $x,y,z$ 來證明）

不過要給沒有接觸過Peano公理的高中小朋友們的學習中，對自然數集的這個性質的理解不夠，然後就不能認識到數學歸納法的結構特徵，就會很難理解這一基本原理的實際含義，我就記得課本上的被講爛了的多米諾骨牌跟火車車廂的例子，聽完之後，我自己都有點對數學歸納法的合理性不確定了……
當高中老師真的挺不容易的啊喂(#`O′)

數學歸納法的正確性來自Peano公理，是不需要證明的。數學歸納法與自然數是良序的（即每個非空子集都有最小元）等價。

第一步：良序原理在自然數集上的一個推論說的是，自然數的非空子集有最小元

第二步：假設在歸納法條件下，使得命題不成立的自然數集合是U

第三步：若U是空集，則證明完畢

第四步：若U不是空集，則U有最小元u，由條件知u≠1，那麼u-1?U，那麼u?U，導致矛盾

$ext{nat\_ind} : Pi(P:mathbb{N} ightarrow ext{Prop}).P(0) ightarrow[Pi(n:mathbb{N}).P(n) ightarrow P(n+1)] ightarrow[Pi(n:mathbb{N}).P(n)]$
從 CiC 角度看每個可以歸納的類型都自帶一個上圖畫風的玩意兒（不動點算符），歸納法就是利用這個東西定義遞歸函數/歸納性證明而已。和 General recursion 相比使用不動點算符可以保證 totality，即證明的正確性。

首先呢題主需要清楚現代數學是建立在一套公理體系之上，即所有的數學定理都是從這有限多個公理推導而來。現在基本通用的一套是ZFC公理系統，由這個公理系統是可以導出數學歸納法的，不過具體過程比較繁瑣一些，介於題主是高中生，有可能無法理解其中的部分內容，所以這裡也不細講了。大致來說這涉及到對自然數的定義，而在定義自然數的時候已經讓它滿足數學歸納法的條件了。本人第一次知乎答題，對於這方面的知識也了解的不太多，如有不妥當之處還請多指教。

看到很多答案都提到數學歸納法是一種遞歸的證明的理解思路。這樣理解是沒問題的。
但是從嚴格的數學角度來說，數學歸納法是一個嚴格的數學定理，注意不是公理。它是可以在集合論的一系列公理下被證明的。
自然數集上的第一數學歸納法即如下定理：

定理（第一數學歸納法）：一個與自然數（整數）n有關的命題P（n），如果滿足P（0）（P（1））成立，並且有P（n）→P（n+1）。那麼對於任意n，P（n）成立。

證明：
反證法，假設上述定理不正確，即
A={n|P(n)不成立} 非空。
由於A是自然數集的非空子集，並且自然數集是良序的，故A有最小元素a∈A（a≠0），並且a－1?A。
由A的定義，P(a)不成立而P(a－1)成立，這與條件P(n－1)→P(n)矛盾，原定理得證。

數學歸納法無論從定義和證明上都是嚴格描述的命題，與歸納和遞歸無關，所謂歸納只是一種理解方式而已。

數學歸納法也有很多種，高中所學的上述定理稱為自然數集上的第一類數學歸納法，除此之外還有第二數學歸納法和一系列超限歸納法。特別要指出的是，其中超限歸納法的證明是依賴於良序定理（即依賴於選擇公理）的。

在書上看到一個簡潔的證明，需要用到上面提到的「最小數原理——自然數集的任一非空子集必有一個最小數」，最小數原理我覺得是比較直觀的，隨便取自然數的一個非空子集，肯定有一個最小的元素。
歸納法：
設 $P(n)$ 是一個與自然數有關的命題，如果：
1° $P(1)$ 成立；
2° $P(k)$ 設成立，則 $P(k+1)$ 成立；
那麼 $P(n)$ 對所有自然數都成立.

下面用反證法證明歸納法的正確性：
如果P（n）不成立，且令S是P（n）為假的n的集合，S是非空集合，則根據最小數原理，S中必然存在最小元素，記為s,根據歸納法的第一個條件，P(1)是成立的，s $e$ 1。又根據集合S的定義，P（s-1）是成立的（因為如果P（s-1）不成立，則s不是S的最小元素），此時根據第二個條件，P（s-1+1）成立，則s $otin$ S，這就出現了矛盾，因此，歸納法是正確的。

維基百科上有解釋。
就像多米諾骨牌：你先證明第一塊你能推倒，
再證明n+1塊你也能推倒，就像傳導一樣，n=1時，第2塊就會倒，n=2時，第3塊就會倒，傳導下去，所有的都會倒，
所以按照這個邏輯你可以把整個多米諾都推倒。
我解釋的比較簡單，你自己去維基百科看看
https://zh.wikipedia.org/wiki/%E6%95%B0%E5%AD%A6%E5%BD%92%E7%BA%B3%E6%B3%95

在讀高中的時候，我就覺得這個數學歸納法太厲害了，遇到不會做的證明題，只要祭出這一大殺器就沒有問題了。當時就這個疑問，為什麼只需要證明這兩點就可以了呢？但是沒有深究過，今天看到了題主的問題，仔細思考了一下，覺得可以如下解釋。
因為個人水平有限可能有回答不準確的地方，還請指出來，也希望以下的解釋能夠解決題主的疑惑。

所謂的數學歸納法是指，如果一個定理對於任意的正整數 $n$ 都成立，那麼我們只需要證明兩點就可以了：

該定理對 $n=1$ 成立；
如果該定理對 $n=k$ 成立，那麼對 $n=k+1$ 也成立。

如果我們能夠窮舉出所有的正整數，證明它對於每一個正整數命題都成立，那麼就證明了這個命題對於任意的正整數 $n$ 都成立。而實際上正整數的個數是無限多的，我們不可能窮舉之。

我們把正整數集 $N_+$ 劃分為 $S$ 和 $ar{S}$ 兩個子集，其中 $S$ 是由使命題成立的正整數構成的集合，而 $ar{S}$ 則是不能使命題成立的正整數集合，顯然有 $N_+ = S cup ar{S}$ 。我們只需要證明 $phi = ar{S}$ 或者 $N_+ = S$ ，即可。

對於數學歸納法中使待證命題成立的第一個條件，我們有 $1 in S$ 。根據第二個條件，我們可以很容易證明 $2 in S, 3 in S, ..., k in S$ 。這就得到了一個集合 $T = left{1, 2, ..., k ight}$ 即 $T= left{ y | y in N_+, y <= k ight}$ 。顯然，集合 $T$ 是 $S$ 的一個子集，即 $T subset S$ 。

現在構建一個集合 $U = left{z | z in N_+, z > k<br /> ight}$ ，顯然滿足 $N_+ = T cup U$ 。對於 $U$ 中的每一個元素 $z$ ，都可以根據第二個條件證明 $z in S$ 。所以 $U$ 也是 $S$ 的一個子集。那麼我們就證明了 $T cup U subseteq S$ ，即 $N_+ subseteq S$ 。又因為 $S subseteq N_+$ ，所以 $N_+ = S$ 。

因此，只要證明了數學歸納法的兩個條件，我們就可以證明命題對任意正整數都成立。

然而大家都在用Peano公理證明數學歸納法的正確性，看著就有自圓其說的嫌疑。公理本身就是基於一種common sense的人為規定，你無法證明其正確性，要分析你可以去隔壁閑得蛋疼的哲學班討論這種common sense的本質意義。數學以人為定義的公理作為基元，然後在基元之上架構邏輯關係。而哲學才能辯證基元的意義… 這才是數學和哲學的區別… ⊙﹏⊙

自然數的皮亞諾式定義中的一點就是「一個符合數學歸納法的數集」(除了這一點外還有四點)；所以對於皮亞諾式自然數，數學歸納法按照自然數的定義(par définition)對於自然數有效。

希爾伯特繼承了這種公理化思路，本質上的套路就是讓對象詞和關係詞的意義服務於命題的真，為了命題的必然為真而把命題中的對象概念和關係概念抽象化，直接用命題的真來定義命題中的所有概念。

然！而！皮亞諾之前並不是沒有數學，而在那個漫長的無皮亞諾狀態下，你的問題的確無法被解答。誰能告訴我，如果只用皮亞諾公設前四條來定義自然數，他怎麼證明數學歸納法？！

要不我們先承認至少存在一個歸納集（就是那種空集是它的元素，如果a是，那麼a的後繼也是），交集引理定義最小歸納集（自然數集）

若A是自然數子集且A是歸納集，那麼A就是自然數集合

最後歸納原理也叫歸納法吧！

第二歸納法，要不假設0是自然數吧（其實…）
P
p--&>q
結論就是q
自然數最小數原理保證p是永真的（重言式），而我們只要求有（構造出來的）蘊含式子，
結論q一定是真的
證明呢，反證法…

https://www.youtube.com/watch?v=L3LMbpZIKhQlist=PLB7540DEDD482705B

看完前兩課就明白了吧。

數學歸納法是個公理(Induction axiom)，證明不了。我們默認數學歸納法就是對的。

數學歸納法成立是根據最小自然數原理來的，默認任何一個非空自然數集合都有一個最小的數。然後我們再根據反證法，假設數學歸納法不成立，那麼一定存在一個最小反例S(n)，由於S(1)成立，則n≥2。同時由於S(n)是最小反例，則必有S(n－1)成立，而根據條件此時必有S(n)成立，於是導出矛盾，所以原先的數學歸納法成立。

打一個不恰當的比方，自行車車棚里停滿了自行車，你證明了可以推到第1輛自行車，又證明了第n輛自行車倒下可以引起第n＋1輛車倒下，所以你一推所有車都倒了

參見二潘初等數論第一章

簡單的看了一下，並不是因為你真的不懂數學歸納法，老師在課堂上給你講的更多的是可以用數學歸納法來證明，但是卻沒有說明數學歸納法為什麼是正確的，即老師沒有給你證明「數學歸納法」是正確的。

我用一句話來說明，數學歸納法依賴於這樣的一個事實：任意一個自然數r,都有一個後繼的自然數r+1,而我們所求的自然數n可以從1經過這樣的有限步驟而達到。

如果你想有更多的理解，首先去理解自然數集，那麼這裡我可以推薦給你一本書《What Is Mathematics》，比較適合你去讀。

看了幾個學術答案表示自己數學水平有限，就從自己理解的角度談談。不是嚴謹的證明，只有助於理解。
數學歸納在高中試題里一般用來證明的是對於所有的自然數n，f(n)會滿足某些條件（例如大於零，是平方數，是兩個連續自然數的乘積等等）
主要有兩個步驟，第一步就是證明n等於前m個數時，這個結論是正確的。這其中，m大多數情況是1。
第二步就是證明n&>=m的時候，在假定f(n)成立的情況下能夠推導出f(n+1)也成立。
這樣就完成了對數學歸納法的證明。那為什麼這個證明有效呢？
簡單起見就把m取1好了。首先你證明了n=1的時候，f(1)是滿足條件的。由於第二步你又證明了n&>=1時，如果f(n)滿足條件，f(n+1)也能滿足條件。那麼由於f(1)滿足條件，那麼f(1+1)即f(2)也是滿足條件的。那麼f(2+1)即f(3)也滿足條件，那麼f(3+1)……………想像一下一直推導至無窮大，於是所有自然數都滿足條件了。

其實上面說的太死了，數學歸納法並不局限於自然數，題主可以發揮想像，舉一反三。

題主先回答我：
公理為什麼是對的？

樓上都太專業了。題主只是個高中生，剛剛上新課，一時沒理解過來數學歸納法的演繹邏輯。我覺得題主只不過想得到一個情感上接受數學歸納法的感性邏輯，而不是天書一樣的底層的公理體系。

其實按照高中階段的要求，把數學歸納法的邏輯認為是顯然正確的就可以了！
事件a：1號同學是對的。
事件b：如果n號同學是對的，那麼n+1號同學也是對的。
對於上面這兩句話，如果這兩句都是成立的。那麼會怎樣呢？因為1對所以2對；於是因為2對所以3對；因為3對所以4對……於是就知道了不管來了多少個同學，反正你們總都是對的（你們開心就好- -）
注意！注意上面這段邏輯中的「如果」。得出「同學們都是對的」這個結論的前提條件是事件a和事件b都是正確的，這兩件事情必須先確定才能進行後面的數學歸納。

數想記有詳細證明直達么公理你是個十分優秀的數學學者！你對數學是認真美好的！這就是興趣！遺憾的是中國人這種人幾乎沒有！對於這個問題一定要搞懂！?則學數學白學數學歸納法藏公理有7個多！是數學中非常少見的！有矛盾律！同一律！三：中中國的孩子讀數學確定是鷹式教育：殘酷，無情，汵血、壓迫！從而來獲得白骨精們的利益：有人說奧數甲天下我否！你能設計為下回棋的電腦程序嗎？你能設計製造電腦何時心片嗎！這就是直正的本領！情況非常的危急，話說時間如流水，銀河浩蕩奔騰去，知是冷月掛東來，欲問取經到何處？廣矛沙漠空想思！曲指1數逢7來！17、27，37、47炮彈飛！57、67·77！87？怎麼樣！兒今又逢7字頭！美帝扣門白骨精！人間己到患難時！請君計算概率來！核彈過後盡開顏！擺在朝鮮喉嚨的兩把尖刀！朝鮮是1個自強不屈的民族！如果棄核那麼它將倫為經濟值民地。成為美金的奴隸！而且第三世界也跟著倫為奴隸！同時帯來資本主義的短暫繁榮！如果不棄核！它可易守可攻擊美金用假美金打痽美帝國主義及走狗！但美國不為同意。

擺在美帝面前的三把尖刀：如果打朝鮮！那麼中國的開放大門將關閉！八國聯軍轟開的戰果將泡影。這對於美國來說是塌天！當年曰本坦言如如果清政府不給物質補給！那麼日本人最多能堅持六天！如果不打朝鮮，整個世界都將有核美金成了廢紙！我故計：長將永不輸！東北亞不會有戰爭————正真的軍事戰爭已轉移到輕經濟效益上————奴隸還有戰爭嗎？首先我可以肯定的告訴你！費馬大定律的初等證明存在！但是它要陽光！水！空氣！土壤！在能開花結果！我已經證明出來了！問題遠沒有那麼簡單！世界上除了我再沒有人能證明！1：要懂數學歸納法為什麼是對的證明！注意：數學歸納法好比是一輛汽車！不是讓你做車夫怎麼用運！而是為什麼它可以用運這對於中國人說是零！是的中國孩子奧數甲天下！車夫只是賺錢的苦力！中國孩子敢於為資本家效力！兒風光我服！但朋友你要點石成金術！不要類土！2：了解邏輯學：這又要注意；你學的邏輯例歐幾里德但它又夾雜著錯誤———祥見數想記朝鮮不是數學高手：從它的進程看：應局於大和民族：

數學歸納法是由良序性質定理證明的，
屬於數論的知識

自然遞降，沒記錯的話這是公理之一