3-3 數學歸納法

3-3 數學歸納法

3-3 數學歸納法

(甲) 數學歸納法 

這個例子, 可以嘗試用 n = 1, 2,3, ...漸漸代入 , 求得等式兩邊是否相等. 然後再推論其對所有的自然數.  最後用數學歸納法證之.

乍看之下, n = 1
1 - 1 + 41 = 41 is prime
n = 2 ,  4 - 2 + 41 = 43 is prime
n = 3 ,  9 - 3 + 41 = 47 is prime
n = 4 , 16 - 4 + 41 = 53 is prime
 ... and so  forth .
都成立 .

But n = 41 , 41^2 - 41 + 41 = 41^2 is a perfect square ,not prime .

依題意 , 如果是偶數且是質數只有 2 , 其餘都是奇數.
假設針對任何一個偶數 n , 其可以表示為任兩個奇質數p1,p2 之和,即 n = p1+ p2 .
使用數學歸納法:
n = 8 ,
6 = 3 + 5
n = 10 ,
10 = 7 + 3
n = 12 ,
12 = 7 + 5
n = 14
14 = 11 + 3
... and so forth .

看起來似乎是成立的. 但是真的這樣嗎 ?
奇質數必能表示為 2k + 1 形式 , 但k 非為自然數所有的集合.
任何偶數 必能寫成 偶 +偶  or 奇 + 奇
但是 偶數  =  必為非質數偶數的平方 (除了2之外)

所以是事實. But how to prove it ?   

 It is clear . 這是個矛盾的命題, 原因是
 n > -1 , n ∈ Z  . n = 0 ,   0 =  0 + 1998 是矛盾的.

有些證明說明必須記的性質

 



(1)
n = 1 , ( 1+3/1) = (1+3) = 4 = 2^2
n = 2 , ( 1+3/1)(1+5/4)  = 9 = 3^2
n = 3 , ( 1+3/1)(1+5/4)(1+7/9) = 16 = 4^2
...
觀察並假設 n ∈ N , P(n) : (1+3/1)(1+5/4) ... (1+2n-1/n^2) = (n+1)^2  
Using mathematical induction
Induction Basis :
n = 1 , P(1) is true.
Inductive Steps :
Assume  n = k , k > 1 ; P(k) holds .
Consider that n = k+1 ,
(1+3/1)(1+5/4) ... (1+2k-1/k^2)(1+2k+1/(k+1)^2) = [ (k+1)^2 ](1+2k+1/(k+1)^2)  = (k+1)^2 + 2k+3 = (k+2)^2  Q.E.D.

(1)  1^3+ 2^3 + ... + n^3 is a proposition P(n) , n = 1,2,3,4,5, ...

n = 1 , 1^2
n = 2 , 1+ 8 = 9 = 3^2
n = 3 , 1+8+27 = 36 = 6^2
n = 4 , 1+8+27+64 = 100 = 10^2
...
觀察,假設 P(n) :   1^3+ 2^3 + ... + n^3 =  [n^2(n+1)^2]/4 

Using mathematical induction.

Induction Basis :
n = 1 , 10+12+5 = 27 , 9 | 27 .
Inductive Steps :
Assume that n = k , k > 1 ; 9  | 10^k+3*4^k + 5
Consider  that  n = k +1 ,
10^(k+1) + 3*4^(k+1)+ 5 = 10*10^k + 12*4^k + 5 = ( 10^k+3*4^k + 5 ) + 9(10^k+3*4^k + 5) = 9 m + 81m . So 9 | 10^(k+1) + 3*4^(k+1)+ 5  holds.

P(n) : 1/1^2 +1/2^2+ ... + 1/n^2  ≤  2 - 1/n , n ∈ N  
Using mathematical induction  
Induction Basis :  
n = 1 , 1^2 ≤  2 - 1/1  , it is true.
Inductive Steps :
Assume that n = k ,  1/1^2 + ... + 1/k^2 ≤ 2 - 1/k  
Consider that n = k +1 , 1/1^2 + ... + 1/k^2 +  1/(k+1)^2 ≤ 2 - 1/k  +  1/(k+1)^2 = 2 + 1/(k+1)^2

Induction on n

Induction Basis :
n = 4 , 2^4 = 16 ≥ 4^2 is ture . 
Inductive Steps : 
Assume  that n = k , k > 4 , 2^k ≥ k^2 

Consider n = k +1 , 2^(k+1) = 2*2^k  ≥ 2*2^k = 2^k + 2^k ≥ k^2  + k^2 ≥    k^2 + 2k+1 Q.E.D. 

當 n = 2 時 , people A 高與自己一樣 , people B 高與自己一樣 , but A, B 不同高 . 這個條件未成立.

Using mathematical induction

