數學歸納法

數學歸納法 是一種證明與自然數相關的定理的方法，它與良序原理等價，且被列入如 Peano公理等一些和自然數相關的公理當中 .
請參閱 Wiki 的定義 , Mathematical induction

Well ordering principle : 所有集合也是良序集。換句話說，對每一個集合來說，都存在一種排序方法，使得它的所有子集也有極小元素或是最小元素。

數學歸納法,基本上有兩個步驟;首先,先做歸納基礎(Basis)的證明,此步驟必須成立.接著再證明歸納步驟(Inductive Steps)成立,即可以斷論整個命題是成立的.
通常用於數學歸納法,都是先以觀察的方式,假設其命題是成立的,然後藉由歸納法證明是成立的.

Ex. 對於每個自然數n，1³+2³+3³+…+n³= (1+2+…n)²成立嗎？

首先,我們假設有一個命題P(n) , P(n) 是針對每個自然數 n , 1³+2³+3³+…+n³=(1+2+…n)²是成立的 .
分析一下上面的命題,
若 n = 1 , P(1) : 1³= (1)²是成立的
若 n = 2 , P(2) : 1³+2³= (1+2)²也是成立的
... 那我們假設針對任何和自然數n ,其命題P(n)皆成立.

歸納基礎:
n = 1 ,   P(1) : 1³= (1)²是成立的.

歸納步驟:
假設 n = k , k > 1 , P(k) 是成立的, 即 1³+2³+3³+…+k³= (1+2+…+k)²
證明當 n = k +1 , P(k+1) 是否也成立 ; 如是 , 則P(n) 也成立 , 針對 n , n 為自然數. 如下就證明當 n = k+1 時, P(k+1) 成立.

因為 , P(k) 成立 ,即 1³+2³+3³+…+k³= (1+2+…+k)^{2 ,}

當 n = k +1 , 則 1³+2³+3³+…+k³+ (k+1)³= (1+2+…+k)²+ (k+1)³
^因為1+2+…+k = [(1+k)k]/2 , 所以 (1+2+…+k)²= ([(1+k)k]/2)²
故 1³+2³+3³+…+k³+ (k+1)³= ([(1+k)k]/2)²+ (k+1)³= [(k+1)²(k+2)²]/4 = (1+2+…+k +(k+1) )²
對於每個自然數 n，1³+2³+3³+…+n³= (1+2+…n)²成立 , 故得證.

Ex. 對於每個自然數n，n²- n + 41都是質數

分析歸納如下:

n = 1 , 1-1+41 = 41 是質數
n = 2 , 4-2+41 = 43 是質數
n = 3 , 9-3+41 = 47 也是質數
n = 4 , 16-4+41 = 53 是質數
...
但 n = 41 , 41²- 41 + 41 不是質數 ( 因為是 41²)

Ex. 任何一個既不是質數也不是質數平方的偶數，是二個奇質數的和嗎？
假設命題 P為不是質數也不是質數平方的偶數,命題 Q是其偶數為二個奇質數的和.
偶數的性質如下,
n = 2k , k為自然數 , 若 P 命題要成立, 即 P(n) : n = 2k , k ≥ 2 , k ∈ N .
Q 命題, Q(n) : n = p1 + p2 ; p1, p2 是奇質數.

n = 4 , 4 = 1+3 = 2+2 , 4 是唯一的偶質數的平方. 故非basis
n = 6 , 6 = 3+3
n = 8 , 8 = 3 + 5
n =10 , 10 = 3 + 7
n = 12 , 12 = 5 + 7
n = 14 , 14 = 7+ 7
n = 16 , 16 = 11+ 5
n = 18 , 18 = 7 + 11
n = 20 , 20 = 3 + 17 = 13 + 7

... 類推

所以命題應該由 n ≥ 3 ,  P(n) : n = 2k , then n = p1 + p2 ; p1, p2 是奇質數 , k ∈ N and k ≥ 3

okay. Let's prove it .

歸納基礎:
k = 3 , n = 6 , then n = 3 + 3 為真

歸納步驟 :

假設 k > 3 , n = 2k , n = p1 + p2 ; p1 , p2 是質數, 且 p1p2 非偶數.

現在考量 k + 1 的情況, n = 2(k+1) = 2k + 2 ; 由歸納假設得知, 2k 是兩個奇質數之合, p1 及 p2 .因為任何大於3質數皆可以寫成 6k-1 或是 6k+5 的形式 ,故 n = 6k-1+6k+5 +2 = 12k +4 +2 = 12k +6 = 2(6k+3) 為偶數. 故其可以表示為認兩個質數 pi , pj 的和, when k > 3 , k ∈ N .  得證

質數與偶數性質

Ｅx. 1+3+5+…+(2n-1) =？ , n = 12,3,4, ... n ∈ N

Analysis above expression as below :

n = 1 , 1

n = 2 , 1+3 = 4

n = 3 , 1+3+5 = 9

n = 4 , 1+3+5+7 = 16

...

It seems that the sum is a perfect square , from 1,2,3, ...

Therefore , assume the above proposition P(n) : 1+3+5+…+(2n-1) = n², n ∈ N

Prove it via mathematics induction as below

Basis :

n = 1 , 1 = 1²

Induction Steps :

Assume n = k , k > 1 , P(n) is true .

Consider n = k +1 , 1+3+5+... + (2(k+1) -1) = 1+3+5+ ... + (2k + 1) = 1+3+5+...+ (2k-1) + (2k+1) = (k+1)²得證

Ex. 證明「對於所有非負的整數n，n=n+1998」的過程：

假設n = k 時上述成立，即k=k+1998。
當n = k+1時，n = k+1 = (k+1996)+1 = (k+1)+1996 = n+1996。
請問這個證明是否完成了數學歸納法的步驟，問題出在哪裡

