證明不神秘，本質上就是用有說服力的論述說明某個陳述是正確的。證明的典型步驟是從下面三者之一匯出一些陳述：1）假設2）已經匯出的陳述3）其他廣泛認可的事實。
術語「匯出」含義是利用邏輯推理的通用原理進行推導。對「廣泛認可的事實」和「邏輯推理的通用原理」的定義的嚴格程度決定了證明的形式化和詳細程度。這裡有兩種極端，太詳細和太初略。
通常證明涉及命題p q，已知p為真，要說明q也為真。
37頁例子2.1是構造性證明的乙個例子。反例法和反證法。
我們的一些結論與自然數相關，要證明對於所有的自然數，結論都成立。假設p(n)是乙個有關整數的命題，為了證明對於所有的n>=n0，p(n)都成立，只要證明下面兩項：
1）p(n0)是成立
2）對於任意的k>=n0，如果p(k)成立，則p(k+1)成立。
使用數學歸納法的乙個好習慣：
1）精確地寫出歸納基礎（初始值）成立
2）精確地寫出歸納假設
3）精確地寫出要證明的歸納命題
4）證明歸納命題，並指出何處應用了歸納假設
最小反例原則（minimal counterexample principle），47頁例子2.10。
假設p(n)是乙個有關整數的命題，為了證明對於所有的n>=n0，p(n)都成立，只要證明下面兩項：
1）p(n0)是成立
2）給定任意的k>=n0，如果對任意的n0<=n<=k，p(n)都成立，則p(k+1)成立。
強原則也稱為完全歸納原則，或course-of-values歸納。你可以總是使用強原則。
例子：n! = 1 if n=0
n*(n-1)! otherwise
很容易發現遞迴定義與數學歸納法的相似性。許多定義既可以採用遞迴方式，又可以採用非遞迴方式，但遞迴定義具有一些優點：直觀、揭示了運算的過程，更符合事務的本質，且提供了構造數學歸納法的自然的方法。
l*的遞迴定義：
1） l*
2）如果x l*，y l*，則xy l*
3）僅由規則1）和規則2）得到的字串
回文pal的遞迴定義：
1） pal
2）如果a ，則a pal
3）如果a ，x pal，則axa pal
4）僅由上面3個規則產生的字串
回文的非遞迴定義是：正序和倒序相同的字串。顯然，遞迴定義提供了乙個構造和判別回文的方法。
人類擅長描述性定義，而計算機擅長構造性定義，遞迴定義則是構造性定義的一種。兩種定義的轉換是乙個難點。
規則的最後一條的更精確說法是有限次應用上述規則。
結構歸納法原理：假設u是乙個集合，i是u的乙個子集，op是u上的一組操作，集合l遞迴定義如下：
1）i l
2）l在op操作下保持封閉性
3）l是滿足條件1）和條件2）的最小集合
要證明集合l中的每個元素滿足性質p，只要證明下面兩條：
1）i中每個元素滿足性質p
2）l中元素在操作op下保持性質p
結構歸納法是專用於遞迴定義的證明方法。理解「保持封閉性」和「保持性質」的含義。
例子2.22，要分清集合是什麼？性質是什麼？操作是什麼？
證明對每個x *和y *，連線後的字串長度是兩個字串長度之和，即|xy|=|x|+|y|。
首先遞迴定義字串長度，然後將x看成固定量，對y進行結構歸納法證明，見61頁和62頁。
最後指出，結構歸納法實質上是數學歸納法，兩種方法可以互相轉換。
數學歸納法
數學歸納法製作人 徐凱 精講部分 年級 高三科目 數學型別 同步 難易程度 中建議用時 20 25min 一.知識點 1 數學歸納法的定義 一般地，證明乙個與正整數n有關的命題，可按下列步驟進行 只要完成這兩個步驟，就可以斷定命題對從n0開始的所有正整數n都成立 這種證明方法叫做數學歸納法 2 數學...
數學歸納法
最小數原理 已知，則，使得。證明若是有限集，且，那麼中元素可以按小到大的順序排列，取為其中最小的那個元素，則，使得。若為無限集，且，那麼是可列的，因而中元素可以按小到大的順序列出，取為其中最小的那個元素，則，使得。綜上所述，若，則，使得。定理 設a是乙個非空集合，對，命題p n 成立 假如，命題p ...
數學歸納法 整理
數學歸納法 資料 學歸納法證明與遞迴定義法的合法性依據 如何避免乙個表面上的 惡性迴圈 即用歸納法定義自然數，然後由此出發來證明自然數上數學歸納法的可行性?算術理論的形式展開 乙個少年時代的疑問之終結 如何嚴格證明加法與乘法的結合律，交換律與分配律?定律 postulates 轉化為 定理 theo...