數的概念 (第 2 頁)

　1│2│3│4│5│6　

數的概念（第 2 頁）

康明昌

首頁 | 搜尋

．原載於數學傳播第六卷第四期、第七卷第一期
．作者當時任教於台大數學系

‧註釋
‧對外搜尋關鍵字

2.數學歸納法

2.1 什麼是數學歸納法？（一）

考慮以下的例題與「證明」。

例題1 求證 $1^3+2^3+\cdots +n^3=\frac{n^2(n+1)^2}{4}$ ，其中 n是任意正整數。

證明：若n=1，左式=1³= $\frac{1^2(1+1)^2}{4}$ =右式

若n=2，左式=1³+2³=9= $\frac{2^2(2+1)^2}{4}$ =右式

若n=3，左式=1³+2³+3³=36= $\frac{3^2(3+1)^2}{4}$ =右式

若n=4，左式= 1³+2³+3³+4³=100= $\frac{4^2(4+1)^2}{4}$ =右式

若n=5，左式= 1³+2³+3³+4³+5³=25= $\frac{5^2(5+1)^2}{4}$ =右式

以此類推，可知對於任意正整數 n，原式都成立。

以上的「證明」有什麼錯誤呢?

我們想一想，以上的「證明」其實只證明 n=1,2,3,4,5 時，原式成立。那麼 $n\geq 6$ 時，有沒有證明呢？

在 $n\geq 6$ ，以上的「證明」只用「以此類推」就一筆帶過。

什麼是以此類推呢？以此類推是表示 $n\geq 6$ 的證明幾乎和 n=1,2,3,4,5 的證明完全一樣。可是我們想一想，即便我們知道 1³ + 2³ + … +5³ 的數值，我們是否能夠很容易的推出 1³ + 2³ + … +100³ 的數值呢？如果不能，n=100 的證明顯然就不能夠用以此類推矇混過去。

有些同學可能會說：你既然不相信我能夠證明 n=100，我就證明給你看。你只要給我一小時的時間，我就可以求出 1³, 2³, 3³, …, 100³，再求其和，然後證明這個式子。

問題就在這裏：你要用一小時的時間證明 n=100 的情形，你究竟要用多少時間才能證明 n=10³ 的情形？此外，在 10³ 之後，還有無窮無盡的正整數等著你一個一個去驗證呢！

愚公想用幾代子孫的力量把一座山搬走，因為一座山的範圍是有限的。我們現在問題的核心，正整數，是無限的。愚公移山式的方法，顯然不能解決我們的問題。

想個新的方法吧。

假設我們能夠證明「若 k 是任意正整數，並且 n=k 時原式成立，則 n=k+1 時原式亦成立」，那麼我們就可以輕而易舉的證明這個恒等式了。為什麼呢？

例如，你想證明 n=100 時原式成立，依照上面的假設，你只要證明 n=99 時原式成立就夠了。

那麼 n=99 時原式會不會成立呢？再用一次我們的假設，我們只要證明 n=98 時原式成立就夠了。

那麼 n=98 時原式會不會成立呢？再用一次我們的假設，我們只要證明 n=97 時原式成立就夠了。

以此類推，我們只要 n=1 時原式成立就夠了。

更一般的說，我們不要把 n 限制為100，現在讓 n 是任意正整數。假定我們能夠證明我們最先的假設是成立的，那麼只要我們能夠證明 n=1 時原式成立，我們就可以推出 n 是任意正整數時原式亦成立。

這就是數學歸納法。

數學歸納法的要點是：

: 一、證明 n=1 時原式成立。
: 二、若 k 是任意正整數，證明「若 n=k 時原式成立，則 n=k+1 時原式亦成立」。

現在我們把例題1.的正確的證明寫在下面。

證明：

(1) 若n=1時，左式=1³=1= $\frac{1^2(1+1)^2}{4}$ =右式

(2) 設k是任意正整數。證明:若n=k時原式成立，則n=k+1時原式亦成立。

假設n=k時，原式成立，即1³+2³+…+k³= $\frac{k^2(k+1)^2}{4}$ 。

考慮n=k+1的情形。

$\begin{eqnarray*} \mbox{{\fontfamily{cwM1}\fontseries{m}\selectfont \char 10}\hs... ...t \char 13}{\fontfamily{cwM0}\fontseries{m}\selectfont \char 1}} \end{eqnarray*}$

(3) 綜合(1)與(2)，可知：對於任意正整數n，原式皆成立。

注意:一般學生在運用數學歸納法時，常會犯下如下的錯誤，如

一、在第(1)步驟時，許多學生可能以為 n=1 時太簡單了，不好意思寫這麼簡單的證明，因此他在這個步驟寫 n=4 或 n=5 時的證明。

請注意，你如果這樣寫的話，你只證明原式在 $n\geq 4$ 或 $n\geq 5$ 時成立，你並沒有證明原式對於任意正整數 n 都成立。（為什麼？）

還有些同學比較客氣，他們也不好意思只寫 n=1 時的證明，他們大概覺得寫得太少不太好，所以他們在這個步驟寫上 n=1,2,3 時的證明。這是過分小心的。大膽一點，只要寫上 n=1 的證明就夠了。

二、最常見的，也是最嚴重的錯誤是以下的類型：

(1) n=1時原式成立。

(2) n=k時原式成立，

即 $1^3+2^3+\cdots +k^3=\frac{k^2(k+1)^2}{4}$

n=k+1 時，左式= $\cdots\cdots$

(3) $\cdots\cdots$

以上的錯誤的寫法是在第(2)步驟。

錯誤的地方是，沒有明白的指出「n=k時原式成立」這件事究竟是你已經證明出來的，還是你的假設。

