线性代数/证明技巧

归纳法

许多证明是迭代的，"这是为什么这个陈述对于数字 $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$ 平方的有理数是不存在的。

这两个例子都是为了证明某些东西不存在。否定命题通常暗示着反证法。