歸納原理和數(shù)學歸納法

第三節(jié)歸納原理和數(shù)學歸納法1．數(shù)學歸納法的理論依據(jù)歸納法和演繹法都是重要的數(shù)學方法．歸納法中的完全歸納法和演繹法都是邏輯方法；不完全歸納法是非邏輯方法，只適用于數(shù)學發(fā)現(xiàn)思維，不適用數(shù)學嚴格證明．數(shù)學歸納法既不是歸納法，也不是演繹法，是一種遞歸推理，其理論依據(jù)是以下佩亞諾公理Ⅰ—Ⅴ中的歸納公理：Ⅰ．存在一個自然數(shù)0∈N；Ⅱ．每個自然數(shù)a有一個后繼元素a′，如果a′是a的后繼元素，那么a叫做a′的生成元素；Ⅲ．自然數(shù)0無生成元素；Ⅳ．如果a′=b′，那么a=b；Ⅴ．(歸納公理)自然數(shù)集N的每個子集合M，如果M含有0，并且含有M內(nèi)每個元素的后繼元素，那么M＝N自然數(shù)就是滿足上述佩亞諾公理的集合N中的元素．關(guān)于自然數(shù)的所有性質(zhì)都是這些公理的直接推論．由佩亞諾公理可知，0是自然數(shù)關(guān)于“后繼〞的起始元素，如果記0′＝1，1′=2，2′=3，…，n′=n＋1，…，那么N=｛0，1，2，…，n，…｝由佩亞諾公理所定義的自然數(shù)與前面由集合所定義的自然數(shù)，在本質(zhì)上是一致的．90年代以前的中學數(shù)學教材中，將自然數(shù)的起始元素視作1，那么自然數(shù)集即為正整數(shù)集．現(xiàn)在已統(tǒng)一采取上面的記法，將0作為第一個自然數(shù)．定理1(最小數(shù)原理)自然數(shù)集N的任一非空子集A都有最小數(shù)．這本是自然數(shù)集N關(guān)于序關(guān)系∈(＜)為良序集的定義．現(xiàn)在用歸納公理來證明．證設(shè)M是不大于A中任何數(shù)的所有自然數(shù)的集合，即M=｛n｜n∈N且n≤m，對任意m∈A｝由于A非空，至少有一自然數(shù)a∈A，而a＋1(＞a)不在M中．所然，就有1°0∈M(0不大于任一自然數(shù))；2°假設(shè)m∈M，那么m＋1∈M．根據(jù)歸納公理，應(yīng)有M＝N．此與M≠N相矛盾．這個自然數(shù)m0就是集合A的最小數(shù)．因為對任何a∈A，都有m0意a∈A，于是m0＋1∈M，這又與m0的選取相矛盾．反之，利用最小數(shù)原理也可以證明歸納公理．因此，最小數(shù)原理與歸納公理是等價的．定理2(數(shù)學歸納法原理)一個與自然數(shù)相關(guān)的命題T(n)，如果1°T(n0)(n0≥0)為真；2°假設(shè)T(n)(n≥n0)為真，那么可以推出T(n＋1)也為真．那么，對所有大于等于n0的自然數(shù)n，命題T(n)為真．證用反證法．假設(shè)命題T(n)不是對所有自然數(shù)n為真，那么M=｛m｜m∈N，m≥n0且T(m)不真｝非空．根據(jù)定理1，M中有最小數(shù)m0．由1°，m0＞n0，從而m0－1≥n0且T(m0-1)為真．由2°，取n=m0-1即知T(m0)為真．此與T(m0)不真相矛盾．從而證明了定理2．在具體運用數(shù)學歸納法進行數(shù)學證明時，有多種不同形式．運用定理2中兩個步驟進行證明的，為Ⅰ型數(shù)學歸納法．經(jīng)常使用的還有Ⅱ型數(shù)學歸納法，Ⅱ型數(shù)學歸納法是：如果命題T(n)滿足1°對某一自然數(shù)n0≥0，T(n0)為真；2°假設(shè)對n0≤k≤n的k，T(k)為真，那么可以推出T(n＋1)也真．那么．對所有大于等于n0的自然數(shù)，命題T(n)都真．定理3Ⅰ型數(shù)學歸納法和Ⅱ型數(shù)學歸納法等價．證假設(shè)命題T(n)對n=n0為真，于是只須證明“由T(n)(n≥n0)為真，可以推出T(n＋1)也為真〞的充要條件為“由T(k)(n0≤k≤n)為真，可以推出T(n+1)也為真．〞1°充分性假設(shè)“由T(n)(n≥n0)為真，可以推出T(n＋1)也為真〞，那么對n0≤k≤n，T(k)為真，特別T(n)為真，因此T(n＋1)也為真．2°必要性用反證法．假設(shè)“由T(k)(n0≤k≤n)為真，可以推出T(n＋1)也為真〞，但并非對所有大于等于n0的自然數(shù)n，由T(n)為真，可以推出T(n＋1)也為真，那么M=｛m｜m∈N，m≥n0且由T(n)為真推不出T(n＋1)也為真｝非空．由定理1，M中有最小數(shù)m0，且對n0≤k＜m0的k，由T(k)為真，可以推出T(k＋1)也為真．特別由T(n0)為真可知T(n0+1)為真，由T(n0＋1)為真可知T(n0＋2)為真，……，由T(m0－1)為真可知T(m0)為真．現(xiàn)T(n0)為真，所以T(n0)，T(n0+1)，…，T(m0)都為真，由此可知T(m0＋1)也為真，所以由T(m0)為真推出了T(m0＋1)也為真．這與m0的選取矛盾．由定理3可知，Ⅱ型數(shù)學歸納法也是合理的推理方法．2．數(shù)學歸納法在應(yīng)用中要注意的問題第一，證明的兩個步驟缺一不可第一步是歸納的根底，第二步是歸納的傳遞．尤其是不可無視第一步的驗證．例1試證1＋3＋5＋…＋(2n＋1)＝(n＋1)2＋1證假設(shè)當n=k時公式成立，那么1＋3＋5＋…＋(2n-1)＋(2n+1)＝［1＋3＋5＋…＋(2n-1)］＋(2n＋1)＝n2＋1＋2n＋1＝(n＋1)2＋1完成了數(shù)學歸納法的第二步，但結(jié)論顯然是錯誤的．為什么？因為缺少第一步．事實上，當n=0時，公式不成立．如果缺了第二步，那么不管對多少個自然數(shù)來驗證命題T(n)的正確性，都不能肯定命題對所有自然數(shù)都正確．例如，哥德巴赫猜測“任何不小于6的偶數(shù)都可以表成兩個奇素數(shù)之和〞，雖然對大量偶數(shù)進行了具體驗證，但因缺少第二步歸納傳遞，所以仍只停留在歸納的第一步上．它至今仍只是個猜測而已．第二，第二步在證明T(n＋1)為真時，一定要用到歸納假設(shè)，即要把“T(n)為真推出T(n＋1)為真〞或“T(n0)，T(n0＋1)，…，T(k-1)為真推出T(k)為真〞的實質(zhì)蘊含真正表達出來．否那么不是數(shù)學歸納法證明．例2設(shè)a1，…，an為n個正數(shù)，b1，…，bn是它的一個排列．試證證1°當n=1時，命題顯然成立．2°假設(shè)(*)式對n=k成立，那么當n=k＋1時根據(jù)數(shù)學歸納法原理，(*)式對所有大于等于1的自然數(shù)n都成立．這里雖然形式上完成了數(shù)學歸納法的兩個步驟，但第二步在證(*)式對n＋1成立的過程中，并沒用到(*)對n成立的歸納假設(shè)．因此，不能說上述證法是采用了數(shù)學歸納法．事實上，在上述證明中無須用數(shù)學歸納法，用平均值不等式證明就行了．第三，并不是凡與自然數(shù)相關(guān)的命題T(n)，都要用數(shù)學歸納法來證明；而且也不是所有這類命題都能用數(shù)學歸納法給以證明的．這一命題是與自然數(shù)相關(guān)的命題，盡管可以對n＝0，1，2，…進行驗證，但無法實現(xiàn)數(shù)學歸納法的第二步，因此不能用數(shù)學歸納法進行證明．事實上，數(shù)學歸納法只適用于具有遞歸性的命題T(n)．3．遞歸函數(shù)一個定義在自然數(shù)集N上的函數(shù)f(n)，如果它對于每個自然數(shù)n的值可以用如下方式確定：(1)f(0)=a(a為數(shù))；(2)存在遞推關(guān)系組S，當/f(0)，f(1)，…，f(n-1)值以后，由S唯一地確定出f(n)的值：f(n)=S［f(0)，f(1)，…，f(n-1)］那么，就把這個函數(shù)f(n)，稱作歸納定義的函數(shù)．簡稱遞歸函數(shù)．在具體的遞歸函數(shù)例子中，關(guān)系組S可能有幾個表達式，或者沒有明確的解析表達式，也可能需要給出f(n)的開頭假設(shè)干個值．這樣定義函數(shù)是合理的，因為我們有：定理4當遞推關(guān)系組S給定后，定義在N上的滿足上述條件(1)、(2)的函數(shù)f(n)是存在而且唯一的．證首先指出：對任一自然數(shù)k，總可以在片斷｜0，k｜上定義一個函數(shù)fk(n)，使fk(0)=a，對于片斷上其他自然數(shù)n，f(n)=S［f(0)，…，f(n-1)］．這個函數(shù)fk(n)是在｜0，k｜上唯一確定的．現(xiàn)對k進行歸納證明：1°當k＝0時，f0(0)＝a是唯一確定的；2°假定在｜0，k｜上已經(jīng)由(1)、(2)定義了一個唯一確定的函數(shù)fk(n)，令那么fk+1(n)在片斷｜0，k＋1｜上有定義，且(1)fk+1(0)=fk(0)=a；(2)fk+1(n)=S［fk(0)，…，fk(n－1)］=S［fk+1(0)，…，fk+1(n－1)］，n=1，2，…，k．因此，函數(shù)人fk+1(n)滿足條件(1)、(2)．由數(shù)學歸納法知，對任何自然數(shù)k，函數(shù)fk(n)在片斷｜0，k｜上唯一確定，且滿足(1)、(2)．又假設(shè)k1＜k2，那么fk1(n)與fk2(n)在片斷｜0，k1｜上完全一致．現(xiàn)作一新的函數(shù)：f(n)=fn(n)，n∈N．首先，函數(shù)f(n)對任一n∈N都有定義，且f(n)=fn(n)=S［fn－1(0)，…，fn-1(n－1)］=S［f0(0)，…，fn-1(n-1)］=S［f(0)，…，f(n-1)］又顯然f(0)＝f0(0)=a．故函數(shù)f(n)是定義在N上且滿足(1)、(2)的唯一確定的函數(shù)．例4設(shè)函數(shù)f∶N→N，且(1)f(0)=2，f(1)=3；(2)f(n＋1)＝3f(n)－2f(n－1)，n≥1．證明：f(n)＝2n＋1．這里給出的遞歸函數(shù)由f(0)、f(1)兩個值和一個關(guān)系式給定的關(guān)系組S確定．但有的遞歸函數(shù)f(0)的值隱含于關(guān)系組S之中而未直接給出．例5(IMO－19試題)設(shè)f：N+→N＋，且(S)f(n＋1)＞f(f(n))，n∈N+求證：對于任意n∈N＋，f(n)＝n．證先用數(shù)學歸納法證明命題An：任意正整數(shù)n，假設(shè)m≥n，那么f(m)≥n．顯然A1真．假設(shè)An-1真，那么對任意m≥n，f(m－1)≥n-1，故f(m)＞f(f(m－1))≥2n－1，于是f(m)≥n，從而An真．由此可知，f(n)≥n，f(n＋1)＞f(f(n))≥f(n)．于是f單調(diào)增加．又如果有一個n使f(n)＞n，那么f(n)≥n+1，f(f(n))≥f(n+1)，與條件(S)矛盾．故只能有f(n)=n．此題給出的遞歸函數(shù)，f(1)的值沒有明顯給出，但實際上隱含于關(guān)系組(S)中．4．遞歸命題一個與自然數(shù)相關(guān)的命題T(n)，一般來說，它未必是一個函數(shù)問題．現(xiàn)在采取如下方式來構(gòu)造命題T(n)的真值函數(shù)f∶N→｛1，0｝．如果命題T(n)的真值函數(shù)f(n)是遞歸函數(shù)，即1°f2°f(n＋1)=S［f(0)，…，f(n)］，且當f(0)=…=f(n)=1時，f(n＋那么就稱T(n)是具有遞歸性質(zhì)的命題，或簡稱遞歸命題．實際上，所謂遞歸命題，就是一個與自然數(shù)相關(guān)的命題T(n)，開頭(如n=0時)為真，且真值可傳遞并不是所有與自然數(shù)相關(guān)的命題都是遞歸命題．例如本節(jié)例3中的命題是與自然數(shù)相關(guān)的命題，而且對任何n∈N，它都為真，但卻不具有遞歸性，它的真值是不可傳遞的．一般而言，大多數(shù)數(shù)論問題，如哥德巴赫猜測、費馬問題、孿生素數(shù)問題等，都不是遞歸命題．只有遞歸命題才能用數(shù)學歸納法來證明．因此判別一個與自然數(shù)相關(guān)的命題T(n)是不是遞歸命題，是運用數(shù)學歸納法的前提．判別的關(guān)鍵在于，探究和發(fā)現(xiàn)T(n)的真值對于T(0)，…，T(n-1)真值的依賴性．而這種探究本身對于數(shù)學歸納法第二步證明，也有直接幫助．例6(1963年北京市競賽題)2n(n∈N＋)個球分成假設(shè)干堆，從中任選兩堆：甲堆p個球，乙堆q個球；假設(shè)p≥q，那么從甲堆取出q個加于乙堆；這作為一次挪動(變換)．證明：總可以經(jīng)過有限次挪動，使所有球都歸為一堆．這是一個與自然數(shù)相關(guān)的命題，記為T(n)．當n=1時，只有兩個球，或已是一堆；或兩堆，每堆一個球．假設(shè)后者，只須挪動一次，就變?yōu)橐欢眩訲(1)為真．T(n)真值是否有傳遞性呢？考察2n+1與2n，前