例題2 若 p>-1，且 $p\neq 0$ ，證明 (1+p)¹⁰⁰ >1+100p。

想法：如果p>0，由二項式定理

$\begin{displaymath}(1+p)^{100}=1+100p+\frac{100\cdot 99}{1\cdot 2} p^2 \\ +\fra... ...s +\frac{100\cdot 99\cdots 2}{1\cdot 2\cdots 99} p^{99}+p^{100}\end{displaymath}$

可得 (1+p)¹⁰⁰ >1+100p。問題在，如果 -1<p<0 時，怎麼辦？

我們不妨作個大膽的猜測：「 (1+p)ⁿ > 1+np」是否恒成立？

要想用「數學歸納法」證明「 (1+p)ⁿ > 1+np」，我們想證明「若 n=k 時原式成立，則 n=k+1 時原式亦成立。」很幸運的，這個步驟並不困難。

但是 n=1 時，「1+p>1+p」並不成立！

幸好 n=2 時， (1+p)² =1+ 2p + p² > 1 + 2p。

所以我們的猜測應該修正為：「若 $n\geq 2$ ，且 n 是正整數，則 (1+p)ⁿ > 1+np，其中 p>-1， $p\neq 0$ 。」

證明：我們要證明，(1+p)ⁿ>1+np，其中 $n\geq 2$ ，n 是正整數。

用「數學歸納法」證明。

(1) n=2時，左式=(1+p)²
=1+2p+p²
>1+2p
=右式

(2) 證明：若 n=k 時，原式成立，則 n=k+1 時原式亦成立。

由 n=k 時原式成立，得 (1+p)^k > 1+kp。

考慮 n=k+1 的情形，左式 =(1+p)^k+1=(1+p^k)(1+p) >(1+kp)(1+p)=1+(k+1)p+kp² >1+(k+1)p = 右式

(3) 綜合(1)與(2)，可知原式對於 $n\geq 2$ 的整數都成立。

因此 (1+p)¹⁰⁰>1+100p，得證。

例題3

若 n 是任意正整數，試證

$\begin{displaymath} (\sqrt{3} +1)^{2n+1}-(\sqrt{3} -1)^{2n+1} \end{displaymath}$

是正整數，並且可被2ⁿ⁺¹整除。

想法：

檢查「若 n=k 時成立；則 n=k+1 時成立」是否辦得到。

由 n=k 成立得 $(\sqrt{3} +1)^{2k+1} - (\sqrt{3} -1)^{2k+1} = 2^{2k+1}a$ ，其中 a 是某個正整數。考慮 n=k+1 的情形。

$\begin{eqnarray*} \lefteqn{ (\sqrt{3} +1)^{2(k+1)+1}-(\sqrt{3} -1)^{2(k+1)+1} } ... ... 8\cdot 2^{k+1}a-4\{ (\sqrt{3} +1)^{2k-1}-(\sqrt{3} -1)^{2k-1}\} \end{eqnarray*}$

現在如果我們知道「 $(\sqrt{3} +1)^{2k-1} - (\sqrt{3} -1)^{2k-1}$ 是一個可被 2^k 整除的正整數」，那麼 n=k+1 時就成立了！但是「 $(\sqrt{3} +1)^{2k-1} - (\sqrt{3} -1)^{2k-1}$ …」正好是 n=k-1 的情況。

所以在第(2)步驟，我們改作「若n=k，k+1時皆成立，則n=k+2時亦成立」。為了順應第(2)步驟的修正，第(1)步驟要改成「n=1時原敘述成立，n=2時原敘述亦成立。」

證明：

我們用「數學歸納法」證明。

(1) n=1時， $(\sqrt{3} +1)^3-(\sqrt{3} -1)^3 =20$ 可被 2² 整除。

n=2 時， $(\sqrt{3} +1)^5-(\sqrt{3} -1)^5 = 152$ 可被 2³ 整除。

(2) 證明：若 n=k，k+1 時成立，則 n=k+2 時亦成立。

由 n=k 時成立，得

$\begin{displaymath}(\sqrt{3} +1)^{2k+1}-(\sqrt{3} -1)^{2k+1}=2^{k+1}a\end{displaymath}$

由n=k+1時成立，得

$\begin{displaymath}(\sqrt{3} +1)^{2k+3}-(\sqrt{3} -1)^{2k+3}=2^{k+2}b\end{displaymath}$

其中 a 與 b 都是正整數。

考慮 n=k+2 的情形，

$\begin{eqnarray*} \lefteqn{ (\sqrt{3} +1)^{2k+5}-(\sqrt{3} -1)^{2k+5} } \\ &=&... ...t \char 98}{\fontfamily{cwM0}\fontseries{m}\selectfont \char 1}} \end{eqnarray*}$

(3) 綜合(1)與(2)，可知 $(\sqrt{3} +1)^{2n+1} - (\sqrt{3} -1)^{2n+1}$ 是一個可被 2ⁿ⁺¹ 整除的正整數。

「數學歸納法」是人類很早就非常熟悉的工具。早在古希臘時代，Euclid（歐基里德，約300B.C.）在證明「質數是無窮多的」時，已經掌握了「數學歸納法」的基本精神（見下一小節的例題1）。以後許多數學家都不自覺的利用「數學歸納法」證明各種問題。第一個明確的指出「數學歸納法」的形成與原理，是法國數學家 Blaise Pascal（巴斯噶 1623-1662） ¹ 。

習題1

證明

$\begin{displaymath} 1^2+2^2+\cdots +n^2=\frac{n(n+1)(2n+1)}{6} \end{displaymath}$
試用「數學歸納法」證明等差級數公式與等比級數公式。
證明