問題發生在本身命題就是錯誤的.

n = 1 , Fn = 4 + 1 = 5 為真

n = 2 , Fn = 2⁴+ 1 = 17 為真

n = 3 , Fn = 2⁸+ 1 = 257　為真

n = 4 , Fn = 2¹⁶+ 1 = 65537　為真
n = 5 , Fn = 2³²+ 1 = 4294967297 非質數
所以命題是錯誤的

n = 1 , ( 1 + 3/1) = 4

n = 2 , ( 1 + 3/1)(1+5/4) = 9

n = 3 , ( 1 + 3/1)(1+5/4)(1+7/9) = 9 × 16/9 = 16

n = 4 , ( 1 + 3/1)(1+5/4)(1+7/9)(1+9/16) = 16 × 25/16 = 25

... and so forth.

Assume that there exist a proposition P(n) , P(n) : (1+3/1)(1+5/4)(1+7/9) ... (1 + (2n+1)/n²) = (n+1)²,∀n ∈ N

Induction on n

Basis :
n = 1 , P(n) : (1+3/1) = 4 = (1+1)²
Inductive Steps :

Assume that n = k , k > 1 P(k) is true ; that is , (1+3/1)(1+5/4)(1+7/9) ... (1+(2k+1)/k²) = (1+k)²

Consider n = k + 1 case .
When n = k + 1, (1+3/1)(1+5/4)(1+7/9) ... (1+(2k+1)/k²)(1+(2k+3)/(k+1)²) = (1+k)²×(1+(2k+3)/(k+1)²) = (2+k)²Q.E.D.

n = 1 , 1³= 1
n = 2 , 1³+ 2³= 1 + 8 = 9
^{^{n = 3 , 9 + 27 = 36}}
n = 4 , 36 + 64 = 100
n = 5 , 100 + 125 = 225
....

9 = 3²= (1+2)²
36 = 4²= (1+2+3)²
100 = 10²= (1+2+3+4)²
^...
^{Assume that there exists a proposition P , P(n) :}∀n ∈ N , 1³+ 2³+ 3³+ ... + n³= (1+2+3+ ...+n)²
^{Induction on n ,}
^{Basis :}

n =1 , 1³= 1²

Inductive Steps :

Assume n = k , k > 1 ; P(n) is true .

Consider n = k + 1 , 1³+ 2³+ 3³+ ... + k³+ (k+1)³= (1+2+3+ ...+k)²+(k+1)³=(1/4)(k(k+1))²+ (k+1)³= [(k+1)(k+2)]²/4 得證

Assume that there exists a proposition P , P(n) : ∀n ∈ N ,9 | 10ⁿ+ 3· 4ⁿ+5

Induction on n

Basis :
n = 1 , P(1) is true ; that is , 9 | 10 + 12 + 5

Inductive Steps :
Assume that n = k and k > 1 , P(k) is true ; that is , 10^k+ 3· 4^k+5 = 9 m , m is positive integer.

Consider n = k +1 case
10^k+1+ 3· 4^k+1+5 = 10·10^k+ 12· 4^k+ 5 = 10^k+ 3· 4^k+ 5 + 9·10^k+ 9· 4^k= 9 ( m + 10^k+ 4^k) , Therefore , 9 | 10^k+1+ 3· 4^k+1+5
根據數學歸納法 , 得知　∀n ∈ N ,9 | 10ⁿ+ 3· 4ⁿ+5

證:

令 P(n) 是一個命題 , P(n) : ∀n ∈ N , 1/1²+ 1/2²+ 1/3²+ ... + 1/n²≤ 2 - 1/n

歸納基礎 :
n = 1 , 1/1²≤ 2 - 1/1 ; P(1) 成立.

歸納步驟 :
假設 n = k , P(k) 成立, 即 1/1²+ 1/2²+ 1/3²+ ... + 1/k²≤ 2 - 1/k

考慮 n = k+1 , 1/1²+ 1/2²+ 1/3²+ ... + 1/k²+ 1/(k+1)²≤ 2 - ( 1/k - 1/(k+1)²)

1/k - 1/(k+1)²= (k²+k+1) / k(k+1)²; 令 A = k²+k+1 , 則1/k - 1/(k+1)²=^{Ａ/ k(A+k)}

因為 k > 0 , 則Ａ> 0 and Ａ/A+k > 1/(k+1) ,when k > 1 ; 故 2 - ( 1/k - 1/(k+1)²) ≤ 2 - A / k(A+k) ≤ 2 - 1/k(k+1) ≤ 2 - 1/k+1 得證

證明：對於任意大於3的自然數n而言，2ⁿ³ n²恆成立

Assume that there exists a proposition P , P(n) : ∀n ∈ N and n > 3, 2ⁿ³ n²
Induction on n

Basis :
n = 4 , 2⁴³ 4²
Inductive Steps :
Assume n = k , k > 4 , P(k) is true ; that is , 2^k³ k²
^{Consider n = k + 1 ,}
2^k+1= 2 · 2^k³ 2 · k²= k² + k²³ k²+ 2k + 1 ( ∵ 1/k-2 > 1/k ) Q.E.D.

試證明：任何n個人都一樣高。
(1^°)　當n=1時，命題變為”任何一個人都一樣高”此結論顯然成立。
(2^°)　若設n=k時，結論成立，即”任何k個人都一樣高” , 則當n=k+1時，將k+1個人記為
A₁、A₂、…、A_k₊₁，由歸納假設 A₁、A₂、…、A_k都一樣高，而A₂、A₂、…、A_k
也都一樣高，故A₁、A₂、…、A_k₊₁都一樣高。
由(1^°)(2^°)根據數學歸納法原理，任何n個人都一樣高。

