数学归纳法

所谓的数学归纳法是指，如果一个定理对于任意的正整数\(n\)都成立，那么我们只需要证明两点就可以了：

1. 该定理对\(n=1\)成立；
2. 如果该定理对\(n=k\)成立，那么对\(n=k+1\)也成立。

在读高中的时候，我就觉得这个数学归纳法太厉害了，遇到不会做的证明题，只要祭出这一大杀器就没有问题了。 当时还有一个疑问，为什么只需要证明这两点就可以了呢？

现在看来一个直观的解释就是，如果我们能够穷举出所有的正整数， 而且对于每一个正整数命题都成立，那么就证明了定理。 而实际上正整数的个数是无限多的，我们不可能穷举之。 我们把正整数集\(N_+\)划分为\(S\)和\(\bar{S}\)两个子集， 其中\(S=\left\{ x | 对于x命题成立 \right\}\)，\(\bar{S} = \left\{ x | 对于x命题不成立 \right\} \)， 而且\(N_+ = S \cup \bar{S} \)。我们只需要证明\(\phi = \bar{S}\)或者\(N_+ = S\)，即可。

对于数学归纳法中使待证命题成立的第一个条件，我们有\(1 \in S \)。 根据第二个条件，我们可以很容易证明\(2 \in S, 3 \in S, ..., k \in S \)。 我们得到了一个集合\(T = \left\{1, 2, ..., k \right\} = \left\{ y | y \in N_+, y <= k \right\} \)。 集合\(T\)是\(S\)的一个子集，即\(T \subset S\)。

对于集合\(U = \left\{z | z \in N_+, z > k \right\}\)，显然满足\(N_+ = T \cup U\)。 对于\(U\)中的每一个元素\(z\)，都可以根据第二个条件证明\(z \in S\)。 所以\(U\)也是S的一个子集。 那么我们就证明了\(T \cup U \subseteq S\)，即\(N_+ \subseteq S\)。 又因为\(S \subseteq N_+\)，所以\(N_+ = S\)。

因此，只要证明了数学归纳法的两个条件，我们就可以证明命题对任意正整数都成立。

============只是分割线而已===============

今天在知乎上看到了一个证明要简洁的多，记录如下：

1. 良序原理在自然数集上的一个推论说的是，自然数的非空子集有最小元
2. 假设在归纳法条件下，使得命题不成立的自然数集合是\(U\)
3. 如果\(U\)为空集，则证明毕
4. 若\(U\)不是空集，则\(U\)有最小元\(u\)，由条件\(u \neq 1\)，那么\(u-1\notin U\)那么\(u \notin U\)，导致矛盾。

============只是分割线而已===============

以下使用数学归纳法证明各个命题

【1】 \(1 + 2 + ... + n = \frac{n(n+1)}{2}\)

证：(1)当\(n = 1\)时，有\(1 = \frac{1 \times (1 + 1)}{2}\)，等式成立。

(2)假设\(n = k\)时等式也成立，则有\(1 + 2 + ... + k = \frac{k(k+1)}{2}\)。 那么，当\(n = k + 1\)时，有： $$ \begin{align} 1 + 2 + ... + k + (k+1) & = \frac{k(k+1)}{2} + (k+1) \\ & = (k+1)(\frac{k}{2} + 1) \\ & = (k+1)\frac{(k+1)+1}{2} \end{align} $$ 所以等式对于\(k+1\)亦成立。

由(1)(2)知等式对于任意\(n \in N_+\)都成立。口

【2】 \(1^2 + 2^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}\)

证：(1)当\(n=1\)时，有\(1^2 = \frac{1\times(1+1)\times(2+1)}{6}\)，等式成立。

(2)假设\(n=k\)时等式也成立，则有\(1^2 + 2^2 + ... + k^2 = \frac{k(k+1)(2k+1)}{6}\)。 那么，当\(n=k+1\)时，有： $$ \begin{align} 1^2 + 2^2 + ... + k^2 + (k+1)^2 & = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \\ & = (k+1)\frac{2k^2 + 7k + 6}{6} \\ \end{align} $$ 又因为\([(k+1)+1][2(k+1)+1] = 2k^2 + 7k + 6\)，所以: $$ 1^2 + 2^2 + ... + k^2 + (k+1)^2 = \frac{(k+1)[(k+1)+1][2(k+1)+1]}{6} $$ 等式对于\(k+1\)亦成立。

由(1)(2)知等式对于任意\(n \in N_+\)都成立。口

【3】\(1^3 + 2^3 + ... + n^3 = (1 + 2 + ... + n)^2\)