$\begin{displaymath} 1\cdot 2\cdot 3 + 2\cdot 3\cdot 4 + \cdots + n (n+1)(n+2) = \frac{1}{4} n(n+1)(n+2)(n+3) \end{displaymath}$
證明 5²⁰ >3²⁰+4²⁰。
證明 3ⁿ>n³ 其中 $n\geq 4$ 。
（提示：你能否證明 $3^{\frac{1}{3}} > 1+\frac{1}{n}$ 若 $n\geq 4$ ？）
證明「二項式定理」：

$\begin{eqnarray*} (1+x)^n &=& 1 + nx + \frac{n!}{2!(n-2)!} x^2 + \frac{n!}{3!(n... ...c{n!}{k!(n-k)!} x^k + \cdots + \frac{n!}{(n-1)!1!} x^{n-1} + x^n \end{eqnarray*}$

其中 x 是任意數，n 是任意正整數， $n! =1 \cdot 2 \cdot 3 \cdots n$ 。
證明

$\begin{eqnarray*} \lefteqn{ (1+x) (1+\frac{x}{2}) (1+\frac{x}{3}) \cdots (1+\fra... ...x+1)(x+2)}{3!} + \cdots + \frac{x(x+1)(x+2) \cdots (x+n-1)}{n!} \end{eqnarray*}$

其中 x 是任意數，n 是任意正整數。
設 -1<x_i<0，i=1,2,…,n，證明

$\begin{displaymath} (1+x_1) (1+x_2) \cdots (1+x_n) > 1 + x_1 +\cdots + x_n \end{displaymath}$

（討論：若 $x_i\geq 0$ ，你能否不用「數學歸納法」，證明 $(1+x_1)(1+x_2) \cdots (1+x_n) \geq 1 + x_1 +x_2 + \cdots +x_n$ ？）
若 $x_i\geq 0$ ，i=1,2,…,n。令 $S_n = x_1+x_2+ \cdots + x_n$ 。證明

$\begin{displaymath} (1+x_1) (1+x_2) \cdots (1+x_n) \leq 1+ S_n + \frac{S_n^2}{2!} + \cdots + \frac{S_n^n}{n!} \end{displaymath}$
證明 xⁿ-nx+(n-1)可被(x-1)²整除，其中 $n\geq 2$ 。
證明 $(3+\sqrt{5} )^n + (3-\sqrt{5} )^n$ 是一個可被 2ⁿ 整除的正整數，其中 n 是任意正整數。
令 x₀=1， $x_n = x_0 + x_1 + \cdots + x_{n-1}$ ，n=1,2,…。證明 x_n=2^n-1。
令 $(\sqrt{3} +\sqrt{2})^{2n-1} = x_n\sqrt{2} + y_n\sqrt{3} + z_n + u_n\sqrt{6}$ 。其中 n 是任意整數，x_n,y_n,z_n,u_n 是整數。求證 z_n = u_n = 0。
（提示：你要作兩種「數學歸納法」，一種從 n=1 開始，推到 n=2,3,4,…，另一種從 n=-1 開始，推到 n= -2, -3, -4,…。）
令 $x_1=\alpha$ , $x_{n+1}=(2\alpha -1) x_n + 1 -\alpha$ ，n=2,3,…。求證

$\begin{displaymath} x_n=\frac{1+(2\alpha -1)^n}{2} \end{displaymath}$
證明 6n⁵ + 15n⁴ + 10n³ -n 是30的倍數。

*2.2 更多的例子

本小節的證明，我們常常省略「數學歸納法」的第三步驟，只寫出證明的要點。

例題1

證明質數是無窮多的。

證明：

我們只要證明「對於任意正整數 n，我們都可找到 n 個相異的正質數」就夠了。現在用「數學歸納法」證明。

: (1) 若n=1，2就是一個正質數。
: (2) 假設n=k時，我們可以找到k個相異的正質數p₁，p₂ …，p_k。
設 $L=p_1p_2\cdots p_k+1$ ，則 $L\geq 3$ 。設p是L的某一個正的質因數。因為p整除 $p_1 p_2 \cdots p_k +1$ ，所以 $p \neq p_1, p_2, \cdots, p_k$ （否則 p 會整除 1，矛盾）。因此 p₁,p₂,…,p_k,p_k+1 =p 是 (k+1) 個相異的正質數。
: (3) 綜合(1)與(2)，可知我們永遠能找到 n 個相異的正質數。

討論：

以上例題是 Euclid 在《幾何原本》（Elements）裏面提出的一個定理。 Euclid 的證明與以上證明在表面上稍有不同，請參看本系列文章「整數的因子分解」。

例題2

設 n 是任意正整數，求證必可找正整數k，使得 $(\sqrt{2} -1)^n$ = $\sqrt{k}$ $-\sqrt{k-1}$ 。

想法：

$(\sqrt{2} -1)^n$ 必可寫成 $u_n + v_n \sqrt{2}$ 的形式，其中 u_n,v_n 都是整數。又因 $\vert\sqrt{2} -1\vert<1$ ，故 u_n 與 v_n 不可能同時是正整數。如果 x_n,y_n 是正整數，那麼 $x_n - y_n \sqrt{2} = \sqrt{k} - \sqrt{k-1}$ 的充分條件是 x_n² - 2y_n² =1。同理如果 x_n,y_n 是正整數，那麼 $x_n\sqrt{2} - y_n = \sqrt{k} - \sqrt{k-1}$ 的充分條件是 2x_n² - y_n² =l。

證明：

第一部份，證明 $(\sqrt{2} -1)^{2n}=x_{2n}-y_{2n}\sqrt{2}$ ，其中 x_2n，y_2n 都是正整數。並且 x_2n²-2y_2n²=1。

(1) n=1， $(\sqrt{2} -1)^2$ =3 $-2\sqrt{2}$ ，且3²- $2\cdot 2^2$ =1。

(2) 設 $(\sqrt{2} -1)^{2k}$ =x_2k $-y_{2k}\sqrt{2}$ ，其中x_2k，y_2k都是正整數，且x_2k² -2y_2k²=1。現在

$\begin{eqnarray*} (\sqrt{2} -1)^{2k+2} &=& (\sqrt{2} -1)^2(\sqrt{2} -1)^{2k}\\ ... ...\sqrt{2} )\\ &=&(3x_{2k}+4y_{2k}) -(2x_{2k}+ 3y_{2k})\sqrt{2} \end{eqnarray*}$

其中 3x_2k + 4y_2k， 2x_2k + 3y_2k 都是正整數，且 (3x_2k +4y_2k)² -2(2x_2k+3y_2k)² =x_2k² -2y_2k²=1。

第二部分，證明 $(\sqrt{2} -1)^{2n-1}$ = $x_{2n-1}\sqrt{2}$ -y_2n-1，其中x_2n-1，y_2n-1都是正整數，並且2x_2n-1²-y_2n-1²=1。

請同學自己做做看吧。

討論：

我們已經證明了 $(\sqrt{2} -1)^n = \sqrt{k} -\sqrt{k-1}$ ，但是 k 究竟是多少呢？
假設

$\begin{displaymath} (\sqrt{2} -1)^n=\sqrt{k} -\sqrt{k-1} \eqno{(1)} \end{displaymath}$

則

$\begin{displaymath} (\frac{1}{\sqrt{2} -1} )^n=\frac{1}{\sqrt{k} -\sqrt{k-1}} \end{displaymath}$

故

$\begin{displaymath} (\sqrt{2} +1)^n=\sqrt{k} +\sqrt{k-1} \eqno{(2)} \end{displaymath}$

(1)+(2)：

$\begin{eqnarray*} \sqrt{k} &=& \frac{1}{2}\{ (\sqrt{2} +1)^n+(\sqrt{2} -1)^n\} \... ...frac{1}{4} \{ 2\sum_{m=0}^n \pmatrix{ 2n \cr 2m \cr } 2^m+2 \} \end{eqnarray*}$

所以，高三同學不妨用以下的提示來證明本題：

證明 $\frac{1}{4} \{ 2\sum_{m=0}^n \pmatrix{ 2n \cr 2m \cr } 2^m+2\}$ 是正整數，且 $(\sqrt{2} -1)^n = \sqrt{k} -\sqrt{k-1}$

: 例題3 已知 x₁,x₂,…,x_n,… 都是正數，並且 $x_1=\sqrt{2}$ ， x_n+1² = x_n + 2。求證
x_n <2，且 $x_1 < x_2 < x_3 < \cdots < x_n < x_{n+1} < \cdots$ 。

證明：欲證x_n<2，x_n<x_n+1。

(1) n=1， $x_1=\sqrt{2}<2$ ，

$x_1=\sqrt{2}<\sqrt{2+\sqrt{2}} =x_2$ 。

(2) 設x_k<2，且x_k<x_k+1。

x_k+1²=x_k+2<2+2=4，故x_k+1<2。

x_k+2²-x_k+1²=x_k+1+2-x_k+1²=-(x_k+1+1)(x_k+1-2)>0，故 x_k+1 < x_k+2。

例題4 已知一組數列 $\frac{1}{1}$ ， $\frac{3}{2}$ ， $\frac{7}{5}$ ，…， $\frac{p_n}{q_n}$ ， $\frac{p_{n+1}}{q_{n+1}}$ ，…，其中p_n+1=p_n+2q_n，q_n+1=p_n+q_n。證明p_n與q_n互質。

證明：

(1) n=1時，p₁=1與q₁=1互質。

(2) 假設p_k與q_k互質。

若r是一個整除p_k+1與q_k+1的正整數，則r整除p_k+1-q_k+1=(p_k+2q_k)-(p_k+q_k)=q_k。故r也整除q_k+1-q_k=p_k。

故r是p_k與q_k的公因數。但是已知p_k與q_k互質。故r=1，即p_k+1與q_k+1互質。

討論：

請同學自己證明

$\begin{eqnarray*} &&\frac{1}{1} <\frac{7}{5} <\frac{p_5}{q_5} < \cdots < \frac{p... ...ac{p_{2n+2}}{q_{2n+2}}< \frac{p_{2n}}{q_{2n}}<\cdots<\frac{3}{2} \end{eqnarray*}$

例題5

已知 $\cos\alpha + \cos\beta + \cos\gamma = \sin\alpha + \sin\beta + \sin\gamma =0$ ，證明

$\begin{displaymath} \cos n\alpha + \cos n\beta + \cos n\gamma = \sin n\alpha + \sin n\beta + \sin n\gamma = 0 \; , \end{displaymath}$

其中 n 是不被 3 整除的正整數。（高一同學不必做這個題目。）

證明：

令

$\begin{eqnarray*} Z_1 &=& \cos\alpha + i\sin\alpha \\ Z_2 &=& \cos\beta + i\sin\beta \\ Z_3 &=& \cos\gamma + i\sin\gamma \end{eqnarray*}$

由 de Moivre 定理，可得

$\begin{eqnarray*} &&( \cos n\alpha +\cos n\beta +\cos n\gamma) +i(\sin n\alpha +... ...n\beta) +(\cos n\gamma +i\sin n\gamma)\\ &=&Z_1^n +Z_2^n +Z_3^n \end{eqnarray*}$

其中 n 是任意整數。

由已知條件知， Z₁ + Z₂ + Z₃ =0，且 $\frac{1}{Z_1} + \frac{1}{Z_2} + \frac{1}{Z_3} =0$ ，故

$\begin{displaymath}Z_1Z_2 +Z_2Z_3 +Z_3Z_1=Z_1Z_2Z_3(\frac{1}{Z_1} +\frac{1}{Z_2} +\frac{1}{Z_3})=0\end{displaymath}$

可見 Z₁, Z₂, Z₃ 是三次方程式 X³-A=0 的三個根，其中 A = Z₁Z₂Z₃。

現在我們要用「數學歸納法」證明所給恆等式。

(1) n=1，這是已給條件。

n=2， Z₁² + Z₂² + Z₃² = (Z₁+Z₂+Z₃)² - 2(Z₁Z₂ +Z₂Z₃ +Z₃Z₁)=0，故

$\begin{displaymath} \cos 2\alpha +\cos 2\beta +\cos 2\gamma = \sin 2\alpha +\sin 2\beta + \sin 2\gamma = 0 \end{displaymath}$

(2) 假設 n=3k-2，3k-1 時皆成立，得

Z₁^3k-2+Z₂^3k-2+Z₃^3k-2=Z₁^3k-1+Z₂^3k-1+Z₃^3k-1=0

因為Z₁³=A，故Z₁^3k+1=AZ₁^3k-2;同理Z₂^3k+1=AZ₂^3k-2，Z₃^3k+1=AZ₃^3k-2。所以

Z₁^3k+1+Z₂^3k+1+Z₃^3k+1=A(Z₁^3k-2+Z₂^3k-2+Z₃^3k-2)=0

得

$\begin{eqnarray*} &&\cos (3k+1)\alpha+\cos (3k+1)\beta+\cos (3k+1)\gamma\\ &=&\sin (3k+1)\alpha+\sin (3k+1)\beta+\sin (3k+1)\gamma=0 \end{eqnarray*}$

同理

Z₁^3k+2+Z₂^3k+2+Z₃^3k+2=A(Z₁^3k-1+Z₂^3k-1+Z₃^3k-1)=0

故

$\begin{eqnarray*} &&\cos (3k+2)\alpha+\cos (3k+2)\beta+\cos (3k+2)\gamma\\ &=&\sin (3k+2)\alpha+\sin (3k+2)\beta+ \sin (3k+2)\gamma=0 \end{eqnarray*}$

討論：

若

$\begin{eqnarray*} && \cos\alpha_1+ \cos\alpha_2+ \cdots+ \cos\alpha_{101} \\ &=&... ...0\alpha_1 +\sin 50\alpha_2 +\cdots +\sin 50\alpha_{101} \\ &=&0 \end{eqnarray*}$

請同學自己證明

$\begin{eqnarray*} &&\cos n\alpha_1 +\cos n\alpha_2 +\cdots +\cos n\alpha_{101} ... ...=& \sin n\alpha_1 +\sin n\alpha_2 +\cdots +\sin n\alpha_{101}=0 \end{eqnarray*}$

其中 n 是不被101整除的整數。

例題6

證明平面上 n 條直線將這平面至多分割成 $1+ \frac{n(n+1)}{2}$ 個區域。

證明：

令 n 條直線

(1) n=1，平面被分割成2=1+ $\frac{1\cdot 2}{2}$ 個區域

(2) 假設k條直線至多分割成1+ $\frac{k(k+1)}{2}$ 個區域。

考慮k+1條直線L₁，L₂，…，L_k+1

如果不考慮L_k+1，則L₁，L₂，…，L_k至多分割出1+ $\frac{k(k+1}{2}$ 個區域。

L_k+1與L₁，L₂，…，L_k的交點至多有k個。由於L_k+1與這些新的交點至多增加了k+1個區域。（為什麼?）

因此k+1條直線至多分割出1+ $\frac{k(k+1)}{2}$ +k+1=1+ $\frac{(k+1)[(k+1)+1]}{2}$ 個平面區域。

習題2

: 1.若a與b都是整數， $(a+b\sqrt{2})^n$ 可以寫成a_n+ $b_n\sqrt{2}$ 的形式，其中a_n與b_n都是整數，n是正整數。證明:如果a是最靠近 $b\sqrt{2}$ 的整數，則對於每一個正整數n，a_n是最靠近 $b_n\sqrt{2}$ 的整數。

2.3 什麼是「數學歸納法」?（二）

回到本節的第2.1小節的例題1。我們要證明1³+2³+…+n³= $\frac{n^2(n+1)^2}{4}$ 。那時候我們發現一種方法:只要能夠證明「若n=k時成立，則n=k+1時也成立」，問題幾乎就迎刃而解了。

同學可能會說:「我不能夠想到這種方法。這種方法好像是從天上掉下來的。平常的人是想不到這種方法的。」

那麼就讓我們再想個新方法吧。同學應該不會反對使用「歸謬證法」吧。

假設這個敘述是錯的。例如，在n=199時，1³+2³+…+199³ $\neq$ $\frac{199^2\cdot 200^2}{4}$ 。很可能，不只在n=199時是錯的，還有很多正整數使這個敘述不成立。我們取出「這個敘述不成立」的最小正整數，令其為k。也就是說，

$\begin{displaymath}1^3+2^3+\cdots +k^3\neq\frac{k^2(k+1)^2}{4}\end{displaymath}$

$\begin{displaymath}1^3+2^3+\cdots +n^3=\frac{n^2(n+1)^2}{4}\,\mbox{, {\fontfamil... ... k-1\mbox{{\fontfamily{cwM0}\fontseries{m}\selectfont \char 1}}\end{displaymath}$

請注意， $k\neq 1$ ，因為n=1時這個敘述顯然成立。

我們現在要導出一個矛盾。

因為

$\begin{displaymath} 1^3+2^3+\cdots +k^3\neq\frac{k^2(k+1)^2}{4} \eqno{(1)} \end{displaymath}$

$\begin{displaymath} 1^3+2^3+\cdots +(k-1)^3=\frac{(k-1)^2k^2}{4} \eqno{(2)} \end{displaymath}$

由 (1)-(2)，

$\begin{displaymath} k^3\neq\frac{k^2(k+1)^2}{4} -\frac{(k-1)^2k^2}{4} \eqno{(3)} \end{displaymath}$

但是

$\begin{eqnarray*} \frac{k^2(k+1)^2}{4} -\frac{(k-1)^2k^2}{4} &=& \frac{k^2\{ (k+1)^2-(k-1)^2 \}}{4} \\ &=& \frac{k^2\cdot 4k}{4}$=$k^3 \end{eqnarray*}$

(3)式顯然是個矛盾。證明完畢。

以上的方法可以總結如下:

: 一、假設這個敘述不正確，我們就可以找到一些反例（counterexamples，也就是這個敘述錯誤的情況）。
: 二、在這些反例中，我們可以找到一個最小反例（minimal counterexample），也就是，找到一個正整數k，使得n=k時這個敘述不成立,n<k時這個敘述一定成立。
: 三、設法導出矛盾。例如，證明「若 n=k-1 成立，則 n=k 亦成立」（若 $k\geq 2$ ），或是證明「若 n=k-2，k-1 成立，則 n=k 成立」（若 $k\geq 3$ ），或是證明「若 n=1,2,…，k-1 成立，則 n=k 成立」（若 $k\geq 2$ ）。

我如果說，這種「最小反例」的方法和第2.1小節所用的「數學歸納法」其實是同樣的精神，同學應該會同意了吧。

同學不妨再進一步想想這種「最小反例」的方法。這種方法其實是利用了自然數一個很顯明（不過也很重要）的性質，即：自然數的任意子集合，如果非空，一定有一個最小的元素。

這個性質表示自然數的大小關係是良序的（well-ordered）。一般來說，一個集合如果具有大小關係，例如整數、有理數或實數，這種大小關係必是良序的，如果任何一個非空的子集合一定都有一個最小的元素。整數、有理數、實數都不是良序的。同學能不能在 N x N 上面定義出一種良序的大小關係?其中 N 代表自然數形成的集合。

有人可能會猜測，一個集合如果是良序的，我們大概就可以利用「最小反例」的方法或「數學歸納法」？答案：完全正確。這種例子在比較高等的數學常常出現，不過我們不準備在此繼續追究下去。

例題：

證明任何大於 1 的整數都可寫成有限個質因數的乘積。

證明：

假設以上敘述不正確。設 n 是最小的不能寫成有限個質因數的乘積的整數。

n不是質數，否則與假設違反。

故 n=mk，其中m， $k\geq 2$ 。因此m，k<n。

所以m與k分別都可寫成有限個質因數的乘積。因此n也可以寫成有限個質因數的乘積。矛盾。

2.4 數學歸納法的誤用

運用數學歸納法時，要注意應該檢查:(1)n=1時是否成立，(2)若n=k時成立，n=k+1是否成立。二者缺一不可。同時在第(2)步驟的k，是任意一個自然數，而不是某些特定的數。

例題1

證明 n²-n+41 是質數。

「證明」

令 f(n)=n²-n+41。

n=1，f(1)=41。
n=2，f(2)=43。
n=3，f(3)=47。
n=4，f(4)=53。
n=5，f(5)=61。
n=6，f(6)=71。

以下類推，f(n)恆為質數。

但是請看 $f(41) = 41 \cdot 40+41= 41^2$ ， $f(42) =42 \cdot 41+41= 41 \cdot 43$ ，都不是質數。

錯在那裏？錯在沒有驗證第(2)步驟。

例題2: 求證一平面上的任意n點，皆在一直線上。
「證明」: 現在讓我們用歸納法來「證明」一下上面的敘述，在
n=1時，這敘述當然成立。
n=2時，這敘述也當然成立，
$\cdots\cdots$

在n=k時，這敘述說：平面上任何k點皆在一直線上，假如這是對的，我們想證明平面上任何k+1個點，皆在一直線上。

設 p₁,…,p_k+1 為這 k+1 個點，因 p₁,… p_k 為 k 個點，故它們必在同一直線上；又因 p₂,p₃,…,p_k+1 是 k 個點，所以它們也在同一直線上。但是任意二點便決定一直線，所以 p₁,p₂,…,p_k+1 必須在同一直線上，因此利用歸納法，我們證明了平面上任意 n 點，皆在一直線上。

但是：我們知到任取三點，便可能不在一直線上，那麼，上面的「證明」錯在那裡？

在k=2時，我們的「證明」發生問題。在k=2轉到k=3時，p₁，p₂固然決定一直線，p₂，p₃也決定一直線，但它們不一定為同一直線。因此p₁，p₂，p₃不一定在一直線上！

我們應該把題目改成：若任意三點皆在一直線上，則任意n點必在一直線上。

習題3

: 1.有人用下法證明全世界的人性別都一樣，設一集合M_n包含n個人，則想證明M_n中的人性別都一樣。當n=1時，M_n中只有一個人，當然其性別是唯一的。現在假定命題當n=k時成立，在假定M_k+1是包含k+1個人的集合。在M_k+1中選定兩個人x和y則 $M_{k+1}\setminus\{ x\}$ 和 $M_{k+1}\setminus\{ y\}$ 都是只包含k個人的集合，所以其中的人性別都一樣，因而x，y和 $M_{k+1}\setminus\{ x,y\}$ 中任何人的性別都相同，故M_k+1中諸位的性別必全相同。請指正這證明錯在那裡？
: 2.有人用下法證明任何兩個自然數都相等。令 $\mbox{max}\{ a,b\}$ 表示a與b之中較大者。對 $\mbox{max}\{ a,b\}$ 做數學歸納法，我們想證明a=b。若 $\mbox{max}\{ a,b\}=1$ 則1 $\leq$ a，b $\leq$ 1，故a=b。假設 $\mbox{max}\{ a,b\}$ =k，則a=b。考慮 $\mbox{max}\{ a,b\}$ =k+1的情形。今 $\mbox{max}\{ a-1,b-1\}$ = $\mbox{max}\{ a,b\}$ -1=k，故a-1=b-1，得a=b。請指出錯在那裡？

2.5 如何尋找答案？

同學可能會問：「現在我們已經學會數學歸納法。可是你如果不告訴我們1³+2³+…+n³的和是 $\frac{n^2(n+1)^2}{4}$ ，我們根本就求不出1³+2³+…+n³。你能不能告訴我們如何尋找答案？」

如何尋找答案？首先，你要先試驗幾個特殊例子；在這些特例尋找它們共同之處，試試看能不能歸納出一般的結論出來。同學可以參考 G. Polya，《How to solve it?》這是一本很值得看的課外讀物，有張憶壽的中文課本，長橋出版社出版。

我們在這一節，要介紹有系統的求和方法。

例題1

求 $S_n=1^2+2^2+\cdots +n^2$ 。

解法1

由 (k+1)³-k³=3k²+3k+1，得

$\begin{displaymath} \begin{array}{rrcl} &2^3-1^3&=&3\cdot 1^2+3\cdot 1+1 \\ &3^... ...1^2+2^2+\cdots +n^2) \\ &&&+3(1+2+\cdots +n)+n \\ \end{array}\end{displaymath}$

$\begin{displaymath} \begin{array}{rcl} \mbox{{\fontfamily{cwM1}\fontseries{m}\se... ...family{cwM0}\fontseries{m}\selectfont \char 1}} \\ \end{array}\end{displaymath}$

解法2

由「差和分理論」可知 S_n = an³ + bn² + cn + d，其中 a,b,c,d 是有理數。

現在只要求出 a,b,c,d 就可以。

$\begin{displaymath} \begin{array}{rcl} 1&=S_1=&a+b+c+d \\ 5&=S_2=&8a+4b+2c+d \\ 14&=S_3=&27a+9b+3c+d \\ 30&=S_4=&64a+16b+4c+d \\ \end{array}\end{displaymath}$

得 $a=\frac{1}{3}$ ， $b=\frac{1}{2}$ ， $c=\frac{1}{6}$ ，d=0。

討論：

1.在解法1中，也可以由公式 (k+1)³ -(k-1)³ = 6 k+2 求得。

2.解法2是所謂「未定係數法」，我們只要求出那些未知的係數 a,b,c,d 即可。

例題2

求 $S_n=1^3+2^3+\cdots +n^3$ 。

解法：

由 (k+1)⁴-(k-1)⁴=8k³+8k，得

$\begin{displaymath} \begin{array}{rrcl} &2^4-0&=&8\cdot 1^3+8\cdot 1 \\ &3^4-1^... ...4-1^4&=&8(1^3+2^3+\cdots +n^3)+8(1+2+\cdots +n) \\ \end{array}\end{displaymath}$

$\begin{displaymath} \begin{array}{rcl} \mbox{{\fontfamily{cwM1}\fontseries{m}\se... ...family{cwM0}\fontseries{m}\selectfont \char 1}} \\ \end{array}\end{displaymath}$

討論：

請用 S_n = an⁴ + bn³ + cn² + dn + e，求 a,b,c,d,e。

例題3

求 $S_n=1+2+4+8+\cdots +2^{n-1}$ 。

解法：

$\begin{displaymath} \begin{array}{rcl} 1+S_n&=&1+1+2+4+8+\cdots +2^{n-1} \\ &=&... ...&8+8+\cdots +2^{n-1} \\ &=&2^{n-1}+2^{n-1}=2^n \\ \end{array}\end{displaymath}$

故 S_n=2ⁿ-1。

討論：

S_n-2S_n=1-2ⁿ，同學能不能說明原因？

習題4

: 1.將循環小數0.317317317…化成分數。
: 2.求2+ $2\cdot 3$ + $2\cdot 3^2$ + $2\cdot 3^3$ +…+ $2\cdot 3^n$ 之和。
: 3.求 $1\cdot 2^2$ + $2\cdot 3^2$ + $3\cdot 4^2$ +…+(n-1)n²之和。（提示：一般項(k-1)k²=k³-k²。）
: 4.求 $1\cdot 2\cdot 3$ + $2\cdot 3\cdot 4$ +…+n(n+1)(n+2)之和。
: 5.求 $\frac{1}{1\cdot 2\cdot 3}$ + $\frac{1}{2\cdot 3\cdot 4}$ +…+ $\frac{1}{n(n+1)(n+2)}$ 之和。
: 6.求 $\cos\frac{\pi}{17}\cos\frac{2\pi}{17}\cos\frac{4\pi}{17}\cos\frac{8\pi}{17}$ 之值。（提示：考慮 $\sin\frac{\pi}{17}\cos\frac{\pi}{17}\cos\frac{2\pi}{17}\cos\frac{4\pi}{17}\cos\frac{8\pi}{17}$ 。）

2.6 不必用數學歸納法的例子

同學們做完了以上五節的例題與習題，會不會「歸納」出如下的口訣：「看到含有n的恆等式或不等式證明題，用數學歸納法」？

如果你這麼迷信數學歸納法，那麼請看以下的例子。你用數學歸納法證明，我用別的方法證明，我們比賽一下，比比看誰做的快，做的巧。

例題1

證明 $\frac{1}{\sqrt{1}} +\frac{1}{\sqrt{2}} +\cdots +\frac{1}{\sqrt{n}}\geq\sqrt{n}$ 。

證明：

用逆推法證明。

$\frac{1}{\sqrt{1}} +\frac{1}{\sqrt{2}} +\cdots +\frac{1}{\sqrt{n}}\geq\sqrt{n}$

$\Leftrightarrow$ $\frac{1}{\sqrt{n}}$ + $\frac{1}{\sqrt{2n}}$ + $\frac{1}{\sqrt{3n}}$ +…+ $\frac{1}{\sqrt{n(n-1)}}$ + $\frac{1}{\sqrt{n^2}}$ $\geq$ 1。

但是 $\frac{1}{\sqrt{n}}\geq\frac{1}{\sqrt{n^2}}$ ， $\frac{1}{\sqrt{2n}}\geq\frac{1}{\sqrt{n^2}}$ ， $\frac{1}{\sqrt{3n}}\geq\frac{1}{\sqrt{n^2}}$ ，…， $\frac{1}{\sqrt{n(n-1)}}\geq\frac{1}{\sqrt{n^2}}$

故 $\frac{1}{\sqrt{n}}$ + $\frac{1}{\sqrt{2n}}$ +…+ $\frac{1}{\sqrt{n(n-1)}}$ + $\frac{1}{\sqrt{n^2}}$ $\geq$ $\frac{n}{\sqrt{n^2}}$ =1。得證

例題2

試證 $n^n<(1\cdot 2\cdots n)^2<(\frac{n+1}{2})^{2n}$ ，其中 $n\geq 3$ 。

證明：

因為

$\begin{displaymath} \begin{array}{rcl} 1\cdot n&\geq&n \\ 2\cdot (n-1)&\geq&n \... ...-1)(n-k)\geq n \\ &\vdots& \\ n\cdot 1&\geq&n \\ \end{array}\end{displaymath}$

故得 $(1\cdot 2\cdots n)^2>n^n$

另一方面，因為

$\begin{eqnarray*} &&(\frac{n+1}{2} )^2-k(n-k+1)\\ &=&\{\frac{k+(n-k+1)}{2}\}^2-k(n-k+1)\\ &=&\{\frac{k-(n-k+1)}{2}\}^2 \geq 0 \end{eqnarray*}$

得

$\begin{displaymath} \begin{array}{rcl} 1\cdot n&\leq&(\frac{n+1}{2} )^2 \\ 2\cd... ... &\vdots& \\ n\cdot 1&\leq&(\frac{n+1}{2} )^2 \\ \end{array}\end{displaymath}$

故得 $(1\cdot 2\cdots n)^2<(\frac{n+1}{2} )^{2n}$

例題3

試證

$\begin{displaymath} \frac{1}{2\sqrt{n}} < \frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n} < \frac{1}{\sqrt{2n+1}} \end{displaymath}$

證明：

$\begin{eqnarray*} &&(\frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n} )^2\cdot (... ...t\frac{2n+1}{2n} )\\ &\leq&\frac{3}{4}\cdot 1\cdot 1\cdots 1 <1 \end{eqnarray*}$

故得

$\begin{displaymath}(\frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n} )^2\cdot (2n+1)<1\end{displaymath}$

