数学归纳法

第一数学归纳法

概念

$\quad \quad 设\,{\color{Black}P(n)}\,是一个含有正整数n的命题，如果\\ \,\,\quad \quad \quad (1)\,当\,n=a\,时，P(a)成立；\\\,\,\quad \quad \quad(2)\,\,由\,P(k)\,成立必可推得\,P(k+1)\,成立，\\ \quad \quad 那么\,P(n)\,对所有正整数\,n \ge a\,都成立。$

例题

例题1-1

$\quad \quad 证明：n边形(n \ge 3)内角和为 (n-2) * \pi$

例题1-2

$\ge 8\,的正整数均能表示为若干个\,3\,和\,5\,的和。$
$证：\\ \quad \quad当\,n=8\,时，有\,8=3+5\,，命题显然成立。\\ \quad \quad假设当\,n=k(k是正整数且k \ge 8)时命题成立\,，即是下面三种情况之一：\\ \quad \quad \quad \quad (1)\,存在正整数a,b，使得\,k=3a+5b\,; \\ \quad \quad \quad \quad (2)\,存在正整数a \ge 3，使得 k=3a; \\ \quad \quad \quad \quad (3)\,存在正整数b \ge 2，使得k=5b。\\ \quad \quad由：\\ \quad \quad \quad \quad如果是情况(1)，则\, k+1 = 3(a+2)+5(b-1) \\ \quad \quad \quad \quad 如果是情况(2)，则\,k+1=3(a-3)+5 \times 2 \\ \quad \quad \quad \quad 如果是情况(3)，则\,k+1=5(b-1)+3 \times 2 \\\quad \quad 可知当\,n=k+1\,时命题也成立。\\ \quad \quad综上，根据第一数学归纳法，这个命题对所有 \ge 8\,的正整数\,n\,都成立。$

例题1-3

$试证：对于任何正整数\,n \ge 3\,，总存在奇数\,x,y\,，使得\,2^n=7x^2+y^2\,。$

证明如下：

$证：\\ \quad \quad 当\,n=3\,时，有\,2^3 = 7 \times 1^2+1^2\,，令\,x=1,y=1\,，可知命题是成立的。\\ \quad \quad 假设\,n=k时，命题成立，即：2^k=7x_1^2+y_1^2，其中x_1,y_1为奇数。\,\\ 由：\\ \quad \quad \begin{aligned}& (7x_1^2+y_1^2)(7x_2^2+y_2^2)=7(x_1y_2+x_2y_1)^2+(7x_1x_2-y_1y_2)^2 \quad (1)\\ &(7x_1^2+y_1^2)(7x_2^2+y_2^2)=7(x_1y_2-x_2y_1)^2+(7x_1x_2+y_1y_2)^2 \quad (2) \end{aligned}\\ 得：\\ \quad \quad 当\,n=k+1\,时，2^{k+1} = 2^k \times 2 = (7x_1^2+y_1^2) \cdot [7({1 \over 2})^2+({1 \over 2})^2]= \\ \quad \quad \begin{cases}& 7({\large x_1+y_1 \over 2})^2+({\large 7x_1-y_1 \over 2})^2 \quad (3)\\ &7({\large x_1-y_1 \over 2})^2+({\large 7x_1+y_1 \over 2})^2 \quad (4) \end{cases} \\因为x_1,y_1都是奇数，所以\,{\large x_1+y_1 \over 2},{\large 7x_1-y_1 \over 2},{\large x_1+y_1 \over 2},{\large 7x_1+y_1 \over 2}\,都是整数。\\如果\,{\large x_1+y_1 \over 2}\,为奇数，则\,{\large 7x_1-y_1 \over 2}=4x_1-{\large x_1+y_1 \over 2}\,也为奇数，命题成立。\\ 如果\,{\large x_1+y_1 \over 2}\,为偶数，则\,{\large x_1-y_1 \over 2}=x_1-{\large x_1+y_1 \over 2}\,为奇数，则\,{\large 7x_1+y_1 \over 2}=4x_1-{\large x_1-y_1 \over 2}\,也为奇数，命题成立。\\综上，由第一数学归纳法可知，命题对所有\,n \ge 3\,都成立。$

第二数学归纳法

概念

$\quad \quad 设\,{\color{Black}P(n)}\,是一个含有正整数n的命题，如果\\ \,\,\quad \quad \quad (1)\,当\,n=a\,时，P(a)成立；\\\,\,\quad \quad \quad(2)\,\,在\,P(m)\,对所有适合\, a \le m \le k\,的正整数\,m\,成立的假定下，\,P(k+1)成立，\,\\ \quad \quad 那么\,P(n)\,对所有正整数\,n \ge a\,都成立。$