這個證明是正確的嗎 ?

( 試證明：1×2²+2×3²+3×4²+…+n×(n+1)²= [n(n+1)(n+2)(3n+5)]/12

使用數學歸納法證明 :
假設 P(n) 是一個命題, P(n) : ∀n ∈ N , 1×2²+2×3²+3×4²+…+n×(n+1)²= n(n+1)(n+2)(3n+5)

歸納基礎:
n = 1 , P(1) 成立 ;1×2²= 1× (1+1) (1+2)(3+5) /12 = 2×3×8/12

歸納步驟:
假設 n = k , k > 1 , P(k) 成立
考慮 n = k + 1 , 1×2²+2×3²+3×4²+…+ (k+1)×(k+2)²= k(k+1)(k+2)(3k+5)/12 + (k+1)×(k+2)² = (k+1)(k+2) [ k(3k+5)/12 + (k+2) ] = (k+1)(k+2) [ 3k²+ 17k + 24 ] / 12 = (k+1)(k+2)(k+3)(3k+8) / 12 故得證.

Ex.

Ex. 設nÎN，n³2 , 求 (1-1/4)(1-1/9)(1-1/16) ...(1-1/n²)

展開上式如下:
(3/4)×(8/9)×(15/16)×(24/25)× ... ×[(n-1)(n-3)/(n-2)²]×[n(n-2)/(n-1)²]×[(n-1)(n+1)/n²] = (n+1)/2n

數學歸納法證之
假設有一個命題 P(n) , P(n) : 設nÎN，n³2 , (1-1/4)(1-1/9)(1-1/16) ...(1-1/n²) = (n+1)/2n

歸納基礎 :
n = 2 , (1-1/4) = 3/4

歸納步驟 :

假設 n = k , k > 2 ; P(k) 成立 , 即 (1-1/4)(1-1/9)(1-1/16) ...(1-1/k²) = (k+1)/2k
考量 n = k +1 , (1-1/4)(1-1/9)(1-1/16) ...(1-1/k²)( 1- 1/(k+1)²) = [(k+1)/2k ][ (k+1)²-1 / (k+1)²] = (k + 2)/2(k+1) 故得証

假設有一個命題 P(n) , P(n) : nÎN , 1/1²+ 1/3²+ 1/5²+ ... + 1/(2n+1)²≤ 3/2 - 1/4n
歸納基礎 :
n = 1 , 1/1²≤ 3/2 - 1/4

歸納步驟 :
假設 n = k , k > 1 , 即P(k) 成立

考慮 n = k +1 時
1/1²+ 1/3²+ 1/5²+ ... + 1/(2k+1)²+ 1/(2k+3)²≤ 3/2 - 1/4k + 1/(2k+3)²由歸納假設
如何求得 3/2 - 1/4(k+1) 與 3/2 - 1/4k + 1/(2k+3)²之間的關係 ?
Ex.當n為自然數時，證明：1+2+3+…+(n-1)+n+(n-1)+…+3+2+1 = n²
其實這個題目很直覺的可以看出來,用一般的方法解之.
令 Sn = 1+2+3+…+(n-1)+n+(n-1)+…+3+2+1 , 而S'n = 1+2+3+…+(n-1) ; 所以 Sn = n + 2S'n , 因為 S'n = 1+2+3+…+(n-1) ,2S'n = [1+(n-1)]+[2+(n-2)]+[3+(n-3)]+…+[(n-1)+1] = n(n-1) , therefore, Sn = n + n(n-1) = n^{2 得證}

證明：不論n是任何的正整數，10²ⁿ+5×12ⁿ-6都可被22整除

To prove the fact via using mathematics induction

Induction Basis :
n = 1 , 10²+5×12¹-6 = 100 + 60 - 6 = 154 , 22 | 154

Induction Steps :
Assume that n = k and k > 1 , 22 | 10^2k+5×12^k-6
Consider n = k +1 case
10^2k+2+ 5×12^k+1- 6 = 100 ×10^2k+ (5×12)×12^k- 6 = ( 10^2k+ 5×12^k- 6 ) + 99×10^2k+ 55×12^k

55×12^k= 11×5×(2×6)^k= 22×5×2^k-1×6^k
99×10^2k= 11×9×(2×5)^k= 22×9×2^k-1×5^k

所以 22 | 10^2k+2+ 5×12^k+1- 6 , n = k+1
因此22 | 10²ⁿ+5×12ⁿ-6 , nÎN 故得證

對於自然數n，其中n>2，試證5ⁿ>2ⁿ+3ⁿ

歸納基礎 :

n = 2 , 5²> 2²+ 3²

歸納步驟 :

假設 n = k 且 k >2 , 5^k> 2^k+ 3^k

考慮 n = k +1 時,
5^k+1= 5×5^k> 5×(2^k+ 3^k) > 2^k+1+ 3^k+1 ^得証

5ⁿ> 2ⁿ+ 3ⁿ , ∀n > 2

遞迴數列

某些與自然數有關的問題，往往隱含固定的規律，處理這一類的問題通常分成三個步驟：
(1)依據題設條件構造一個遞迴數列{an}。
(2)建立相鄰幾項之間的遞迴關係式(亦稱遞迴方程式)。
(3)解遞迴方程，求出一般項an。(不一定每個遞迴關係式都能夠求出一般項)

此種處理問題的方法叫做遞迴方法。簡而言之，遞迴方法就是一種構造遞推式的解題法。
至於如何求解遞迴數列？較簡單的，可用「觀察→歸納→猜想→證明」的模式去處理

Wiki's recursive method definition :

In mathematics and computer science, a class of objects or methods exhibit recursive behavior when they can be defined by two properties:

A simple base case (or cases)
A set of rules that reduce all other cases toward the base case

More information about it , please visit Recursion .

Ex.相傳在創世紀時代，河內(Hanoi)的一座寺廟中豎立著三根銀棒，有64個大小都不同的金盤(金盤正中央有一個小孔)「大盤在下，小盤在上」依序套在同一根銀棒上。造物主命僧侶把64個金盤全部移到另外一根銀棒上，並且規定：每一次只能移動一個金盤，在移動過程中，較大的金盤不可套在較小的金盤上。當金盤全數搬完，世界末日將降臨，忠誠者得到好報，不忠者受到懲罰。試問搬完64個金盤最少需多少次？

按照規則,以3個disks為例其移動的是意圖如下:

3 個碟子移動情形

其行為分析為 :

D1 ---> Tc

D2 ---> Tb

D1 ---> Tb ------ D1 , D2 in Tb

D3 ---> Tc

D1 ---> Ta

D2 ---> Tc ------ D2 , D3 in Tc

D1 ---> Tc

做的步驟有兩個 process 處理相同的動作,即將第1個disk 至第n-1個disk 由A柱搬移到B柱 (此動作是為了將最底的Disk 3 可以移到 C柱)及由B柱搬移到C柱 (最後將Disk1,Disk 2 移到柱 C) . 完成全部的process 則為 7 次移動 ,其中有6 次移動是一樣的,加上最後一次最小disk的移動 . 真是這樣的 ?

看下面 4 disks 的移動情形 :

其行為分析為:

D1---> Tb

D2---> Tc

D1---> Tc ---- D1 , D2 in Tc

D3---> Tb

D1---> Ta

D2---> Tb

D1---> Tb ---- D1,D2,D3 in Tb

接著再將 D2,D3,D4 移至 Tc ,動作如下:

D4--->Tc
D1--->Tc
D2--->Ta
D1--->Ta
D3--->Tc ---- D3,D4 in Tc
D1--->Tb
D2--->Tc ---- D2,D3,D4 in Tc

所以行為與3 disks 一樣, 如此觀察出來搬移次數為 2ⁿ-1 . 真的是這樣嗎 ?
如上討論出一個現象;假設disk的數量為n , 必然有⌊n/2⌋次的搬移是為移動剩下(n-1)個disks (無論是由小到大或是由大到小). 所以我們可以根據其移動的行為給定一個遞迴定義:
假設H(n) 為n個disks總移動次數,其為2個H(n-1)移動的次數和加上最後一次移動(最小的disk移動),所以可以寫出如下的定義:

H(n) = 2H(n-1) + 1 , H(1) = 1 (若只有一個disk就只有移動1次)

接著證明其是否為2ⁿ-1 移動次數 ?
H(1) = 1
H(2) = 2H(1) + 1 = 2 +1 = 3
H(3) = 2H(2) + 1 = 6 +1 = 7
H(4) = 2H(3) + 1 = 14 + 1 = 15
...
H(4) = 2H(3)+ 1 = 2(2H(2)+1) + 1 = 2(2(2H(1)+1)+1)+1 = 2³H(1) + 2²+ 2 + 1 = 2³+ 2²+ 2 + 1 = 2⁴- 1 .
所以我們可以給定一個遞迴定義:

H(n) = 2H(n-1) + 1 , n > 1
H(1) = 1

Ex.兔子問題
假定養兔場中一開始有一對成年的兔子，一個月後生了一對小兔子，而這對小兔子經過一個月就長大成大兔子，此後每對大兔子每月生一對小兔子，而每對小兔子經過一個月就長成大兔子，如果不發生死亡，請問第n個月，養兔場中有多少對兔子？

分析此問題如下:
第一個月: 小兔 1 , 成兔 0 , 兔子總數 1
第二個月: 小兔 0 , 成兔 1  , 兔子總數 1 (小兔長成成兔,但未生)

第三個月: 小兔 1 , 成兔 1  , 兔子總數 2 (多了小兔,故成兔加小兔為2)

第四個月: 小兔 1 , 成兔 2 , 兔子總數 3

第五個月: 小兔 2 , 成兔 3 , 兔子總數 5

.... 類推

如列表計算兔子數:

第n個月	1	2	3	4	5	6	7	8	……
兔子數a_n	1	1	2	3	5	8	13	21

觀察發現, 由第3個月開始,其兔子總數為前兩個月兔子總數之和.可以列出一個數列如下:
1,1,2,3,5,8,13,21,34,55, ...
歸納結果 , 若第n個月,其兔子總數假設為an , an = an-1 + an-2 , n >2 ,此為著名的 Fibonacci sequence (費式數列)
維基 Fibonacci_number

Ex. 設DABC是邊長為1的正三角形。將三邊分別三等份，取中間段為一邊向外側作一個正三角形，並且將中間這一段擦去，其次將剩下的每一邊再三等份，取中間段為一邊向外作正三角形，再將中間這一段擦去。依此程序繼續下去，得到一系列的圖形，這種自我複製的圖形，稱為碎形。試求(a)第6次之碎形的周長。(b)第n次的周長 , 那請問第n次的總面積為 ?

由左到右,由上到下,分別為 n = 0 , n =1
n = 2 , n = 3 的圖形增生的圖形 , n為增生的次數

分析如下:

假設 n 為碎形增生的次數.
n = 0 , 即無任何碎形增生, 總周長為 3
n = 1 , 每一邊都均分三等份,並以中間段為邊長在增生一個正三角形;故
每個邊都增生2個正三角形的邊長,其邊長為原邊長的1/3.
故此時的總邊長 = (1/3 + 1/3 + 2/3) × 3 = 4 (共有12個邊)
n = 2 , 多出來的3個三角形的2個邊都均分三等份,並以中間段為邊長在增生一個正三角形;故每個三角形每個邊貢獻2個邊為 6× 2× 2 = 24 再加上每個三角形每兩個邊皆有2個邊,故 2 × 2 × 6 = 24 ,故總邊數為 24+ 24 = 48 個
而邊長為前一次增生的邊長的1/3 ,故為1/9 則邊長為 48/9
但是這樣我要如何歸納其現象呢?
起始的情況為:
n = 0 , 圖形的邊總數為 3 , 邊長為 1 (令 a0 = 1 , s0 = 3 , T0 = 1)
n = 1 , 每個邊都會多出一個三角形而每個三角形都會少一個邊,而原來的三角形的每個邊會分裂出兩個邊. 故每邊的邊總數為 2 + 2 (多一三角形貢獻兩邊,底邊也分裂兩個邊)
可以將每次分裂的邊拉成一直線,即有4個等長的線段令其為 an , n > 0 , 故
假設第n次邊長為 an , 第n+1次分裂的圖形的邊長為an+1 , 則an+1 = an - an/3 + 2an/3 = 4/3an .

那第6次分裂後的總周長為何 ?
首先,求第6次的每一邊的邊長 a6 = 4/3 a5 , a5 = 4/3 a4 , a4 = 4/3 a3, a3 = 4/3 a2 , a2 = 4/3 a1 . 則 a6 = (4/3)⁵總邊長為 4⁵/3⁴

面積為多少 ? 請參考 fractal

Ex. 平面上n條直線，任兩條都不互相平行，而且任三條都不共點，試問這n條直線把平面分割成多少個互不重疊的區域

假設有An為n 條線分割後的區域, 分析歸納如下:
n = 1 , A1 = 2
n = 2 , A2 = 4 = 2 + 2
n = 3 , A3 = 7 = 4 + 3
n = 4 , A4 = 11 = 7 + 4
.... 類推
觀察一個現象, 當直線的數目大於1時,其分割平面的數目為前一次分割後的區域數+目前的直線數. 故歸納一個遞迴定義 :
An+1 = An + (n+1) , n = 1,2,3,4,5, ...

起始

給定數列{a_n}：1,3,6,10,15,21,…，找出a_n前後項之間的關係

a1 = 1
a2 = 3 = a1 + 2
a3 = 6 = a2 + 3
a4 = 10 = a3 + 4
...
可以分析出第n項為 an+1 = an + (n+1) , n = 1,2,3,4, ...

求遞迴數列a_n的一般式

(a) a_n+₁= a_n+f(n) Þ 遞迴相加求a_n
(b) a_n+₁= f(n)´a_n Þ 遞迴相乘求a_n
_{n = 0 ,}a₁= a₀+ f(0)
_{n = 1 ,}a₂= a₁+ f(1)
_{n = 2 ,}a₃= a₂+ f(2)
...
_{n = k-1 ,}a_k-1= a_k-2+ f(k-1)
_{n = k ,}a_k= a_k-1+ f(k)

Therefore , a_k= a₀+ f(0) + f(1) + f(2) + ... f(k)

a_n₊₁= aa_n+ k Þ 設計b , 使得 a_n+₁- b =a´(a_n-b )

Since a_n₊₁= aa_n+ k , this is a recursive definition.
a_n₊₁= aa_n+ k
aa_n= a²a_n-1+ ak
a²_n-1= a³a_n-2+ a²k
a³a_n-2= a⁴a_n-3+ a³k
...
a^n-1a₂= aⁿa₁+ a^n-1k
aⁿa₁= aⁿ⁺¹a₀+ aⁿk

a_n₊₁= aⁿ⁺¹a₀+ k + ak + a²k + ... + aⁿk = aⁿ⁺¹a₀+ k(1+ a + a² + ... + aⁿ) = aⁿ⁺¹a₀+ k (aⁿ⁺¹- 1) / a -1 this is its general form.

a_n+₁- b = a´(a_n-b ) , then a_n+₁- b = aa_n-ab , a_n+₁= aa_n- (1-a)b

- (1-a)b = k , b = k/(a-1)

Ex. 設a₁= 1，且a_n+₁= a_n+ 3n²，求a_n=？

a_n+₁= a_n+ 3n²
a_n= a_n-1+ 3(n-1)²

a_n-1= a_n-2+ 3(n-2)²

a_n-2= a_n-3+ 3(n-3)²

...
a₂= a₁+ 3(1)²

a_n+₁= 3n²+ 3(n-1)² + 3(n-2)²+ 3(n-3)²+ ... + 3(2)² + 3(1)²+ 1 = 3 [ n² + (n-1)²+ ... + 2²+ 1²] + 1 , therefore a_n= 3[ (n-1)²+ ... + 2²+ 1²] + 1 = 3[(n-1)n(2n-1)/6] + 1 = (n-1)n(2n-1)/2 + 1

....

一數列<a_n>定義如下：a₁=3，a_n₊₁=5a_n+4，n為自然數，試求a_n的一般項，並用數學歸納法加以證明

a_n₊₁= 5a_n+4
5a_n= 5²a_n-1+ 4´5
5²a_n-1= 5³a_n-2+ 4´5²

5³a_n-2= 5⁴a_n-3+ 4´5³
^...

5^n-1a₂= 5ⁿa₁+ 4´5^n-1

5a_n= 4´5 + 4´5²+ ... + 4´5^n-1+ 3´5ⁿ
a_{n =}4 + 4´5+ ... + 4´5^n-2+ 3´5^n-1= 4(1+5 + ... + 5^n-2+ 5^n-1) - 5^n-1= 5ⁿ- 1 - 5^n-1= 4´5^n-1- 1

使用數學歸納法證之

歸納基礎:
n = 1 , a₁ = 4´5^1-1- 1

歸納步驟:
假設 n = k , k > 1 ; a_k=4´5^k-1- 1
考慮 n = k +1 時 ,
a_k₊₁= 5a_k+4 = 5´(4´5^k-1- 1) + 4 = 4´5^k - 5 + 4 = 4´5^k - 1 故得證.

(1)有一階差數列1,5,12,22,35,51,…，
設a₁=1，a₂=5，a₃=12，a₄=22，a₅=35，a₆=51，
考慮a₂-a₁=4，a₃-a₂=7，a₄-a₃=10，a₅-a₄=13，a₅-a₆=16，請寫出這
個數列的遞迴關係。
(2)求出此階差數列的第30項。
(3)求出此階差數列的第n項。

Since a₂-a₁= 4 = 3 + 1
a₃-a₂= 7 = 3´2 + 1
a₄-a₃= 10 = 3´3 + 1
a₅-a₄= 13 = 3´4 + 1
a₅-a₆= 16 = 3´5 + 1
....
所以假設 a_n+1- a_{n = 3n +1 , n =12,3,4, ...}
將上式分成左右式 :

a₂-a₁= 4 = 3 + 1
a₃-a₂= 7 = 3´2 + 1
a₄-a₃= 10 = 3´3 + 1
a₅-a₄= 13 = 3´4 + 1
a₆-a₅= 16 = 3´5 + 1

...

a_n-a_n-1= 3´(n-1) + 1

Therefore , a_n- a₁= 4+7+10+13+16+19+ ... + [3´(n-1) + 1] 為一個等差數列,公差為 3 ; 即 a_n= S_n_,S_{n = n}_{[2 + 3(n-1)] / 2}

一機器狗每秒鐘前進或後退一步，程式設計師讓機器狗以前進3步，然後再後退2步的規律移動。如果將此機器狗放在數線的原點，面向正的方向，以1步的距離為1單位。令 P(n) 表示第n秒時機器狗所在位置的坐標，且P(0)=0 , 求P(n) .

令 P(n) 為第n秒的位置, 分析如下:

n = 0 , P(0) = 0

n =1 , P(1) = P(0) + 3-2

n =2 , P(2) = P(1) + 3-2
n =3 , P(3) = P(2) + 3-2
....
n = k , P(k) = P(k-1) + 3-2

n = k , P(k) = 1+1+1+ ...+ 1 ; k times .

觀察情況一 :

1 : 7 = 4*2 -1
2 : 5 = 4*2 - 1 - 2
3 : 3 = 4*2 - 1 - 2 - 2
4 : 1 = 4*2 - 1 - 2 - 2 - 2 stop

觀察如上圖形並分析其結果如下:
3´3 方格
由最下面一列所有方格中的數字總和並令其為
a_{1 = 1+1+1 = 3}

a_{2 = 1+2+2 = 5}
a_{3 = 1+2+3 = 6}
a₂-a_{1 = 5}-_{3 = 2}
a₃-a_{2 = 6}-_{5 = 1}

4´4 方格
由最下面一列所有方格中的數字總和並令其為

a_{1 = 1+1+1+1 = 4 (最終列)}

a_{2 = 1+2+2+2 = 7}
a_{3 = 1+2+3+3 = 9}

a_{4 = 1+2+3+4 = 10 (最上列)}

_{同樣地,由最左行為第1行,其元素和 b1 = 1+1+1+1 ,}b2 = 2+2+2 , ...

與列總和相同.

假設 n´n 方格共有n列 , 令最上列所有元素總和為 an , an+1 - an = n , n = 3,4,5, ...

Assume that there exists a n by n square , then sum of nth row is an = an-1 + (n-1) and a1 = n , n =3,4,5,6, ... therefore it is a 等差級數.

And a 5 by 5 square , how should we do it ?

1 1 1 1 1 (5)

1 2 2 2 2 (9)

1 2 3 3 3 (12)

1 2 3 4 4 (14)

1 2 3 4 5 (15)

可以觀察出一個規律現象, 假設有一個 n´n 方格 , 將其編號由最底一列開始,由左至右為A(1,1),A(1,2),A(1,3), ... , A(1,n),A(2,1),A(2,2), ..., A(n,n) 共 n´n 元素.

其元素值行列一樣的位置A(i,i) = i , i =1,2,3,4, ... ,n ;而其他元素的值為如下的規律:

A(i,j) = A(j,i) , i = 1,2,3, ..., n 且 j = 1,2,3, ..., n

針對每一個主對角線元素A(i,i) , 其 A(i,i+1) , A(i,i+2) , ... , A(i,n) 及 A(i+1,i),A(i+2,i), ..., A(n,i) 值與A(i,i) 相同. 所以, 其總和為:

i = 1, A(1,1) = 1 , ∑A(i,k) ; k = i+1 , ... , n-1 . ∑ A(k,i) , k = i+1 , ... , n .故其總和為 ∑ A(i,i) + 2∑j∑A(i,k) , i ≤ j ≤ n-i , 1 ≤ i ≤ n , i +1 ≤ k ≤ n-1

A(i,i) = i , i =1,2,3, ... , n 且A(i,j) = A(j,i) = i ; i , j = 1,2,3, ... , n-1 ;

故 10 ´ 10 方格元素為如下的排列 :
1 1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2 2
1 2 3 3 3 3 3 3 3 3
1 2 3 4 4 4 4 4 4 4
1 2 3 4 5 5 5 5 5 5
1 2 3 4 5 6 6 6 6 6
1 2 3 4 5 6 7 7 7 7
1 2 3 4 5 6 7 8 8 8
1 2 3 4 5 6 7 8 9 9
1 2 3 4 5 6 7 8 9 10

觀察現象如下:

1 1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2 2
1 2 3 3 3 3 3 3 3 3
1 2 3 4 4 4 4 4 4 4
1 2 3 4 5 5 5 5 5 5
1 2 3 4 5 6 6 6 6 6
1 2 3 4 5 6 7 7 7 7
1 2 3 4 5 6 7 8 8 8
1 2 3 4 5 6 7 8 9 9
1 2 3 4 5 6 7 8 9 10

假設ai = 顏色覆蓋區域之和, Si = ai + 每列灰色區域之和
ai = [(1+i)i]/2 , i = 1,2,3 , ... , n , 令 Ai = i(n-i) , i = 1,2,3,4 , ... , n

S = ∑ (ai + Ai) , i =1,2,3, ... , n

另一種觀察:

由主對角線的第一個元素A(1,1)開始,向右依續加總其同列元素,即∑ A(1,j+1) , j =1,2,3, ... , n ; 在向下加總其同行元素,即∑ A(i+1,1) , j =1,2,3, ... , n ;再加上 A(1,1) 故總和為 A(n,n) + A(1,1) + ∑ A(i+1,1) + ∑ A(1,j+1), i , j = 1,2,3,4, ..., n-1
如上例:
(2n-1)+(2n-3)´2+(2n-5)´3+ ... +3´(n-1)+n = Sn ,Sn 為數字總和 , n 為方格.

Sn = a1 + a2 + a3 + ... an-1 + an
a1 = (2n-1)
a2 = (2n-3)´2 = 4n - 6 , a2 - a1 = 2n -5 ,
a3 = (2n-5)´3 = 6n - 15 , a3 - a2 = 2n - 9 ,
a4 = (2n-7)´4 = 8n - 28 , a4 - a3 = 2n -13
...
To be continued ...

綜合練習

1) 試證：1²×2¹+ 2²×2²+ 3²×2³+…+ n²×2ⁿ= (n²-2n+3)×2ⁿ⁺¹- 6

