02 One Step at a Time. The Method of Mathematical Induction

Weak Induction

如果能完整一下两步，则能证明给定命定对于所有的自然数$m$都成立。
(1) 初始步骤。证明对于$m$取最小值时（通常为0或1）命题时成立的。
(2) 归纳步骤。从归纳假设$m$取$n$时命题成立，证明取$n+1$时也成立。

Example 2.1. 对于所有正整数$n$有 $$1^2+2^2+\cdots+m^2=\frac{m(m+1)(2m+1)}{6}$$
Solution. 略。

Example 2.2. $m$条线最多把平面分成$f(m)$个区域。对于所有正整数$m$有$f(m)=\frac{m(m+1)}{2}+1$。
Solution. 显然，一条直线能分成两个部分，两条直线能分成四个部分，三条直线最多可分成七个部分。
假设对于$n$条直线，命题成立。我们添加第$n+1$条直线$s$，和直线$t_1,t_2,\cdots,t_k$相交，$k\leq n$。直线$s$经过$k+1$个区域，所以新增了$k+1$个区域，$k+1\leq n+1$。所以$f(n+1)\leq f(n)+n+1$。当且仅当直线$s$穿过之前的$n$条直线，等号成立。 $$f(n+1)=f(n)+n+1=\frac{n(n+1)}{2}+1+n+1=\frac{(n+1)(n+2)}{2}+1$$

Example 2.3. 假设$a_1=1$；$a_{n+1}=3a_n+1$，其中$n\geq 1$。求$a_n$的通项公式。
Solution. 数列前几项是$1, 4, 13, 40, 121$，可以归纳得出通向公式为$a_m=(3^m-1)/2$。当$m=1$时，显然成立。假设当$m=n$成立，那么 $$a_{n+1}=3a_n+1=3(\frac{3^n-1}{2})+1=\frac{3^{n+1}-1}{2}$$ 证毕。

上面例子中$a_{n+1}=3a_n+1$称之为递推关系(recurrence relation)。$a_{n+1}=\frac{3^n-1}{2}$称之为显式公式(explicit formula)，也被称为解析式(closed formula)。

Theorem 2.4. 对所有正整数$n$，$[n]$的子集个数是$2^n$。
Proof $n=1$时，$[1]$的子集有两个：$\emptyset$和${1}$。
假设取$n$时成立，我们现在证明$n+1$也是成立的。我们可以把$[n+1]$的子集分成两类：包含$n+1$的和不包含$n+1$。对于不包含$n+1$的，就是$[n]$的子集，有$2^n$个。包含$n+1$的，这些子集是由$n+1$和$[n]$某个子集组成的，所以也有$2^n$个。所以共有$2^{n+1}$个子集。证毕。

我们特别要警惕使用数学归纳法时的陷阱，特别时初始步骤。
我们试着证明一个明显错误的例子：所有的马都是一个颜色的。换成数学语言：对于任意正整数$n$，任意$n$匹马有相同的颜色。$n=1$时，任意一匹马显然有相同的颜色。假设任意$n$匹马有相同的颜色，我们现在递推至$n+1$，根据前提假设，前$n$匹马有相同颜色，比如黑色，后$n$匹马也有相同颜色，也只能时黑色，所有$n+1$匹都是一个颜色，黑色。
这个证明哪里有问题呢？在于从1到2时有错误的地方。对于$n=2$，前 $n$匹马就是第一匹马，后$n$匹马就是第二匹马，或者最后一匹马。这两个集合是没有交集的，这两匹马没有必要是同一种颜色。

Strong Induction

Example 2.5. 数列${a_n}$，其$a_0=0$，$n\geq 0$时，$a_{n+1}=a_0+a_1+\cdots+a_n+n+1$。求证对于正整数$n$，$a_n=2^n-1$。
这里$a_{n+1}$不仅依赖于$a_n$，还依赖于$a_{n-1},a_{n-2},\ldots,a_1$，不能应用上一小节所讲的归纳法的。