例题

例题2-1

$有两堆石子，数目相等，有两个人玩耍，每人可以在任一堆里任意取几颗，但不能同时在两堆里取，规定取得\\最后一颗者胜。试证：后取者必胜。\\证：\\ \quad \quad 设\,n\,是每一堆棋子的颗数。\\ \quad \quad 当n=1时，先取者只能在一堆里取一颗，这样另一堆里留下的1颗就被后者取得，所以结论成立。\\ \quad \quad 假设当\,1 \le n \le k\,时结论成立，当\,n=k+1\,时，先取者可以在一堆里取棋子\,t\,(\,1 \le t \le k\,)颗，这样剩下的\\棋子中，一堆有棋子\,k+1颗\,，另一堆有棋子\,k+1-t\,颗，这时后取者可以在较多的一堆里取棋子\,t\,颗，使得\\两堆棋子都有\,k+1-t\,颗。由归纳假设，后取者可以获胜。\\ 根据第二数学归纳法，这个命题对所有正整数\,n\,来说，后取者必胜。$

例题2-2

$试证：对任意正整数\,n,n+1\,个组合数\,C_n^0,C_n^1,\cdots,C_n^n\,均为奇数的充要条件是\,n\,具有\,n=2^k-1\,(k \ge 1)\,的形式。$
$证：\\ \quad \quad 当\,n \le 7\,时，直接验证可知，仅在\,n=1=2^1-1,n=3=2^2-1,n=7=2^3-1\,时，组合数\,C_n^l(0 \le l \le n)\, \\ \quad \quad 为奇数。假设对小于\,n\,的情形命题成立。我们来考察等于\,n\,的情形，此时全体组合数\,C_n^l\,分别为 \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad 1,n,{\Large n(n-1) \over 2\,!},\cdots,{\Large n(n-1)\cdots(n-l+1) \over l\,!},\cdots,n,1 \\ \quad \quad 要使这些数都为奇数；首先，第二项及倒数第二项的\,n\,应是奇数，即\,n=2m+1\,；\\ \quad \quad 另外，在其余各项的分子、分母中，把奇因子去掉后，余下部分以\,n=2m+1\,代入，恰得\\ \quad \quad \quad \quad \quad \quad \qquad \qquad \qquad \qquad {\Large m \over 1},{\Large m(m-1) \over 1 \times 2},\cdots,{\Large m \over 1} \\ \quad \quad 要使这些数均为奇数，则它们也应全是奇数，而它们恰是\,m(\lt n)\,时的全体\,C_m^l(0 \lt l \lt m)\,。\\ \quad \quad 由归纳假设知，它们都是奇数的充要条件是，m\,有\,m=2^k-1\,的形式，此时\\ \quad \quad \qquad \qquad n = 2m+1 = \,2(2^k-1)+1=2^{k+1}-1\,。\\ \qquad 由第二数学归纳法可知，该命题对任意正整数\,n\,都成立。$

事实上

$\begin{aligned}当\,n=2m+1\,时，& C_{n}^{2k+1}=C_{2m+1}^{2k+1}={ (2m+1)(2m)(2m-1)\cdots(2m-2k+1) \over (2k+1)\,! }\\ & \xlongequal[]{去掉奇因数,奇偶性不变}{ (2m)(2m-2)\cdots(2m-2k+2) \over (2k)(2k-2)\cdots2} \\ \\ &\xlongequal[]{上下同时除以2^k，奇偶性不变} {m(m-1)\cdots(m-k+1) \over k\,!} \\ &= C_m^k \quad (1)\end{aligned} \\ 于是得：\\ \begin{aligned} \\ \quad \quad C_n^{2k+2} &= C_n^{2k+1} \cdot {n-2k-1 \over 2k+2} \xlongequal[]{奇偶性不变}=C_m^k \cdot {n-2k-1 \over 2k+2} \\ &=C_m^k \cdot {(2m+1)-2k-1 \over 2k+2} \xlongequal[]{上下同时除以2,奇偶性不变}C_m^k \cdot {m-k \over k+1} \\ &=C_m^{k+1} \quad (2)\end{aligned} \\ 于是，由于假定\,m=2^h-1\,为奇数，且\,n=2m+1\,为奇数，则对于任意\,1 \le t \le n\,，\\ \quad \quad 若\,t\,为偶数，必可取\,k_1={\large t \over 2}\, \le {\large n-1 \over 2}=m\,，应用(2)式，使得\,C_n^t\,与\,C_m^{k_1}\,的奇偶性相同；\\ \quad \quad 若\,t\,为奇数，必可取\,k_2\,={\large t-1 \over 2} \le {\large n-1 \over 2}=m，应用\,(1)\,式，使得\,C_n^t\,与\,C_m^{k_2}\,的奇偶性相同。\\ 于是如果当\,m=2^k-1\,时，命题成立，那么\,n=2m+1=2^{k+1}-1\,时，命题也成立。\\ 那么由数学归纳法可知，该命题成立。$