令 P(n) 為一個命題, P(n): ∀n ∈ N , N 是自然數集合. 則 1²×2¹+ 2²×2²+ 3²×2³+…+ n²×2ⁿ= (n²-2n+3)×2ⁿ⁺¹- 6 成立.

歸納基礎 :

n =1 , 1²×2¹= (1²-2+3)×2²- 6

歸納步驟 :

假設 n = k , k > 1 則 1²×2¹+ 2²×2²+ 3²×2³+…+ k²×2^k= (k²- 2k + 3)×2^k+1- 6

考慮 n = k +1 時 ,

1²×2¹+ 2²×2²+ 3²×2³+…+ k²×2^k+ (k+1)²×2^k+1 = (k²- 2k + 3)×2^k+1- 6 + (k+1)²×2^k+1= [ (k²- 2k + 3) + (k+1)²]×2^k+1- 6 = [(k+1-1)² + 2 ]×2^k+2- 6 故得証.

歸納基礎 :
n = 1 , 1×2¹/ 2×3 = 4/3 - 1

歸納步驟 :
假設 n = k , k > 1 , 1×2¹/ 2×3 + 2×2²/ 3×4 + 3×2³/ 4×5 + ... + k×2^k/ (k+1)×(k+2) = 2^k+1/ (k+2) - 1
考慮 n = k + 1 時 ,
1×2¹/ 2×3 + 2×2²/ 3×4 + 3×2³/ 4×5 + ... + k×2^k/ (k+1)×(k+2) + (k+1)×2^k+1/ (k+2)×(k+3) = 2^k+1/ (k+2) - 1 + (k+1)×2^k+1/ (k+2)×(k+3) = 2^k+2/ (k+3) - 1 故得證

