本專題講座將集中討論數學歸納法、無窮遞降法、遞推方法的原理以及在解數學競賽題中的應用。
§1 數學歸納法
peano 自然數公理所謂自然數，是指乙個集合n裡某些元素之間有一基本關係，稱為「直接後繼」（用「,」表示，比如5是4的直接後繼，記為，5稱為4的後繼數）。並且集合n滿足下列條件：
ⅰ 「1」是自然數；
ⅱ 每個自然數的後繼數是自然數；
ⅲ 如果、都是自然數的後繼數，則；
ⅳ 1不是任何自然數的後繼數；
ⅴ 任意乙個自然數的集合，如果包含1，並且假設包含，也一定包含的後繼數，那麼這個集合包含所有的自然數。
定理1 （最小數原理）任意乙個自然數的集合n，如果不是空集，必有最小數。
定理2 （第一數學歸納法）如果關於自然數的某個命題具備下列條件：
（1）真；
（2）真則真，那麼對真。
定理3 （第二數學歸納法）如果關於自然數的某個命題具備下列條件：
（1）真；
（2）時，真真，則對，真。
上述的定理2、定理3為我們提供了證明關於自然數的命題的一種方法。應用定理2或定理3實現證題的方法叫做用數學歸納法證題。
例1 求證對
例2 證明：
例3 用天平稱重量，若砝碼只能放在一邊，證明：用1,2,4,8,…,2克的砝碼，可以稱出1,2,3,…，克的重量。
例4 證明：如果和是方程的根，則對任意都是整數，且不能被5整除。
例5 證明：任何由個相同的數字組成的整數，能被整除（如222,777都能被3整除，而***和555555555都能被整除等等）。
例6 1985個點分布在一圓的圓周上，每個點標上+1或，乙個點稱為「好點」，如果從這點開始，依任一方向繞圓周前進到任何一點時，所經過的各數的和都是正數。證明：如果標有的點少於662個時，圓周上至少有乙個「好點」。
§2 無窮遞降法
哪個無理數最「古老」？不容置疑是。雖然我們不能確切知道是誰第乙個證明了是無理數，但仍有必要對歷史上證明為無理數的方法作些分析。
是無理數的第乙個證明：
假設是有理數，在幾何學上，這意味著正方形的對角線長同它的邊長可以公度，即存在長為的線段和整數、使得：在對角線ac上放置個點，在邊dc上放置個點。它們分這兩條線段的長是的小段。
在ac上取線段ak，使；在dc上取線段de，使點k和e與取的分點重合（如圖）
我們證明，∽。因為這兩個三角形中為公用角，這意味著只要檢驗就足夠了。
由於，所以，
因為，所以，開方得
這樣一來，∽由於是等腰直角三角形，也是等腰直角三角形，並且我們可以在的邊上通過類似於對的邊上那樣的作法，在ec上擷取線段，使得，在kc上擷取線段，使，點和又與分點重合，有是等腰直角三角形，對我們用同樣的方法作，這個程式可以無止境地繼續下去，在這種情況下，變得非常小，但任意多次後點和仍將重合於線段ac和cd在開始時的分點。這些分點只有有限個，而無限變小，即的邊長無限變小，這樣引出了矛盾，從而證明了是無理數。
第二個證明：
的無理性意味著沒有這樣的自然數與滿足方程。假設有這樣的解，並且是解中的乙個，即
由方程得出是偶數，設，代入方程中，得到，即也是方程的解。我們發現，此時由於是偶數，設，因此，，這樣一來，是方程的解。在這種情況下，，我們可以進一步同樣求得比小根、還小的方程的解；….
這已經得到了矛盾。因為所有數都是自然數，而自然數的無窮遞降序列是不可能存在的，這意味著，我們的假設是錯誤的，數應是無理數。
以上關於是無理數的兩個證明，實質上是按乙個模式進行的。即假設問題有序，我們構造某個無窮遞降過程，同時根據問題本身的意義，這個過程應當是有限的。這種方法叫做無窮遞降法。
在證明過程中，我們經常採用簡單形式的遞降法，即假設我們已經達到過程的唯一的終點，但我們發現，「停止」是不可能的。
相傳歷史上無窮遞降法可能被古希臘數學家描述過。比較有根據的推測是：費爾瑪曾企圖應用這個方法證明沒有自然數解。
第三個證明：
設是方程的解中取值最小的。數應當是偶數，.因此，也是方程的解。然而，這與是取值最小的解相矛盾。
在這個證明中，我們見到遞降法與數學歸納法都把前面介紹過的最小數原理作為證明的依據。遞降法的特點決定了它對地些證明「否定式」的命題很方便。
例1 證明：在自然數範圍內，方程沒有解。
例2 證明：方程沒有自然數解。
例3 求方程的全部自然數解。
例4 有個砝碼，它們每乙個重量都是整數克。已知其中任意個砝碼都可以這樣放在天平上，每邊放上即可實現天平平衡。證明：所有的砝碼具有相同的重量。
例5 試問能夠把乙個立方體分割成若干個彼此不等的立方體嗎？
例6 給出乙個網格為正方形的座標紙，證明：當時，不存在這樣的正邊形，它的頂點都在格點上。
§3遞推方法
我們先看乙個趣題。
例有乙個10層的台階，若是每次可以上一層或二層，問共有多少種上法？
解設層台階有種上法，依題意
，； （*）
在（*）式中，令，求得，，
，，，，
即上10層台階共有89種上法。
這裡表明了第項與第項和第項之間的關係，我們把這種關係叫遞迴關係。
定義乙個數列的連續項之間的關係叫做遞迴關係。
由遞迴關係確定的數列叫遞迴數列。用遞迴關係來解題的方法是一種重要的數學方法，通常叫遞推方法。
乙個數列叫做一階遞迴數列，如果它滿足遞迴關係。由此可推得.其中叫初始值，一階遞迴數列由遞迴關係和乙個初始值來確定。
等差數列：（其中為非零常數）；
等比數列：（其中為常數）都是一階遞迴數列。
滿足關係的數列叫二階遞迴數列。二階遞迴數列需要由遞迴關係和兩個初始值來確定。
一般地，滿足遞迴關係的數列叫階遞迴數列。階遞迴數列要由遞迴關係和個初始值來確定。
遞迴方法通常用來解決「集合計數」問題，即計算有限集中元素的個數。
有限集合計數，通過建立遞推關係，求解遞推關係來解決。
下面我們通過一些例題，講講怎樣建立遞推關係。
例1 在乙個圓的直徑兩端寫上自然數1，將此直徑分得的兩個半圓都對分，在每個分點上寫上該點相鄰兩數之和（即1+1=2）。然後，又把所分得的四個圓周各自對分，在所得分點寫上該點相鄰兩數之和（即1+2=3）。如此繼續下去，問這樣到第步，圓周上所有分點的數之總和是多少？
例2 把圓分成個不相等的扇形，並且用紅、藍、黃三種顏色給扇形染色，但不許相鄰的扇形有相同的顏色。問共有多少種染色法？
例3 假定有個外徑不相等的圓環，套在一尖端朝上的木釘上，最大的圓環在最底層，形成乙個上小下大的「塔」（如圖）。另外，在充分遠處還有兩個釘子豎直釘在木板上。我們希望將這些圓環全部移到第二根釘子上，而一次僅能移動乙個圓環，但在每一移動中，都不能將大圓環置於小圓環之上，這當然要靠第三個釘子的輔助。
試問最少的移動次數是多少？
例4 某人給六個不同的收信人寫了六封信，並且準備了六個寫有收信人位址的信封。問有多少種投放信箋的方法，使每封信箋與信封上的收信人都不相符？
例5 求方程(是正整數)的正整數解的個數。
例6 設a和e是乙個正八邊形相對的頂點。一青蛙由a點出發，按照如下的規則跳躍；除e點外，不論在哪一點，都可跳到與這點相鄰的兩個頂點之一，當到達e點時，不得再跳，而停留在那裡。設為以e為終點的次跳躍的所有不同途徑的數目。
求證：，式中
求遞推數列通項公式的十種策略
一、利用公式法求通項公式
例1、已知數列滿足，求數列的通項公式。
二、利用迭加法求通項公式
例2、已知數列滿足，求數列的通項公式。
例3、已知數列滿足，，求數列的通項公式。
例4、已知數列滿足，，求數列的通項公式。
三、利用迭乘法求通項公式
例5、已知數列滿足，，求數列的通項公式。
例6、（04年，全國，15）已知數列滿足則的通項
四、利用待定係數法求通項公式
例7、已知數列滿足，，求數列的通項公式。
例8、已知數列滿足，，求數列的通項公式。
例9、已知數列滿足，，求數列的通項公式。
五、利用對數變換法求通項公式
例10、已知數列滿足，，求數列的通項公式。
六、利用迭代法求通項公式
例11、已知數列滿足，，求數列的通項公式。
七、利用數學歸納法求通項公式
例12、已知數列滿足，,求數列的通項公式。
八 、利用換元法求通項公式
例13、已知數列滿足,，求數列的通項公式。
九、利用不動點法求通項公式
例14、已知數列滿足,，求數列的通項公式。
例15、已知數列滿足,，求數列的通項公式。
十、利用特徵根法求通項公式
例16、已知數列滿足,，求數列的通項公式。
引申：可轉化為特徵方程求通項的幾類遞推數列
特徵方程是解決遞推數列問題的重要方法，但有些遞推關係並不是以我們常見的形式出現，因此，不能直接使用特徵方程，必須通過適當的轉換。現加以分類列述。
一、消常數轉化法
例1：已知數列滿足，求通項公式。
例2：設數列，滿足，且。證明：是完全平方數。
二、利用韋達定理轉化
例4：數列的定義如下：，證明：不可能有正整數m ，使被2007整除。
三、強化，轉換命題進行轉化
例5：正整數數列定義如下：。
求該數列的通項。
高考物理解題方法遞推法方法歸納
六 遞推法 方法簡介 遞推法是解決物體與物體發生多次作用後的情況。即當問題中涉及相互聯絡的物體較多並且有規律時，應根據題目特點應用數學思想將所研究的問題歸類，然後求出通式。具體方法是先分析某一次作用的情況，得出結論。再根據多次作用的重複性和它們的共同點，把結論推廣，然後結合數學知識求解。用遞推法解題...
幾類常見遞推數列的解題方法
疊加 疊乘 迭代遞推 代數轉化 幾類常見遞推數列的教學隨筆 436032 湖北省鄂州市葛店高階中學廖傳堯 已知數列的遞推關係式求數列的通項公式的方法大約分為兩類 一類是根據前幾項的特點歸納猜想出a的表示式，然後用數學歸納法證明 另一類是將已知遞推關係，用代數法 迭代法 換元法，或是轉化為基本數列 等...
小公升初數學總複習歸納講義
學人教育2010 2011小公升初數學總複習資料歸納講義 持有人 劉老師 一年級上冊 數一數 比一比 1 5的認識和加減法 認識物體和圖形 分類 6 10的認識和加減法 11 20各數的認識 認識鐘錶 20以內的進製加法 總複習 一年級下冊 位置 20以內的退位減法 圖形的拼組 100以內數的認識 ...