數學歸納法

Prove, by mathematical induction, that
1．5 + 2．6 + 3．7 + ... + n(n+4) = (1/6)n(n+1)(2n+13)
for all positive integers n.
當 n = 1 時
LHS = 1‧5 = 5
RHS=(1/6)n(n+1)(2n+1 3)
=(1/6)(1)(1+1)(2(1)+ 13)
= (1/6)(1)(2)(15)
= 5
所以 n = 1 成立
設 n = k 時成立，則
1．5 + 2．6 + 3．7 + ... + k(k+4) = (1/6)k(k+1)(2k+13)
當 n = k+1
LHS =
1．5 + 2．6 + 3．7 + ... + k(k+4) + (k+1)(k+5)
= (1/6)k(k+1)(2k+13) + (k+1)(k+5)
= (k+1)[(1/6)k (2k+13) + (k+5)]
= (k+1)[k (2k+13) + 6(k+5)]/6
= (k+1)[2k2+13k + 6k+30]/6
= (k+1)[2k2+19k+30]/6
= (k+1)(k+2)(2k+15)/6
= (k+1)(k+2)(2(k+1)+13 )/6
= RHS
所以這式成立

(b) It is given that 1 + 2 + 3 + ... + n = (1/2)n(n+1).
Hence, using the result of (a), find the sum of
(i) 1．4 + 2．5 + 3．6 + ... + n(n+3), and
1．5 + 2．6 + 3．7 + ... + n(n+4) = (1/6)n(n+1)(2n+13)
1．(4+1) + 2．(5+1) + 3．(6+1) + ... + n(n+3+1)
= 1．4 + 2．5 + 3．6 + ... + n(n+3) + 1 + 2 + 3 + …. + n
所以
1．4 + 2．5 + 3．6 + ... + n(n+3)
= (1/6)n(n+1)(2n+13) – (1/2)n(n+1)
= n(n+1)[(2n+13)/6 – 1/2]
= n(n+1)(2n+13 –3)/6
= n(n+1)(2n+10)/6

(ii) 1² + 2² + 3² + ... + (2n)²
1．(1+4) + 2．(2+4) + 3．(3+4) + ... + n(n+4)+...+2n(2n+4)
= 1² + 2² + 3² + ... + n² +...+(2n)^2+4(1+2+3+…+n+...+2n)
所以
1² + 2² + 3² + ... + n² +...+(2n)^2

= 1．(1+4) + 2．(2+4) + 3．(3+4) + ... + n(n+4)+...+2n(2n+4)- 4(1+2+3+…+n+...+2n)
=(1/6)(2n)(2n+1)(4n+13) - 4(1/2)(2n)(2n+1)
= (2n)(2n+1)[(1/6)(4n+13) – 2]
= (2n)(2n+1)[4n+13 – 12]/6
= (2n)(2n+1)(4n+1)/6
=1/3[n(2n+1)(4n+1)]
(iii)
2^2+4^2+6^2+...+(2n)^2
=2^2[1^2+2^2+3^2+...+n^2]
=4([1^2+2^2+3^2+...+n^2])
=4n(n+1)(2n+1)/6
=2/3[n(n+1)(2n+1)]
(iv)
1^2+3^2+5^2+...+(2n-1)^2
=[1^2+2^2+3^2+...+(2n)^2]-[2^2+4^2+6^2+...+(2n)^2]
=1/3[n(2n+1)(4n+1)]-2/3[n(n+1)(2n+1)]
=1/3(n)(2n+1)[4n+1-2(n+1)]
=1/3(n)(2n+1)(2n-1)

數學歸納法
數學歸納法﹝Mathematical Induction﹞是用來証明某些與自然數n有關的數學命題的一種方法。它的步驟是：

驗証n=1時命題成立﹝這叫歸納的基礎，或遞推的基礎﹞；
假設n=k時命題成立﹝這叫歸納假設，或叫遞推的根據﹞，在這假設下証明n=k+1時命題成立。

根據1、2可以斷定命題對一切自然數都成立。


數學歸納法的思想可以遠推至歐幾里得﹝前330-前275﹞。嚴格的數學歸納法是在16世紀後期才引入的。1575年意大利數學家、物理學家莫洛克斯﹝1494-1575﹞在他的《算術》一書中明確提出了這一方法，並且用它証了
1+3+……+(2n+1)=(n+1)2
等；法國著名數學家帕斯卡﹝1623-1662﹞承認莫洛克斯引用了這方法，並在他的著作《三角陣算術》中運用了這一方法。


因此，一般認為帕斯卡是數學歸納法的主要發明人。由於帕斯卡還沒有表示任意自然數的符號，因此組合公式及証明只能用敘述的方法，1686年J‧伯努利首先採用了表示任意自然數的符號，在他的名著《猜度術》﹝1713﹞中包含運用數學歸納法証題的出色例子。『數學歸納法』這個名稱及數學歸納法的証題形式是德‧摩根﹝1806-1871﹞所提出的。皮亞諾﹝1858-1932﹞的自然數公理中包含了歸納


EXAMPLE:
1.利用數學歸納法，證明對於所有正整數n，
1 + 2 + 3 + … + n = ½ n (n + 1)
證明:(步驟1)
設 P(n) 為命題 “1 + 2 + 3 + … + n = ½ n (n + 1)”
當 n = 1，左方 = 1
右方 = ½ (1)(1 + 1) = 1
左方 = 右方
P(1) 成立

步驟2: 假設 P(k) 成立
即 1 + 2 + 3 + … + k = ½ k (k + 1)
當 n = k + 1， 1 + 2 + 3 + … + k + (k + 1)
= ½ k (k + 1) + (k + 1)
= ½ [k(k + 1) + 2(k + 1)]
= ½ (k + 1)(k + 2)
= ½ (k + 1)[(k + 1) + 1]
P(k + 1) 成立。
結論:根據數學歸納法，對於所有正整數n，P(n) 都成立。