1/1*3+1/3*5 + 1/5*7 + 1/7*9 + ... + 1/(2n-1)*(2n+1) = (1-1/3)+(1/3 - 1/5)+(1/5-1/7)+ ... + (1/2n-1 - 1/2n+1) = 1 - 1/2n+1
Induction Basis :
n = 1 , 1/1*3 = 1- 1/3 = 1- 1/(2*1+1)
Induction Steps:
Assume that n = k , k > 1 , then 1/1*3+1/3*5 + 1/5*7 + 1/7*9 + ... + 1/(2k-1)*(2k+1) = 1 - 1/(2k+1)

Consider n = k +1 ,
1/1*3+1/3*5 + 1/5*7 + 1/7*9 + ... + 1/(2n-1)*(2n+1) = (1-1/3)+(1/3 - 1/5)+(1/5-1/7)+ ... + (1/2k-1 - 1/2k+1) + (1/2k+1 - 1/2k+3) = 1 - 1/(2k+3) Q.E.D.

4) Assume that there exists a proposition P(n) , and P(n) : For any positive number n , then 1+1/2+1/3+...+1/n ≥ 2n/n+1 .

Induction Basis :

n = 1, 1 ≥ 2/1+1

Induction Steps :
Assume that n = k , k > 1 ; 1+1/2+1/3+...+1/k ≥ 2k/k+1
Consider n = k +1 ,
1+1/2+1/3+...+1/k+1/(k+1) ≥ 2k/k+1 + 1/(k+1)
2k/(k+1) + 1/(k+1) = 2k +1 /(k+1)
Since k > 0, then (2k+1)(k+2)>2(k+1)^{2 故得証.}
^{5) Assume that there exists a proposition P(n) , P(n) : For all nature numbers , [123...(2n-1)]/[246 ...(2n) ]}< (2n-1)^-1/2
^{Induction Basis :}
^{n = 1 , 1/2 < 1}
^{Induction Steps :}
^{Assume n = k , k > 1}^{[123...(2k-1)]/[246 ...(2k) ] < 1 /}√(2k-1)
Consider n = k +1 , [123...(2k-1)]/[246 ...(2k) ] (2k+1)/2k+2 < (1/√2k+1 ) (2k+1)/(2k+2)

