Apostol Linear Algebra Exercise 0.13.3

問題

令$A(n)$表示命題$\displaystyle \sum_{r = 1}^{n} r = \frac{(2n + 1)^2}{8}$。

(a) 證明對整數$k \geq 1$，由$A(k)$可得$A(k + 1)$。

(b) 試說明為什麼命題「由歸納法可知對所有$n \geq 1$，$A(n)$為真」不成立。

(c) 將$A(n)$中的等號改為一個不等號，使得對所有$n \geq 1$，$A(n)$都為真。

解答

(a) 假定命題$A(k)$正確，亦即有
$$\sum_{r = 1}^{k} r = \frac{(2k + 1)^2}{8}.$$
那麼
\begin{align}
\sum_{r = 1}^{k + 1} r
&= \sum_{r = 1}^{k} r + (k + 1) \notag \\
&= \frac{(2k + 1)^2}{8} + k + 1 \quad [\text{假設}] \notag \\
&= \frac{4k^2 + 4k + 1}{8} + \frac{8k + 8}{8} \notag \\
&= \frac{4k^2 + 12k + 9}{8} \notag \\
&= \frac{(2k+3)^2}{8} \notag \\
&= \frac{[2(k + 1) + 1]^2}{8} \notag
\end{align}
於是命題$A(k + 1)$成立。

(b) 對於$n = 1$，$\displaystyle \sum_{r = 1}^{1} r = 1 < \frac{9}{8} = \frac{(2 \cdot 1 + 1)^2}{8}$，所以$A(1)$不成立，因此無法由歸納法證明對所有$n \geq 1$，$A(n)$為真。

(c) 由(b)的計算，應該將命題$A(n)$修改為
$$\sum_{r = 1}^{n} r < \frac{(2n + 1)^2}{8}.$$

以下用歸納法證明修改後的命題$A(n)$對所有整數$n \geq 1$成立。

$n = 1$時，見(b)之計算，可知命題成立。

設命題在$n - 1$時成立，即有
$$\sum_{r = 1}^{n - 1} r < \frac{[2(n - 1) + 1]^2}{8}.$$

$n$時，
\begin{align}
\sum_{r = 1}^{n} r
&= \sum_{r = 1}^{n - 1} r + n \notag \\
&< \frac{[2(n - 1) + 1]^2}{8} + n \quad [\text{歸納假設}] \notag \\
&= \frac{4n^2 - 4n + 1}{8} + \frac{8n}{8} \notag \\
&= \frac{4n^2 + 4n + 1}{8} \notag \\
&= \frac{(2n + 1)^2}{8} \notag
\end{align}
故由數學歸納法得證。