Induction Basis : 
n = 1 , 1*2^2 = 2 = 1/12*1*2*3*8 is true.
Inductive Steps : 
Assume that n = k , k > 1 ; 1*2^2+2*3^2 + ... + k(k+1)^2 = 1/12 k(k+1)(k+2)(3k+5) holds .
Consider n = k +1 , 1*2^2+2*3^2 + ... + k(k+1)^2+(k+1)(k+2)^2  = 1/12 k(k+1)(k+2)(3k+5) + (k+1)(k+2)^2 = (k+1)(k+2)[k(3k+5)+12k+24]/12  = (k+1)(k+2)[3k^2+17k+24]/12 = (k+1)(k+2)(3k+8)(k+3)/ 12 Q.E.D.

(1)

n = 2 , (1-1/4) = 3/4 = 2+1/2*2
n = 3 , (1-1/4)(1-/9) = 3/4*8/9 = 2/3 = 4/6 = 3+1/2*3
n = 4 , (1-1/4)(1-1/9)(1-1/16) =  3/4*8/9*15/16 = 2/3*15/16 = 5/8 = 4+1/2*4

Suppose that  (1-1/4)(1-1/9)(1-1/16) ...(1-1/n^2) = n+1/2*n , n ≥ 2  

Induction Basis :
n = 2 ,  (1-1/4) = 3/4 = 2+1/2*2  is true.
Inductive Steps : 
Assume that n = k , (1-1/4)(1-1/9)...(1-1/k^2) = k+1/2*k holds .  
Consider that n = k +1 , (1-1/4)(1-1/9)...(1-1/k^2) (1-1/(k+1)^2) = [ k+1/2*k ]k(k+2)/(k+1)^2  = k+2/ 2*(k+1) 
故  (1-1/4)(1-1/9)(1-1/16) ...(1-1/n^2) = n+1/2*n , 對 n ≥ 2   

Let S = 1+2+3+...+(n-1)+n+(n-1)+ ...+3+2+1  
      S = [1+2+3+ ...+(n-1)] + n +[(n-1)+ ...+3+2+1] = 2[1+2+3+...+(n-1)] + n = 2*(n-1+1)(n-1) /2 + n = n(n-1) + n = n^2 
Induction on n : 
n = 1 , 1 = 1^2 
Inductive Steps : 
Assume that n = k , k > 1 ;  1+2+3+...+(k-1)+k+(k-1)+ ...+3+2+1 = k^2 
Consider that n = k +1 , 
1+2+3+...+(k-1)+k+(k+1)+k+(k-1)+ ...+3+2+1 =  [1+2+3+...+(k-1)+k+(k-1)+ ...+3+2+1]+(k+1)+k = k^2 + 2k +1 = (k+1)^2  
故  1+2+3+...+(n-1)+n+(n-1)+ ...+3+2+1 = n^2 , n 為自然數. 

Using mathematics induction 
Induction Basis : 
n = 1 , 100 + 60 - 6 = 154 , 22 | 154 
Inductive Steps : 
Assume that n = k  and k > 1 , 22 |10^2k + 5*12^k - 6 holds . 
Consider that n = k+1 , 
10^2(k+1) + 5*12^(k+1) - 6  
= 100 * 10^2k + 12*(5*12^k)  - 6 
= ( 10^2k + 5*12^k - 6 ) + 99 * 10^2k + 11* (5*12^k) 
= 22 m  + 11*9*10^2k + 11*5*2^k*6^k
= 22 m + 11*9*2^k*5^k + 11*5*2^k*6^k 
= 22m + 22*(9*2^k-1*5^k+5*2^k-1*6^k) 
Q.E.D.  

 

Induction on n 
Induction Basis : 
n = 3 , 5^3 = 125 > 8 + 27 is true. 
Inductive Steps : 
Assume that n = k and k > 1 , 5^n > 2^n + 3^n holds . 
Consider that n = k+1 , 
5^k+1 = 5*5^k > 5(2^k+3^k) > 2*2^k + 3*3^k = 2^k+1 + 3^k+1 Q.E.D. 


(乙) 遞迴數列

 

















(1) 從  n = 1 開始 , 
    一條線分割兩個區域, 即 a1 = 2 
    n  = 2 , a2 = 4  = 2 + 2 
    n  = 3 , a3 = 7 = 4 + 3 (看起來還是不容易找到規律) 
    n  = 4 , a4 = 11 = 7 + 4 
  (2)  ... 看起來好像有一個規律存在, 即 an = an-1 + n , n = 2,3,4, ...  

    

{an} : 1 , 3 , 6 , 10 , 15 , 21 , ...
  a1 = 1
 a2 = 3 = 1 + 2
 a3 = 3 + 3 = 3 + (2+1)
 a4 = 10 = 6 + 4 = 6 + (3+1)
 .....
可以觀察出一種關係, 即 an = an-1 + n  , n = 2,3,4,5,6, ... 