(1/√2k+1 ) (2k+1)/(2k+2) = √2k+1 /(2k+2) ,

√(2k+1)(2k+3) = √(2k+1)²+2(2k+1) = √(2k+1)²+2(2k+1)+1-1 = √(2k+2)²-1 < 2k+2

1 / √(2k+2)²-1 >2k+2 / √2k+1

1/ / √2k+3 >2k + 2 >√2k+1 /(2k+2) 故得證

6)
(a) 假設 k為n位的自然數, 令 k = anan-1an-2an-3...a2a1 , a1 = 6 ,
k 能夠被表示 10m + 6 , m 是自然數.

(b) 由題意 2⁴ⁿ⁺¹- 6ⁿ個位數是6 , 故 2⁴ⁿ⁺¹- 6ⁿ= 10m + 6

歸納法證明之:

假設 P(n) 是一個命題 , 對任何自然數 n , 2⁴ⁿ⁺¹- 6ⁿ= 10m + 6 ; 其中m 是自然數.

Induction Basis :

n = 1 , 32 - 6 = 20 + 6

Induction Steps :

Assume n = k , k > 1 ; P(k) is true . 2^4k+1- 6^k= 10m + 6 , m is nature number .

C Consider that n = k + 1 case ,

2^4k+5- 6^k+1= 16 (2^4k+1- 6^k) + 10(6^k) = 60m + 36 + 10p = 10(6m+p) + 30 + 6 = 10(6m+p+3) + 6 故得證

