33数学归纳法与递回数列

《33数学归纳法与递回数列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§3-3數學歸納法與遞迴數列(甲)數學歸納法(1)歸納法：研究一個科學問題時，歸納法是很常用的方法，而歸納法常常從觀察開始。一個生物學家會觀察鳥類、昆蟲的生活，一個晶體學家會觀察晶體的形狀，當然一個對數論感興趣的數學家會觀察整數的一些性質。從幾個例子說起：例子：對於每個自然數n，13+23+33+…+n3=(1+2+…n)2成立嗎？例子：對於每個自然數n，n2-n+41都是質數？例子：任何一個既不是質數也不是質數平方的偶數，是二個奇質數的和嗎？從這幾個例子，可知經由觀察歸納得到的結果，只是一種猜想，不一定是對的，可是觀察歸納是自然科學中一個重要的手段，因為這

2、是許多偉大發明的起步。另一方面，即使每一個自然數代入檢查都正確，我們也還不能說這個命題對於所有的自然數都成立，因為我們不可能將自然數逐一檢查。於是，接下來我們介紹一種方法¾數學歸納法，可以證明某些性質，對於所有自然數都成立，雖然我們沒有一個一個去檢查。(2)數學歸納法：根據文獻記載，最早使用數學歸納法的作品是十六世紀的數學家F.Maurolico(1494~1575)。在ArithmeticorumLibriDuo一書中，他首先用數學歸納法來證明下面的例子猜測的結果是正確的。例子：1+3+5+…+(2n-1)=？根據觀察n=1，n=2，n=3的結果，我們可能

3、猜測答案是n2。但由前面的說明可知在沒有妥善的求證之前，不可遽下定論。而F.Maurolico的方法如下：設Sn表示前n個奇數的和，則S1=12，S2=22，S3=32，….假設Sk=k2成立，則Sk+1=1+3+5+…+(2k-1)+(2k+1)=Sk+(2k+1)=k2+2k+1=(k+1)2~3-3-12~因此，由S1可推得S2，再由S2可推得S3，仿此過程我們就可以逐次推得對任何一個正整數n恆有Sn=n2。上面所引用的程序去證明一個推測的結果的方法就稱為數學歸納法。(3)數學歸納法的形式：若要用數學歸納法證明「一個與自然數有關的命題P(n)」是真的，

4、有下列的形式：第一步驟：證明P(1)是真的。第二步驟：假設P(k)是真的，去證明P(k+1)是真的。注意：(a)有時候不一定從n=1開始，如果P(n)是n³m才會是真的，這時候將第一步驟改為證明P(m)是真的。(b)不管用哪一個數學歸納法的形式，每一個步驟都缺一不可，我們用兩個例子來說明。例子：證明「對於所有非負的整數n，n=n+1998」的過程：假設n=k時上述成立，即k=k+1998。當n=k+1時，n=k+1=(k+1996)+1=(k+1)+1996=n+1996。請問這個證明是否完成了數學歸納法的步驟，問題出在哪裡例子：證明：「對於每一個自然數n，

5、Fn=均為質數？」的過程中，當n=1,2,3,4時，Fn=均為質數，但n=5時，F5不為質數。[例題1]設nÎN(1)利用歸納法求(1+)(1+)(1+)…(1+)=？(2)利用數學歸納法證明(1)的結果。Ans：(1)n2~3-3-12~[例題1](1)請歸納13+23+…+n3的結果。(2)用數學歸納法證明你的結果。[例題2]試證：不論n是任何的正整數，10n+3×4n+5都可被9整除。[例題3]試證：£2-~3-3-12~[例題1]證明：對於任意大於3的自然數n而言，2n³n2恆成立。(練習1)試證明：任何n個人都一樣高。(1°)當n=1時，命題變為”

6、任何一個人都一樣高”此結論顯然成立。(2°)若設n=k時，結論成立，即”任何k個人都一樣高”則當n=k+1時，將k+1個人記為A1、A2、…、Ak+1，由歸納假設，A1、A2、…、Ak都一樣高，而A2、A2、…、Ak也都一樣高，故A1、A2、…、Ak+1都一樣高。由(1°)(2°)根據數學歸納法原理，任何n個人都一樣高。這個例子顯然有誤，但問題出在那裡呢？(練習2)試證明：1×22+2×32+3×42+…+n×(n+1)2=n(n+1)(n+2)(3n+5)(練習3)設nÎN，n³2(1)求(1-)(1-)(1-)…(1-)=？Ans：(2)利用數學歸納法證

7、明(1)的結果。(練習4)根據例題4證明：+++…+£-。(練習5)當n為自然數時，證明：1+2+3+…+(n-1)+n+(n-1)+…+3+2+1=n2。(練習6)試證明：不論n是任何的正整數，102n+5×12n-6都可被22整除。(練習7)試證對於自然數n，其中n>2，試證5n>2n+3n。~3-3-12~(乙)遞迴數列(1)遞迴數列：某些與自然數有關的問題，往往隱含固定的規律，處理這一類的問題通常分成三個步驟：(a)依據題設條件構造一個數列{an}。(b)建立相鄰幾項之間的遞迴關係式(亦稱遞迴方程式)。(c)解遞迴方程，求出一般項an。以上這種處理問

8、題的方法稱為遞迴方法。簡而言之，遞迴方法就是一種構造