证明下述线性方程有非0解：
\begin{equation}
x_1 + x_2 =0.\tag{A.1}
\end{equation}
附录 A 数学证明简介
上面的一段话引用自麻省理工学院教授 Michael Sipser 的专著《Introduction to the Theory of Computation》。这一句话是这本专著第0章第3节的开篇第一句话。我们这一部分也主要借鉴这本书的内容。
大学数学与高中数学有很大不同。大学数学中，定义是精神所在，定理与证明是核心和灵魂。大学数学的学习应该围绕着这三者展开。
数学中有很多术语，定义 就是这些术语含意的精确和清晰描述。应用这些术语可以简洁而准确地划定讨论问题的范围。
有了定义之后，关于所定义的数学术语会有一些数学命题。所谓的数学命题，是表述严密、没有歧义的一句或多句学术语句，一般表现为具有前提范围，提出条件继而得出结论的形式，是一个判断性语句。这样的判断性语句可对可错。
从已知条件出发，经过严密的逻辑推导，说明一个命题正确的过程称为证明。经过证明，并具有一定重要性的正确命题称为 定理。证明定理的已知条件一般是公理或其它已经经过证明的命题。
确定数学命题结论正确性的唯一方法就是给出证明，不幸的是发现证明往往困难且需要耐心。发现证明的能力是数学能力的精髓所在。为了帮助寻找证明，《Introduction to the Theory of Computation》这本书中给出了如下一些技巧：
- 仔细阅读命题的条件和结论。确认自己理解命题中出现的所有记号和概念，尝试用自己的语言重新叙述命题。
-
尝试分解问题。一种常见的命题类型是充分必要型（等价型）命题，即形如 “命题P成立的充分必要条件是命题Q成立”。此种形式的命题也常被表述为：“P的充分必要条件是Q”、“P当且仅当Q”、“P与Q等价”等；用数学记号表示，上述命题也可记为“P \(\Leftrightarrow\) Q”。充分必要条件也可简记为充要条件。例如命题“设\(n\in \N\)。 \(n\)是偶数的充分必要条件是 \(n\)的个位数是偶数。”。我们称这个具体的命题为命题S。S中的命题P是“\(n\)是偶数”，命题Q是“\(n\)的个位数是偶数”。“\(n\in \N\)”是整个命题的前提条件，即P和Q都要遵守的条件。在有了“\(n\in \N\)”这个前提后，命题S可以被等价的表述为：“\(n\)是偶数的充要条件是\(n\)的个位数是偶数”、“\(n\)是偶数等价于\(n\)的个位数是偶数”、“\(n\)是偶数\(\Leftrightarrow\)\(n\)的个位数是偶数”等。遇到充分必要型命题时，最常用的分解问题的方式是将证明分解为充分性证明和必要性证明，即分解为“若Q成立，则P成立”（Q\(\Rightarrow\)P ）和“若P成立，则Q成立”(P\(\Rightarrow\)Q)。这样分解后通常会降低证明的逻辑难度。另一种常见的可分解命题是“\(A=B\)”型命题。这种类型命题又可以进一步区分为以下两种情况。
- \(A,B\)表示实数。此时命题“\(A=B\)”的证明通常可以分解为“\(A\le B\)”和“\(A\ge B\)”两步来完成。
- \(A,B\)表示集合。此时命题“\(A=B\)”的证明通常分解为“\(A\subseteq B\)”和“\(B \subseteq A\)”两步来完成，即证明“任取 \(x\in A\)，可推出\(x\in B\)”及 “任取 \(x\in B\)，可推出\(x\in A\)”。通过上面的分解，我们可以将对集合整体讨论转化为对集合中元素的单一讨论，更容易获得证明。
- 获得对命题的直观感觉。有意义的命题通常阐述的是多个对象所共有的性质。为了获得对命题成立的直观感觉，可以通过观察其中几个具体的特例来加深理解；如果这样还不够，可以通过尝试构造反例的方式来理解命题成立的原因。有时，尝试构造反例会有意想不到的效果。
当相信自己已经发现了证明方法时，你需要用恰当的方式把证明记录下来。一个好证明应该由一系列的论断构成，论断中间包含着从前面已经说明的论断推导出后续论断成立的简单推理。仔细书写证明很重要，一方面是为了让读者可以读懂其中的逻辑；另一方面也是可以让自己确信证明过程没有错误。
下面是寻找证明过程中一些有用的提示。
- 要有耐心。发现证明需要耐心。在课本里的证明通常都是一些先贤通过长时间总结而发现的。即便是对经过长期训练的专业研究人员，也可能需要几周甚至几年才能获得一个证明。
- 经常回顾。仔细阅读并记住要证明的问题，把问题放在大脑中思考一下，如果短时间没有结果就先放一下去做别的事情，过一段时间再来思考一下。让你的潜意识和直觉有机会帮你解决问题。
- 保持整洁、有序。整洁、有序的书写和图形以及周边环境会让我们中的多数人容易平静且心情舒畅，这样的状态更容易发现证明。
- 保持简明扼要。简洁有助于您表达高层次的想法，而不会迷失在细节中。优秀的数学符号对于简洁地表达想法很有帮助。但是在写证明时一定要包括足够的推理细节，这样读者就可以轻松理解您想说什么。
典型的证明方法有：
-
构造性证明：多适用于存在性命题，即一个命题声称某种结构的存在性。证明此类存在性命题，一个直接的方法就是把相应的结构构造出来。数学分析中按定义证明极限很多是采用构造性证明。
例 A.0.1.
- 反证法：假设要证明的结论不成立，根据这个假设去做推理，最终推出矛盾，于是可以推得假设不成立，即原命题成立。
例 A.0.2.
证明\(\sqrt{2}\)不是有理数。
解答.
假设结论不成立，即存在互素的两个整数\(p,q\)，使得
\begin{equation*}
\sqrt{2}= \frac{q}{p}.
\end{equation*}
等式两端平方并同时乘以\(p^2\)得
\begin{equation}
2p^2=q^2,\tag{A.2}
\end{equation}
\begin{equation*}
p^2=2k^2
\end{equation*}
同理可知\(p\)也是偶数。这样\(p,q\)至少有一个公因子2，与\(p,q\)互素矛盾，假设不成立，即\(\sqrt{2}\)不是有理数。
- 数学归纳法：通常用来证明与自然数集相关的命题\(\mathcal{P}(n)\)。数学归纳法一般包含两个步骤：
- 验证初始命题\(\mathcal{P}(0)\)；
- 对任意\(k\in \N\)， 假设\(\mathcal{P}(k)\)成立，以此为已知条件推出\(\mathcal{P}(k+1)\)成立。
数学归纳法是一种相对高级的证明工具，也是一种非常有力的工具，是数学证明中最常使用的一种证明方法。
数学归纳法的基本逻辑是：首先在第1步中验证\(\mathcal{P}(0)\)的正确性；当\(\mathcal{P}(0)\)的正确性得到确认后，在第2步中取 \(k=0\)，根据第2步，确认\(\mathcal{P}(1)\)的正确性; \(\mathcal{P}(1)\)的正确性确认后，仍回到第2步，取\(k=1\)来确认\(\mathcal{P}(2)\)的正确性；再根据\(\mathcal{P}(2)\)的正确性利用第2步确认\(\mathcal{P}(3)\)的正确性。如此循环往复，可以断定所有\(\mathcal{P}(n)\)的正确性。
我们举几个具体的例子来熟悉数学归纳法的证明过程。
例 A.0.3.
数列\((a_n)_{n=0}^{\infty}\)是首项\(a_0=1\)，公比\(q\ne 1\)的等比数列，即\(a_n = q^n,n =0,1,2,\ldots\)。记\(s_n = \sum_{i=0}^n a_i\)。证明:
\begin{equation*}
s_n = \frac{1-q^{n+1}}{1-q},\ n=0,1,\ldots .
\end{equation*}
解答.
容易验证
\begin{equation*}
s_0=a_0=1= \frac{1-q}{1-q}.
\end{equation*}
即当\(n=0\)时命题成立。
假设\(n=k\)时命题成立，即
\begin{equation*}
s_k = \frac{1-q^{k+1}}{1-q}.
\end{equation*}
于是
\begin{equation*}
s_{k+1}=s_k+a_k= \frac{1-q^{k+1}}{1-q}+q^{k+1}=\frac{1-q^{k+2}}{1-q},
\end{equation*}
即当\(n=k+1\)命题也成立。
根据归纳法，结论对所有的 \(n\in \N\) 均成立。
关于数学归纳法，我们有几点说明。
- 数学归纳法的第一步也称为验证初始条件。有些数学命题\(\mathcal{P}(n)\)中的\(n\)不一定从0开始，可以从任何一个整数\(a\) 开始，此时证明的结论为：对任意的\(n\ge a\)，\(\mathcal{P}(n)\)都成立。
- 数学归纳法的第二步称为归纳证明。其中对\(\mathcal{P}(k)\)正确性的假设也称为归纳假设。有些用归纳法思想的证明中，归纳假设可能不止假设一步，此时初始条件的验证也要做相应调整。
- 归纳证明中\(k\)的任意性特别需要留意，否则可能产生一些似是而非的证明。请参考下面的例子。
例 A.0.4. 似是而非的数学归纳法证明.
请分析下面的归纳法证明是否正确。如果错误，请分析错误的原因。
命题 A.0.5.
世界上所有的马都是同一种颜色。
证明.
此命题等价于要证明：对任意\(n\in \N\)， 任意\(n\)匹马的颜色都相同。下面尝试用归纳法证明此命题。
当 \(n=1\)时，命题显然成立。
假设\(n=k\)时命题成立，即任意 \(k\)匹马颜色相同。用\(h_1,h_2,\ldots,h_{k+1}\)表示任给的\(k+1\)匹马，\(c(h_i)\)表示第\(i\)匹马\(h_i\)的颜色 。根据归纳假设，\(h_1,h_2,\ldots,h_k\)这\(k\)匹马有相同的颜色，即
\begin{equation*}
c(h_1)=c(h_2)=\cdots=c(h_k).
\end{equation*}
同理，\(h_2,h_3,\ldots,h_{k+1}\)这\(k\)匹马也有相同的颜色，即
\begin{equation*}
c(h_2)=c(h_3)=\cdots=c(h_{k+1}).
\end{equation*}
于是
\begin{equation*}
c(h_1)=c(h_2)=\cdots=c(h_k)=c(h_{k+1}),
\end{equation*}
即\(k+1\)匹马颜色也相同，命题得证。