由題意, for any n , n is nature number , then 3²ⁿ⁺¹ + 2ⁿ⁺²= pk , p is a prime and k is a positive number , then find p .

n = 1 , 3²⁺¹ + 2¹⁺²= 17 *1 , therefore p = 17

n = 2 , 3⁴⁺¹ + 2²⁺²= 97 , but it is a prime , not the multiplies of 17

I think the question gets some troubles.

設a是固定的正數，觀察下列式子：

(1+a)¹=1+a，(1+a)²=1+2a+a²³1+2a，(1+a)³=1+3a+3a²+a³³1+3a ,

對於任意自然數n，不等式(1+a)ⁿ³1+na是否恆成立？

of Course . 歸納法證之.

9) 有一個數列 <a_n> 滿足 a₁=1，a_n₊₁= a_n+ 5(n-1) , it is a recursive sequence .

a₁=1，

a₂= a₁+ 5(2-1) = 1 + 5 = 6

a₃= a₂+ 5(3-1) = 6 + 12 = 18

a₄= a₃+ 5(4-1) = 18 + 15 = 33

...

a_n-1= a_n-2+ 5(n-1-1)

a_n= a_n-1+ 5(n-1)

a_n= 5(n-1) + 5(n-1-1) + 5(n-3) + ... + 5(3-1) + 5(2-1) + 1 = 5 [ (n-1) + (n-2) + (n-3) + ... + (3-1) + (2-1) ] + 1 = (5/2)[(n-1+1)(n-1)] = 5/2[ n(n-1) ] + 1

