線性代數/證明技巧

歸納法

許多證明是迭代的，"這是為什麼這個陳述對於數字 $1$ 是正確的，然後它對於 $2$ 也是正確的，然後從那裡推斷到 $3$，等等..."。這些被稱為歸納法證明。這樣的證明有兩個步驟。 在基本步驟中，命題對於某個第一個數字被證明是正確的，通常是 $0$ 或 $1$。 然後在歸納步驟中，我們假設命題對於小於某個 $k$ 的所有數字都是正確的，並推匯出它對於下一個數字 $k+1$ 也是正確的。

以下是一個例子。

我們將證明 $1+2+3+\dots +n=n(n+1)/2$.

對於基本步驟，我們必須證明當 $n=1$ 時，公式成立。這很簡單，前 $1$ 個數字的和確實等於 $1(1+1)/2$.

對於歸納步驟，假設公式對於數字 $1,2,\ldots ,k$ 成立。也就是說，假設這些公式的所有例項都成立。

${\begin{array}{rl}1&=1(1+1)/2\\{\text{and}}\quad 1+2&=2(2+1)/2\\{\text{and}}\quad 1+2+3&=3(3+1)/2\\&\vdots \\{\text{and}}\quad 1+\dots +k&=k(k+1)/2\end{array}}$

從這個假設，我們將推斷出該公式也適用於$k+1$下一個情況。推導過程是簡單的代數運算。

$1+2+\cdots +k+(k+1)={\frac {k(k+1)}{2}}+(k+1)={\frac {(k+1)(k+2)}{2}}$

我們在基本情況下已經證明了上述命題對$1$成立。我們在歸納步驟中已經證明了如果它對$1$成立，那麼它也對$2$成立；因此它對$2$成立。我們還在歸納步驟中已經證明了如果該語句對$1$和$2$成立，那麼它也對下一個情況$3$成立，等等。因此它對任何大於或等於$1$的自然數成立。

這裡還有另一個例子。

我們將證明每個大於$1$的整數都是質數的乘積。

基本步驟很容易：$2$是一個單一質數的乘積。

對於歸納步驟，假設$2,3,\ldots ,k$中的每一個都是質數的乘積，旨在證明$k+1$也是質數的乘積。有兩種可能性：（i）如果$k+1$不能被比它小的數整除，那麼它是一個質數，因此也是質數的乘積；（ii）如果$k+1$可以被整除，那麼它的因子可以寫成質數的乘積（根據歸納假設），因此$k+1$可以重新寫成質數的乘積。這就是證明的結束。

(備註。數論中的素因數分解定理指出，不僅存在分解，而且分解是唯一的。我們已經證明了容易的部分。）

在歸納論證中，關於“下一個數字”需要注意兩點。

一方面，雖然歸納適用於整數，但它不適用於實數。實數沒有“下一個”。

另一方面，我們有時會使用歸納法來降序，例如，從 $10$ 到 $9$ 到 $8$，等等，一直降到 $0$。所以“下一個數字”可能意味著“下一個最小的數字”。當然，最後我們並沒有證明所有自然數的情況，而只是證明了小於或等於 $10$ 的數字。

反證法

另一種證明方法是透過證明某件事不可能是錯誤的來證明它是正確的。

經典的例子是歐幾里得的證明，即存在無限多個素數。

假設只有有限多個素數 $p_{1},\dots ,p_{k}$。考慮 $p_{1}\cdot p_{2}\dots p_{k}+1$。在這個假設的完整列表中，沒有一個素數能被這個數字整除，每個素數都餘 $1$。但每個數字都是素數的乘積，因此這種情況不可能發生。因此，不可能只有有限多個素數。

每一個反證法都有相同的形式：假設錯誤命題是正確的，並推匯出一些與已知事實矛盾的結果。這種邏輯被稱為亞里士多德邏輯或項邏輯。

另一個例子是證明 ${\sqrt {2}}$ 不是有理數的證明。

假設 ${\sqrt {2}}=m/n$。

$2n^{2}=m^{2}$

提取 $2$：$n=2^{k_{n}}\cdot {\hat {n}}$ 以及 $m=2^{k_{m}}\cdot {\hat {m}}$ 並重新寫。

$2\cdot (2^{k_{n}}\cdot {\hat {n}})^{2}=(2^{k_{m}}\cdot {\hat {m}})^{2}$

素因數分解定理指出，$2$ 的因數個數在等式兩邊必須相同，但左邊有奇數個 $1+2k_{n}$，而右邊有偶數個 $2k_{m}$。這是一個矛盾，因此一個有 $2$ 平方的有理數是不存在的。

這兩個例子都是為了證明某些東西不存在。否定命題通常暗示著反證法。