证：(1)当\(n=1\)时，有\(1^3 = (1)^2\)，等式成立。

(2)假设\(n=k\)时等式也成立，则有： $$ \begin{align} 1^3 + 2^3 + ... + k^3 & = (1 + 2 + ... + k)^2 \\ & = \left[\frac{k(k+1)}{2} \right]^2 \end{align} $$ 那么，当\(n=k+1\)时，有： $$ \begin{align} 1^3 + 2^3 + ... + k^3 + (k+1)^3 & = \left[\frac{k(k+1)}{2} \right]^2 + (k+1)^3 \\ & = (k+1)^2\left[\frac{k^2}{4} + k + 1 \right] \\ & = \frac{(k+1)^2(k+2)^2}{4} \\ & = [1 + 2 + ... + k + (k+1)]^2 \end{align} $$ 所以等式对于\(k+1\)亦成立。

由(1)(2)知等式对于任意\(n \in N_+\)都成立。口

【4】\(1 + 2 + 2^2 + ... + 2^{n-1} = 2^n -1\)

证：(1)当\(n=1\)时，有\(1 = 2^1 - 1\)，等式成立。

(2)假设\(n=k\)时等式也成立，则有\(1 + 2 + 2^2 + ... + 2^{k-1} = 2^k - 1\) 那么，当\(n=k+1\)时，有： $$ \begin{align} 1 + 2 + 2^2 + ... + 2^{k-1} + 2^k & = 2^k - 1 + 2^k \\ & = 2^{k+1} - 1 \end{align} $$ 所以等式对于\(k+1\)亦成立。

由(1)(2)知等式对于任意\(n \in N_+\)都成立。口

【5】设\(a^{[n]} = a(a-h)...[a-(n-1)h]\)及\(a^{[0]} = 1\)，求证： $$ (a+b)^{[n]} = \sum_{m=0}^n C_n^m a^{[n-m]}b^{[m]} $$ 其中\(C_n^m\)是由\(n\)个元素中选取\(m\)个元素的组合数，由此推出牛顿二项式公式。

证：(1)当\(n=1\)时，有： $$ \begin{align} (a+b)^{[1]} = a+b \\ C_1^0a^{[1]}b^{[0]} + C_1^1a^{[0]}b^{[1]} = a+b \end{align} $$ 所以，等式对于\(n=1\)成立。

(2)假设当\(n=k\)时，等式成立，则有\((a+b)^{[k]}=\sum_{m=0}^k C_k^m a^{[k-m]}b^{[m]} \) 那么，当\(n=k+1\)时，有： $$ \begin{align} (a+b)^{[n+1]} & = (a+b)(a+b-h)...[(a+b)-(n-1)h][(a+b)-nh] \\ & = (a+b)^{[n]}[(a+b)-nh] \\ & = [(a+b)-nh]\sum_{m=0}^k C_k^m a^{[k-m]}b^{[m]} \\ & = C_k^0a^{[k]}b^{[0]}(a-nh + b) + C_k^1a^{[k-1]}b^{[1]}[a-(n-1)h + b - h] + ... + C_k^ka^{[0]}b^{[k]}(a + b -nh) \\ & = C_k^0a^{[k+1]}b^{[0]} + C_k^0a^{[k]}b^{[1]} + C_k^1a^{[k]}b^{[1]} + C_k^1a^{[k-1]}b^{[2]} + ... + C_k^ka^{[1]}b^{[k]} + C_k^ka^{[0]}b^{[k+1]} \\ & = C_{k+1}^0a^{[k+1]}b^{[0]} + C_{k+1}^1a^{[k]}b^{[1]} + ... + C_{k+1}^ka^{[1]}b^{[k]} + C_{k+1}^{k+1}a^{[0]}b^{[k+1]} \\ & = \sum_{m=0}^{k+1} C_{k+1}^m a^{[k+1-m]}b^{[m]} \end{align} $$ 所以等式对于\(k+1\)亦成立。

由(1)(2)知等式对于任意\(n \in N_+\)都成立。

当\(h=0\)时，有\(a^{[n]}=a^n\)，所以牛顿二项式公式\((a+b)^n=C_n^ma^{n-m}b^m\)成立。口

【6】证明伯努利不等式： $$ (1+x_1)(1+x_2)...(1+x_n) ≥ 1 + x_1 + x_2 + ... + x_n $$ 式中\(x_1, x_2,...,x_k\)是符号相同且大于-1的数。

证：(1)当\(n=1\)时，有\((1 + x_1) ≥ 1 + x_1\)，不等式成立。