11) 當初有7個細胞, 依照提意, 每隔一小時死亡2個, 剩下的每個分別分裂成2個,如下的過程

13) 13) 設 a₁= 1，a_n= (1-1/n²)a_n_{-1 ,}n ≥ 2

規

參考:
數學歸納法專輯說明 - 林倉億
數學歸納法的證明 - 呂文寶

資料收集

Other blogs

Thursday, December 12, 2013

3-3 數學歸納法與遞迴數列

( 試證明：1×2²+2×3²+3×4²+…+n×(n+1)²= [n(n+1)(n+2)(3n+5)]/12

1) 試證：1²×2¹+ 2²×2²+ 3²×2³+…+ n²×2ⁿ= (n²-2n+3)×2ⁿ⁺¹- 6

令 P(n) 為一個命題, P(n): ∀n ∈ N , N 是自然數集合. 則 1²×2¹+ 2²×2²+ 3²×2³+…+ n²×2ⁿ= (n²-2n+3)×2ⁿ⁺¹- 6 成立.

歸納基礎 :

No comments:

Post a Comment

Other blogs

Thursday, December 12, 2013

3-3 數學歸納法與遞迴數列

( 試證明：1×22+2×32+3×42+…+n×(n+1)2 = [n(n+1)(n+2)(3n+5)]/12

1) 試證：12×21 + 22×22 + 32×23 +…+ n2×2n = (n2-2n+3)×2n+1 - 6

令 P(n) 為一個命題, P(n): ∀n ∈ N , N 是自然數集合. 則 12×21 + 22×22 + 32×23 +…+ n2×2n = (n2-2n+3)×2n+1 - 6 成立.

歸納基礎 :

No comments:

Post a Comment

( 試證明：1×2²+2×3²+3×4²+…+n×(n+1)²= [n(n+1)(n+2)(3n+5)]/12

1) 試證：1²×2¹+ 2²×2²+ 3²×2³+…+ n²×2ⁿ= (n²-2n+3)×2ⁿ⁺¹- 6

令 P(n) 為一個命題, P(n): ∀n ∈ N , N 是自然數集合. 則 1²×2¹+ 2²×2²+ 3²×2³+…+ n²×2ⁿ= (n²-2n+3)×2ⁿ⁺¹- 6 成立.