Mathematical Induction Second Principle

只有一點不同
First Principle of mathematical induction
1. Basis step. The proposition P(1) is shown to be true.
2. Inductive step. The implication P(n)
圖片參考：http://www.cs.odu.edu/~toida/nerzic/content/symbols_sets/imp.gif
P(n+1) is shown to be true for
every positive integer n.In the inductive step, we usually assume that P(n) is true (this assumption is called the inductive hypothesis) and try to show that then
P(n+1) is also true.
Second principle of mathematical induction:
To show that P(n) is true for every positive integer n, show that:
Basis step. P(1) is true.
Inductive step. For every positive integer n, if P(1), P(2), …, P(n) are
true, then so is P(n+1).
所以不同點只是Second principle 中的Inductive step假設P(1), P(2), …, P(n)都是對的。而First Principle 只需假設P(n) 是對的。
幾時要用Second Principle,幾時不需要呢?
是由題目決定的。有些基本題目只需用First Principle 就可以。如以下例子:
prove,by mathematical induction , that
1^2+2^2+3^2+...+n^2=(1/6)x n x(n+1)(2n+1)
Let P (n) be the proposition 1^2+2^2+3^2+...+n^2= (1/6) n (n+1) (2n+1),
where n is a natural number

(i) When n = 1
L H S =1^2 = 1
R H S = (1/6)(1) (1 + 1) [2(1) + 1] = (1/6)(1)(2)(3) = 1
L H S = R H S
∴P (1) is true.

(ii) Assume P (k) is true, where k is a natural number
That is, 1^2+2^2+3^2+...+k^2= (1/6) k (k+1) (2k+1)

L H S of P (k+1)
= 1^2+2^2+3^2+...+k^2 + (k+1)^2
= (1/6) k (k+1) (2k+1) + (k+1)^2
= (1/6) [k (k+1) (2k+1)] + 6[(k+1)^2] / 6
= (1/6) (k+1) [k (2k+1) + 6(k+1)]
= (1/6) (k+1) [2k^2 + k + 6k + 6]
= (1/6) (k+1) (2k^2 + 7k + 6)
= (1/6) (k+1) (k + 2) (2k + 3)
= (1/6) (k+1) [(k + 1) + 1] (2k + 2 + 1)
= (1/6) (k+1) [(k + 1) + 1] [2(k + 1) + 1]
= R H S of P (k+1)
∴ P (k + 1) is true if P (k) is true

By the principle of Mathematical Induction, P (n) is true for all natural numbers n.
例如這條Inductive step 中只需假設 P(n)是對的便成﹐就算多設P(1), P(2), …, P(n-1)是對的也用不著。
這類加數題多數用First Principle 就可完成。
但有時則非用Second Principle不可
例
Show that if n∈Z and n >1, then n can be written as the product of primes.
Proof :
Let P(n) be the proposition that n can be written as the product of primes.
Basis : P(2) is true, since 2 is a prime number
Inductive : Assume P(k) is true for all k<=n.
Consider P(n+1) :
Case 1 : n+1 is prime . P(n+1) is true
Case 2 : n+1 is composite. i.e., n+1=ab where 2 <=a<=b <n+1
By the induction hypothesis, both a and b can be written as the product of primes.
[注意:因為不知確實的a,b是甚麼﹐所以要假設P(k) is true for all k<=n]
So P(n+1) is true.
By Second principle of mathematical induction, P(n) is true if n∈Z and n >1