(2) 
  an+1 = an + f(n)
  an = an-1 + f(n-1)
   an-1 = an-2 + f(n-2)
   an-2 = an-3 + f(n-3)
   ...
  a2 = a1 + f(1)
  a1 = a0 + f(0)

  an+1 = a0 + f(n) + f(n-1) + f(n-1) + ... + f(2) + f(1) + f(0)  .


an+1 = an * f(n)
an = an-1 * f(n-1)
an-1 = an-2 * f(n-2) 
... 
a3 = a2 * f(2) 
a2 = a1 * f(1) 
a1 = a0 * f(0)
    
an+1 = f(n)* f(n-1)* f(n-2)* ... * f(3)* f(2)*f(1)*f(0)

an+1 = αan + k
αan = α²an-1 + αk
α²an-1 = α³an-2 + α²k
α³an-2 = α⁴an-3 + α³k
....
α^n-1a2 = αⁿa1 + α^n-1k

αⁿa1 = αⁿ⁺¹a0 + αⁿk

an+1 = k + αk + α²k + ... +  α^n-1k + αⁿk + αⁿ⁺¹a0  = k ( 1 + α + α² + α³+ ... + αⁿ ) +   αⁿ⁺¹a0
an+1 = αan + k
an+1 - β = α(an - β)  , then we can obtain following
β - αβ = k . β(1-α) = k , β = k /(1-α) , α ≠ 1.  

a1 = 1 
a2 = a1 + 3  = 1 +3 = 4 
a3 = a2 + 3*4 = 4 + 12 = 16 
a4 = a3 + 3*9 = 16 + 27 = 43 
a5 = a4 + 3*16 = 43 + 48 = 91  

an+1 - an = 3n²   
an - an-1 = 3(n-1)²
an-1 - an-2 = 3(n-2)^{2 
... 
a3 - a2 = 3(2)2 
a2 - a1 = 3(1)2} 
an+1 - a1  = 3[ n²  +  (n-1)² +  (n-1)² +  ... +  +  (2)² +  (1)² ]  = 3 [n(n+1)(2n+1)/6] = 

 n(n+1)(2n+1)/2 , an+1 =  n(n+1)(2n+1)/2  +1 . 

an+1 = 3an  + 1 

3an = 3²an-1  + 3 
3²an-1 = 3³an-2  + 3^2 
... 

3^n-2a3 = 3^n-1a2  + 3^n-2 

^{3n-1a2 = 3na1  + 3n-1} 

^{= 1 + 3 + 3^2 + ... + 3^n  = ( 3^n - 1 )/ 2}  

an+1 = 5an + 4
5an = 5²an-1 + 5*4
5²an-1 = 5³an-2 + 5²*4
...

5^n-1a2 = 5ⁿa1 + 5^n-1*4

an+1 = 4 + 4*5 + 5²*4 + ... + 5ⁿa1 + 5^n-1*4  = 4*[5 + 5²+ ... + 5ⁿ] - 5ⁿ 

 ^{a1 = 1 , a2 = 5 , a3 = 12, a4 = 22 , a5 = 35 , a6 = 51 , ...}

a2  - a1 = 4 = 3 + 1

a3  - a2 = 7 = 3*2 + 1

a4  - a3 = 10 = 3*3 +1

... 

an  - an-1 = 3*(n-1) + 1 

  

an  - a1  = 4 + 7 + 10 + ... + 3*(n-1) +1
an  = 1 + 4 + 7 + 10 + ... + 3*(n-1) +1  = n(3n - 2 +1) / 2 = ( 3n^2 - n )/ 2

如果有n 個 discs 則有 (n-1) 個 discs 必須做2次的movement , 最後在加1次的movement .
所以 T(n) = 2T(n-1) +1 . 這個用一般的式子表達為 2^n -1 .
Using mathematical induction
Induction Basis : 
n = 1 , 只做一次movement , 即 2^2-1
Inductive Steps : 
假設 n = k 且 k > 1 , 搬移次數為 兩次的 n-1 discs 的搬移, 加上 1次的 最小 disc 的搬移為 2^k-1+1.
考慮  n = k +1 , 即在 k 個碟子多加一個disc , 其前面 k 個 discs 有 2^k 的搬移兩次 ,即 2^k+1 在加一次movement , 即  2^k+1 + 1

(1) 可略
(2)
using mathematical induction  ,

Induction Basis : 

n = 2 ,  1 < √2  < 2 , 1 + 2 < √2   + 2 < 2 + 2 , 3 < √2  + 2  < 4 ,   √3   <  √√2  + 2  < √4 

Inductive Steps  : 

Assume that n = k and k > 1 ;   ak+1 =  √2+ak < 2

Consider that n = k +1 , ak+2 =   √2+ak+1 

2 + ak+1 < 2 + 2 

√2 + ak+1 < √4 Q.E.D.