例题2-3

$已知，斐波那契(Fibonacci)数列\,\{f_n\}\,满足 \\ \qquad f_1=1\,,\,f_2=1\,,\,f_n=f_{n-1}+f_{n-2}\,\,(n \ge 3)\,,\\ 试证：\quad f_n={\large 1 \over \sqrt[]{5}}[({\large 1+\sqrt[]{5} \over 2})^n-({\large 1-\sqrt[]{5} \over 2})^n]$
$证明：\\ \qquad (1)\,当\,n\,=1,2\,时，通过验证可知，f_1=1,f_2=1,\,可知命题是成立的；\\ \qquad (2)\,假设当\,1 \le m \le k-1\,,f_n\,的等式成立，当\,n=k\,时，观察{\large 1+\sqrt[]{5} \over 2},{\large 1-\sqrt{5} \over 2}与一元二次方程的求根公式 \\ \qquad \qquad \qquad \qquad x_1,x_2={\large -b \pm \sqrt{b^2-4ac} \over 2a} \\ \qquad \quad \,\,式子构造相似，通过比对求得一元二次方程为\,\,x^2-x-1=0\,,设\,x_1 = {\large 1+\sqrt{5} \over 2}\,,x_2= {\large 1-\sqrt{5} \over 2}\,,则有：\\ \qquad \qquad \qquad ({\large1 \over x_1})^2 + {\large1 \over x_1} = 1 \qquad (1)\,\qquad | \qquad ({\large1 \over x_2})^2 + {\large1 \over x_2} = 1 \qquad (2) \\ \quad \quad \,\, 由：\\ \qquad \qquad \qquad f_k={\large 1 \over \sqrt[]{5}}[(x_1)^k-(x_2)^k] \quad (3) \\ \qquad \qquad \qquad f_{k-1}={\large 1 \over \sqrt[]{5}}[({\large 1 \over x_1})(x_1)^k-({\large 1 \over x_2})(x_2)^k] \quad (4) \\ \qquad \qquad \qquad f_{k-2}={\large 1 \over \sqrt[]{5}}[({\large 1 \over x_1})^2(x_1)^k-({\large 1 \over x_2})^2(x_2)^k] \quad (5) \\ \qquad \,\,则由\,(1),(2)\,式，可知\,(3)= (4)+(5)\,,\,即\,f_k = f_{k-1}+f_{k-2}\,,\,故命题也成立；\\ \qquad 综上，由第二数学归纳法可知，该命题对任何正整数都成立。$

“跳跃”的数学归纳法

概念

$\quad \quad 设{\color{Black}P(n)}是一个含有正整数n的命题，如果\\ \,\,\quad \quad \quad (1)\,当\,k=1,2,\cdots,k_0\,时，命题P(k)是成立的；\\\,\,\quad \quad \quad(2)\,\,由\,P(k)\,成立必可推得\,P(k+k_0)\,成立，\\ \quad \quad 那么\,P(n)\,对所有正整数\,n\,都成立。$

这个归纳法的起点是一组事实，相当于对所有正整数以 $k_0$ 个为一组的规模 ( 跨度为 $k_0$ ) 进行分组，形成一个分组序列，然后由前一个分组导出后一个分组，不断进行下去，这是分类分组的思想。

例题

例题3-1

$\begin{aligned}& 求证：方程\,x+2y=n(n \ge 1)\,的非负整数解的组数为\,\,{n+1 \over 2}+{1+(-1)^n \over 4}\,\,\\ & 证明如下：\\ &\quad \quad (1) \,当\,n=1\,时，(x,y)=(1,0)；当\,n=2时，(x,y)=(0,1)\,，可验证命题都是成立的。\\ &\quad \quad (2)\,假设当\,n=k\,时，命题成立，则当\,n=k+2\,时，x+2y=k+2\,的非负整数解的个数，\\ &\quad \quad \quad \,\,等价于\,x+2(y-1)=k\,的非负整数解的个数，等价于\,x+2y=k\,的非负整数解的个数加上\\ &\quad \quad \quad\,\,(x,y)=(k+2,-1)这一组，组数为\,{k+1 \over 2}+{1+(-1)^k \over 4}+1={k+2 \over 2}+{1+(-1)^{k+2} \over 4}\,，因此命题也成立。\\ &\quad\quad (3)\,综上，根据数学归纳法可知，该命题对所有\,n \ge 1\,都成立。\end{aligned}$
更一般地， 方程 $x + m y = n$ 的非负整数解的组数为 $\large \lfloor {n \over m} \rfloor+1$ ，其中 $\large \lfloor {n \over m} \rfloor$ 表示向下取整，也即商 $\large {n \over m}$ 的整数部分。