(2)假设\(n=k\)时不等式也成立，则有\((1+x_1)(1+x_2)...(1+x_k) ≥ 1 + x_1 + x_2 + ... + x_k\) 那么，当\(n=k+1\)时，有： $$ \begin{align} (1+x_1)(1+x_2)...(1+x_k)(1+x_{k+1}) & ≥ (1 + x_1 + x_2 + ... + x_k)(1+x_{k+1}) \\ & = 1 + x_1 + x_2 + x_k + x_{k+1} + x_{k+1}(x_1 + x_2 + ... + x_k) \\ & ≥ 1 + x_1 + x_2 + x_k + x_{k+1} \end{align} $$ 所以不等式对于\(k+1\)亦成立。

由(1)(2)知不等式对于任意\(n \in N_+\)都成立。口

【7】证明：若\(x>-1\)，则不等式\( (1+x)^n ≥ 1 + nx (n>1) \)为真，且仅当\(x=0\)时，等号成立。

证：对【6】中的伯努利不等式进行扩展，令： $$ x_1 = x_2 = ... = x_n = x $$ 得到 \((1 + x)^n ≥ 1 + nx\)，对于\(x>-1，n \in N_+, n>1\)成立。口

【8】证明不等式：\(n! < \left(\frac{n+1}{2} \right)^n, n > 1 \)

证：(1)当\(n=2\)时，有\(2! < \frac{3}{2}^2\)，不等式成立。

(2)假设\(n=k\)时不等式也成立，则有\(k! < \left(\frac{k+1}{2} \right)^k\) 那么，当\(n=k+1\)时，有： $$ k!(k+1) < (k+1)\left(\frac{k+1}{2} \right)^k $$ 又因为不等式： $$ \begin{align} \frac{(k+2)^{k+1}}{2^{k+1}}\frac{2^k}{(k+1)^{k+1}} & = \frac{1}{2}\left[1 + \left(\frac{1}{k+1}\right)^{k+1}\right] \\ & > \frac{1}{2}\left[1+\left(k+1\right)\frac{1}{k+1}\right] \\ & = 1 \end{align} $$ 所以不等式对于\(k+1\)亦成立。

由(1)(2)知不等式对于任意\(n \in N_+, n>1\)都成立。口

【9】证明不等式：\(2! \cdot 4! ...(2n)! > \left[(n+1)!\right]^n, n>1\)

证：（1）当\(n=2\)时，有： $$ \begin{align} 2! \cdot 4! = 48 \\ \left[(2+1)!\right]^2 = 36 \end{align} $$ 所以，不等式对于\(n=2\)成立。

(2)假设当\(n=k\)时，不等式成立，则有\(2! \cdot 4! ...(2k)! > \left[(k+1)!\right]^k \) 那么，当\(n=k+1\)时，有： $$ \begin{align} 2! \cdot 4! ...(2k)![2(k+1)]! & > [2(k+1)]!\left[(k+1)!\right]^k \\ & = (2k+2)(2k+1)...(k+2)\left[(k+1)!\right]^{k+1} \\ & > (k+2)^{k+1}\left[(k+1)!\right]^{k+1} \\ & = \left[[(k+1)+1]!\right]^{k+1} \end{align} $$ 所以不等式对于\(k+1\)亦成立。

由(1)(2)知不等式对于任意\(n \in N_+, n>1\)都成立。

【10】证明不等式：\(\frac{1}{2} \cdot \frac{3}{4} ... \frac{2n-1}{2n} < \frac{1}{\sqrt{2n+1}}\)

证：（1）当\(n=1\)时，有\(\frac{1}{2} < \frac{1}{\sqrt{3}}\)，不等式对于\(n=1\)成立。

(2)假设当\(n=k\)时，不等式成立，则有\(\frac{1}{2} \cdot \frac{3}{4} ... \frac{2k-1}{2k} < \frac{1}{\sqrt{2k+1}} \) 那么，当\(n=k+1\)时，有： $$ \begin{align} \frac{1}{2} \cdot \frac{3}{4} ... \frac{2k-1}{2k}\cdot\frac{2k+1}{2k+2} & < \frac{2k+1}{2k+2}\cdot\frac{1}{\sqrt{2k+1}} \\ & = \frac{\sqrt{2k+1}}{2k+2} \\ & < \frac{\sqrt{2k+2}}{2k+2} \\ & = \frac{1}{\sqrt{2k+2}} \end{align} $$ 所以不等式对于\(k+1\)亦成立。

由(1)(2)知不等式对于任意\(n \in N_+\)都成立。