得

$\begin{displaymath}\frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n} <\frac{1}{\sqrt{2n+1}}\end{displaymath}$

另一方面，

$\begin{eqnarray*} &&4n\cdot (\frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n} )^... ...ts(\frac{2n-1}{2n-2}\cdot\frac{2n-1}{2n})\\ &>&1\cdot1\cdots1=1 \end{eqnarray*}$

故得

$\begin{displaymath}4n\cdot (\frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n} )^2>1\end{displaymath}$

得

$\begin{displaymath}\frac{1}{2\sqrt{n}} <\frac{1}{2}\cdot\frac{3}{4}\cdots\frac{2n-1}{2n}\end{displaymath}$

例題4

試證

$\begin{displaymath} 2(\sqrt{n+1} -\sqrt{n}) < \frac{1}{\sqrt{n}} < 2(\sqrt{n}-\sqrt{n-1}) \end{displaymath}$

證明：

$\begin{eqnarray*} 2(\sqrt{n+1} -\sqrt{n} ) &=&\frac{2(\sqrt{n+1} -\sqrt{n} )(\sq... ...} +\sqrt{n-1}} >\frac{2}{\sqrt{n} +\sqrt{n}} =\frac{1}{\sqrt{n}} \end{eqnarray*}$

[討論：] 過份迷信數學歸納法的同學無論如何都應該用數學歸納法來解解這個題目。同學可以利用這個題目，證明 $[\sum_{n=1}^{10000}\frac{1}{\sqrt{n}} ]=198$ ，其中 Gauss 符號 [x] 表示正實數 x 的整數部分。

　1│2│3│4│5│6　


	（若有指正、疑問……，可以在此留言或寫信給我們。）

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有

編輯：陳文是

最後修改日期：4/30/2002