跷跷板归纳法

概念

$\quad \quad 设有两个关于正整数\,n\,的命题\,A_n,B_n\,，如果\\ \quad \quad \quad\,(1)\,A_1\,成立；\\ \quad \quad \quad\,(2)\,假设\,A_k\,成立，则推出\,B_k\,成立；\\ \quad \quad \quad \,(3)\,假设\,B_k\,成立，则推出\,A_{k+1}\,成立，\\ \quad \quad那么对于任意正整数\,n\,，命题\,A_n,B_n\,都成立。$

例题

例题4-1

$\{ a_n \}满足：a_{2n} = 3n^2，a_{2n-1} = 3n(n-1)+1，n=1,2,3,...。\\ 设\,S_m\,为数列的前\,m\,项的和，即\,S_m = a_1+a_2+\cdots+a_m\,。\\求证：\\\begin{aligned}\quad \quad (1)\,S_{2n-1} &={1 \over 2}n(4n^2-3n+1) \\ \quad \quad (2)\,\,\,\,\,\, S_{2n} &= {1 \over 2}n(4n^2+3n+1) \end{aligned}$

自行证明即可

例题4-2

$设\,r(n)\,表示方程\,x+2y=n\,的非负整数解的组数，试证：\\ \quad \quad r(2l-1)=l，r(2l)=l+1 \\证：\\ \quad \quad 这里，设命题\,A_n\,是“\,r(2n-1)=n\,”，命题\,B_n\,是“\,r(2n)=n+1\,”。\\ \quad \quad 当\,n=1\,时，方程\,x+2y=1\,仅有一组非负整数解\,x=1,y=0\,，所以命题A_1成立。\\ \quad \quad 假设\,r(2k-1)=k\,，即\,A_k\,成立，则当\,n=2k\,时，方程\,x+2y=2k\,时，方程\,x+2y=2k\,的非负整数 \\ \quad \quad 解的组数\,r(2k)\,可分为两类：\\ \quad \quad 一类是\,x=0，解的组数等于1；一类是\,x \ge 1\,，解的组数等于方程\,(x-1)+2y=2k-1\,满足\,x-1 \ge 0,y \ge 0(x,y都是整数)\,的解的组数\,r(2k-1)\,。所以 \,r(2k) = 1+r(2k-1) = k+1\,，即命题\,B_k\,成立。\\ \quad \quad 假设\,r(2k)=k+1\,，即\,B_k\,成立，则当\,n=2k+1\,时，方程\,x+2y=2k+1\,的非负整数解的组数\,r(2k+1) \\ \quad \quad 同样可以分为两类：\\ \quad \quad \,一类是\,x=0\,，解的组数等于0；一类是\,x \ge 1\,，解的组数等于方程\,(x-1)+2y=2k\,满足 \,x-1 \ge 0,y \ge 0(x,y都是整数)\,的解的组数\,r(2k)\,。所以\,r(2k+1)=0+r(2k)=k+1\,，即命题A_{k+1}也成立。\\ \quad \quad 因此，由跷跷板归纳法可知，对一切非负整数l，有：r(2l-1)=l，r(2l)=l+1$

反向归纳法

概念

$设\,P(n)\,是与自然数\,n\,相关的命题，如果\\ \quad \quad(1)\,存在一个递增的无限自然数序列\{n_k\}，使命题\,P_{nk}成立\,，\\ \quad \quad (2)\,在假设当\,n=k+1\,时命题\,P_{k+1}\,成立的前提下，当\,n=k\,时，P(k)\,成立，\\ 那么命题\,P(n)\,对所有自然数\,n\,都是成立的。$

例题

例题5-1