强归纳法(strong induction)就是来解决这个问题的。和上一节归纳法不同的是，这里的归纳假设是命题对于所有小于等于$n$整数都是成立的，然后推导出$n+1$时也成立。强归纳要注意初始步骤，因为有时递归推导需要多个初始值。

Solution. $a_0=0$，所以初始条件成立。假设对于小于等于正整数$n$的数，公式都成立。 $$\begin{aligned} a_{n+1}&=a_0+a_1+\cdots+a_n+n+1\\ &=(2^0-1)+(2^1-1)+\cdots+(2^n-1)+n+1\\ &=1+2+4+\cdots+2^n\\ &=2^{n+1}-1 \end{aligned}$$

Example 2.6. $f(0)=1,f(1)=2$，当$n\geq 1$时，$f(n+1)=f(n-1)+2f(n)$。求证$f(n)\leq 3^n,n\in N$。
Solution. 当$n=0,n=1$时，显然成立。假设对于小于等于$n$的整数都成立，那么$n+1$时， $$\begin{aligned} f(n+1)&=f(n-1)+2f(n)\\ &\leq 3^{n-1}+2\cdot 3^n\\ &=7\cdot 3^{n-1}\\ &<9\cdot 3^{n-1}\\ &=3^{n+1} \end{aligned}$$

Exercises

(15) 用数学归纳法证明几何平均数和算术平均数满足下式： $$\sqrt[n]{a_1a_2\cdots a_n}\leq\frac{a_1+a_2+\cdots+a_n}{n}$$ 其中$a_1,a_2,\cdots,a_n$是非负数。
Solution. $n=1$时，等式左右两边均为$a_1$，显然成立。
假设$n$时成立，现在证明$n+1$的时候。
不妨设$a_n$最大，令 $$C=\frac{a_1+a_2+\cdots+a_{n-1}}{n-1}$$ 那么 $$\sqrt[n-1]{a_1a_2\cdots a_{n-1}}\leq C$$ 所以 $$C^{n-1}\geq a_1a_2\cdots a_{n-1}$$ 我们要证明 $$\sqrt[n]{C^{n-1}a_n}\leq \frac{(n-1)C+a_n}{n}$$ 这个命题要比原命题更加严格。
由于$a_n>C$，那么右边这个算数平均值在$C$和$a_n$中间，不妨设和$C$的差值是$d$，那么和$a_n$的差值就是$(n-1)d$。
左边有$n-1$个$C$相乘，右边有$n-1$个$C$相加，我们迭代$n-1$次，每次将$C$变大为$C+d$，$a_n$减少为$a_n-d$，那么右边不变；由于$Ca_n\leq (C+d)(a_n-d)$，那么左边再变大（至少没有变小）。所以命题变得越来越严格
$n-1$次迭代之后，左边和右边相等，均为$C+d$。所以命题成立。

(15) 令$a_1=5,a_{n+1}=a_n^2$。求证$a_n$和$a_{n+1}$的后$n$个数字相同。
Solution.

这个题我思考了一段时间，没有做出来，Google一下从Mathematics社区找到了答案，我个人觉得robjohn的解答更容易理解。

很容易推得通项公式是 $$a_{n+1}=5^{2^n}$$ 要求证的命题等价于 $$5^{2^{n-1}}\equiv 5^{2^n} \text{ mod }10^n$$ $$10^n|5^{2^n}-5^{2^{n-1}}=5^{2^{n-1}}(5^{2^{n-1}}-1)$$ 显然 $$5^n|5^{2^{n-1}}$$ $$\begin{aligned} 5^{2^{n-1}}-1&=(5^{2^{n-2}}+1)(5^{2^{n-2}}-1)\\ &=(5^{2^{n-2}}+1)(5^{2^{n-3}}+1)(5^{2^{n-3}}-1)\\ &\vdots\\ &=(5^{2^{n-2}}+1)(5^{2^{n-3}}+1)\cdots(5^{2^0}+1)(5^{2^0}-1) \end{aligned}$$ 上式共有$n$项，所以 $$2^n|5^{2^{n-1}}-1$$ 所以 $$10^n|5^{2^n}-5^{2^{n-1}}$$