$设\,p\,是素数，而\,m\,是正整数，试证：m^p-m是\,p\,的倍数。\\ 证：\\ \quad \quad 令\,m=tp(t\,是正整数)\,，则\,(tp)^p-tp\,是\,p\,的倍数，即有无穷多个正整数\,tp(t=1,2,\cdots)\,，使得 \\ \,m^p-m\,是\,p\,的倍数。假设\,m=k+1\,时，(k+1)^p-(k+1)\,是\,p\,的倍数，则由 \\ \quad \quad (k+1)^p-(k+1)=(k^p-k)+C_p^1k^{p-1}+C_p^2k^{p-2}+\,\cdots\,+C_p^{p-1}k \\以及 \\ \quad \quad C_p^i={\Large p(p-1)\cdots(p-i+1) \over i\,!}\,\,(1 \le i \le p-1)是\,p\,的倍数，知\,k^p-k\,是\,p\,的倍数。\\ 从而根据反向归纳法，对任意正整数\,m\,，m^p-m\,都是\,p\,的倍数。$

精彩的部分来了

例题5-2：精彩！

$\\ \qquad 设命题\,P(n)为：\,\,a_1,a_2,\cdots,a_n\,是\,n\,个非负实数，则成立不等式 \\ \quad \quad \qquad {\Large a_1+a_2+\cdots+a_n \over n} \ge \sqrt[n]{\large a_1a_2\cdots a_n} \\ \qquad 其中等号成立的充分必要条件是\,a_1=a_2=\cdots=a_n$
$证：\\ \qquad (1)当\,n=1\,，命题\,P(1)\,显然成立；\,当\,n=2\,时，由于\,{\Large (a_1-a_2)^2 \over 4} \ge 0\,，因此\,{\Large a_1+a_2 \over 2} \ge \sqrt[]{a_1a_2}\,，\,P(2)\,显然成立。\\ \qquad (2) \,假设\,n=2^k\,时不等式成立，则当\,n=2^{k+1}\,时，不等式 \\ \qquad \quad \begin{aligned}{ 1 \over 2^{k+1}}\sum_{i=1}^{2^{k+1}} a_i &={1 \over 2}[{1 \over 2^k}\sum_{i=1}^{2^k}a_i+{1 \over 2^k}\sum_{i=2^k+1}^{2^{k+1}}a_i] \\ &\ge \sqrt[]{({1 \over 2^k}\sum_{i=1}^{2^k}a_i)\cdot({1 \over 2^k}\sum_{i=2^k+1}^{2^{k+1}}a_i)} \\ & \ge \sqrt[]{\sqrt[2^k]{\prod_{i=1}^{2^k}a_i} \,\,\,\cdot \sqrt[2^k]{\prod_{i=2^k+1}^{2^{k+1}}a_i}} \\ &= \sqrt[2^{k+1}]{\prod_{i=1}^{2^{k+1}}a_i} \end{aligned} \\ \qquad 也成立，故存在一个递增的无限自然数序列\{n_k=2^k,k \ge 1\}，使命题\,P_{nk}成立。\\ \qquad (3)\,假设当\,n=k+1\,时，命题成立，当\,n=k\,时，由：\\ \qquad \begin{aligned}\quad \quad {1 \over k}\sum_{i=1}^{k}a_i &= {1 \over k+1}({k+1 \over k})\sum_{i=1}^ka_i={1 \over k+1}[\sum_{i=1}^{k}a_i+{1 \over k}\sum_{i=1}^{k}a_i] \\ & \ge \sqrt[k+1]{(\prod_{i=1}^{k}a_i)\cdot({1 \over k}\sum_{i=1}^{k}a_i)}\end{aligned} \\ \qquad \quad 将以上不等式两边升高\,k+1\,次幂，就有 \\ \qquad \qquad \begin{aligned}({1 \over k}\sum_{i=1}^{k}a_i)^{k+1} \ge (\prod_{i=1}^{k}a_i) \cdot ({1 \over k}\sum_{i=1}^ka_i) \end{aligned} \\ \quad \quad 然后两边约去公因子\,\begin{aligned}{1 \over k}\sum_{i=1}^ka_i\end{aligned}\,，再开\,k\,次方根，就得到 \\ \quad \quad \qquad \qquad \qquad \begin{aligned}{1 \over k}\sum_{i=1}^{k}a_i \ge \sqrt[k]{\prod_{i=1}^ka_i}\end{aligned} \\ \qquad 综上，由反向归纳法可知，命题\,P(n)\,对任意正整数都成立。$

推广：数学归纳法也可用于实数相关的问题？

Note : 应以开放的思维看待数学归纳法，学习其思维的精神与本质，而不要被其形式所束缚。

比如：

$设\,P(x)\,是与非负实数相关的命题，如果 \\ \qquad (1) \, 当\, x \in [0,1]\,时，P(x)成立；\\ \qquad (2) \, 在假设\,P(x)\,成立的前提下，可推出\,P(x+1)\,成立，\\ 那么命题\,P(x)\,对所有非负实数\,x\,都是成立的$ 。