39. 数学归纳法

数学归纳法是一个证明命题的方法.

定理 39.1 (数学归纳法). 设 $P(n)$ 是跟整数 $n$ 有关的句子. 设存在一个整数 $n_0$ 使:

(1) (起始步) $P(n_0)$ 为真;

(2) (递推步) 对每一个不低于 $n_0$ 的整数 $n$, “若 $P(n)$ 为真, 则 $P(n+1)$ 为真” 是真的.

那么, 对每一个不低于 $n_0$ 的整数 $n$, $P(n)$ 是真的.

形象地, 我们可视每一个 $P(n)$ 为一本竖立的书. 我们视 “$P(n)$ 为真” 为 “第 $n$ 本书倒下”. 假定, 我们推倒了第 $1$ 本书 $P(1)$ (这对应 “起始步”), 且一本书倒下总会使跟在它后面的那一本书倒下 (这对应 “递推步”). 那么, 第 $1$ 本书, 与其后面的书, 都应倒下.

我们看一个具体的例.

例 39.2. 设 $n$ 是正整数. 用数学归纳法证明$$1+3+\cdots +(2n-1)=n^2.$$(39.1)

既然, 我们要证, 对正整数 $n$, 式 (39.1) 是正确的, 我们可试取 $n_0=1$, 并设命题 $P(n)$: $1+3+\cdots +(2n-1)=n^2$. 我们验证数学归纳法的条件, 即起始步与递推步, 是否都成立.

(1) $P(n_0)$ 即 $P(1)$, 即 $1=1^2$. 这显然是对的. 故起始步成立.

(2) 我们假定 $P(n)$ 是对的, 其中 $n⩾n_0=1$. 我们要由此证明 $P(n+1)$ 也是对的: $$\begin{array}{rl}& 1+3+\cdots +(2n-1)+(2(n+1)-1)\\ =& (1+3+\cdots +(2n-1))+(2n+1)\\ =& n^2+(2n+1)\\ =& (n+1{)}^2.\end{array}$$其中, 从行 2 到行 3, 我们用到了 “$P(n)$ 为真” 的假定 (我们叫这样的假定为归纳假定). 所以, (若 $P(n)$ 是对的, 则) $P(n+1)$ 是对的. 故递推步成立.

根据数学归纳法原理, $P(n)$ 对任何正整数 $n$ 都是成立的.

值得注意的是, 数学归纳法只是证明命题的一个方法. 其实, 我们可用更简单的方法证式 (39.1). 我们记$$\begin{array}{r}{S}_n=1+3+\cdots +(2(n-1)-1)+(2n-1).\end{array}$$因为数的加法适合结合律与交换律, 故$$\begin{array}{r}{S}_n=(2n-1)+(2(n-1)-1)+\cdots +3+1.\end{array}$$从而, 仍由结合律与交换律,$$\begin{array}{r}2S_n=(1+(2n-1))+(3+(2(n-1)-1))+\cdots +((2n-1)+1)=2n\cdot n.\end{array}$$由此可知 $S_n=n^2$.

在数学归纳法里, 起始步与递推步是缺一不可的.

例 39.3 (缺起始步). 设 $n$ 是正整数. 用数学归纳法 “证明” $$1+3+\cdots +(2n-1)=n^2+1.$$(39.2)

既然, 我们要证, 对正整数 $n$, 式 (39.2) 是正确的, 我们可试取 $n_0=1$, 并设命题 $P^{\prime }(n)$: $1+3+\cdots +(2n-1)=n^2+1$. 我们验证数学归纳法的条件, 即起始步与递推步, 是否都成立.

(1) $P^{\prime }(n_0)$ 即 $P^{\prime }(1)$, 即 $1=1^2+1$. 这显然是对的. 故起始步成立.

(2) 我们假定 $P^{\prime }(n)$ 是对的, 其中 $n⩾n_0=1$. 我们要由此证明 $P^{\prime }(n+1)$ 也是对的: $$\begin{array}{rl}& 1+3+\cdots +(2n-1)+(2(n+1)-1)\\ =& (1+3+\cdots +(2n-1))+(2n+1)\\ =& (n^2+1)+(2n+1)\\ =& (n+1{)}^2+1.\end{array}$$其中, 从行 2 到行 3, 我们用到了 “$P^{\prime }(n)$ 为真” 的假定. 所以, (若 $P^{\prime }(n)$ 是对的, 则) $P^{\prime }(n+1)$ 是对的. 故递推步成立.

所以, 根据数学归纳法, 式 (39.2) 是正确的. 可是, 式 (39.2) 不可能是对的! 上个例说, 左侧是 $n^2$, 而 $n^2$ 跟 $n^2+1$ 不可能相等.

我在哪儿出了问题? 不难看出, 起始步出问题了: 我 “错误地” 认为 $P^{\prime }(1)$ 是对的.

由此可见, 数学归纳法的起始步是不可少的.

例 39.4 (缺递推步). 用数学归纳法 “证明” 命题 $Q(n)$ ($n$ 为正整数): 对任何 $n$ 个数 $a_1$, $a_2$, $\dots$, $a_n$, 它 (们) 都相等.

既然, 我们要证, 对正整数 $n$, $Q(n)$ 是正确的, 我们可试取 $n_0=1$. 我们验证数学归纳法的条件, 即起始步与递推步, 是否都成立.

(1) $Q(n_0)$ 即 $Q(1)$, 即: 对任何 $1$ 个数 $a_1$, 它 (们) 都相等. 一般地, 我们认为, 一个数总等于自己. 所以, $Q(1)$ 是对的. 故起始步成立.

(2) 我们假定 $Q(n)$ 是对的, 其中 $n⩾n_0=1$. 我们要由此证明 $Q(n+1)$ 也是对的. 任取 $n+1$ 个数 $a_1$, $a_2$, $\dots$, $a_n$, $a_{n+1}$. 考虑这 $n+1$ 个数的前 $n$ 个: $a_1$, $a_2$, $\dots$, $a_n$. 因为 $Q(n)$ 是对的, 故$$\begin{array}{r}{a}_1=a_2=\cdots =a_n.\end{array}$$再考虑这 $n+1$ 个数的后 $n$ 个: $a_2$, $\dots$, $a_n$, $a_{n+1}$. 仍因 $Q(n)$ 是对的, 故$$\begin{array}{r}{a}_2=\cdots =a_n=a_{n+1}.\end{array}$$既然 $a_1=a_2$, $\dots$, $a_n=a_{n+1}$, 故$$\begin{array}{r}{a}_1=a_2=\cdots =a_n=a_{n+1}.\end{array}$$所以, (若 $Q(n)$ 是对的, 则) $Q(n+1)$ 是对的. 故递推步成立.

所以, 根据数学归纳法, 对每一个正整数 $n$, $Q(n)$ 是正确的. 可是, 这甚至不合常识: 毕竟, $0$ 与 $1$ 就是不相同的二个数.

我在哪儿出了问题? 其实, $Q(1)$ 是不能推出 $Q(2)$ 的. 但是, $Q(2)$ 的确可推出 $Q(3)$; 甚至, 不难看出, 对每一个不低于 $2$ 的整数 $n$, “若 $Q(n)$ 为真, 则 $Q(n+1)$ 为真” 是对的. 虽然如此, 因存在一个不低于 $n_0$ 的整数 $1$, 使 “若 $Q(1)$ 为真, 则 $Q(2)$ 为真” 是错的, 故递推步不成立.

由此可见, 数学归纳法的递推步也是不可少的.

最后, 我用二个有挑战的例助您更好地理解与运用数学归纳法.

例 39.5. 设数列 $a_1$, $a_2$, $\dots$, $a_n$, $\dots$ 适合$$\begin{array}{r}{a}_n=\{\begin{array}{ll}1,& n=1;\\ 1,& n=2;\\ a_{n-1}+2a_{n-2},& n⩾3.\end{array}\end{array}$$用数学归纳法证明: 对任何正整数 $n$, $$\begin{array}{r}{a}_n=\frac{2^n-(-1{)}^n}{3}.\end{array}$$

根据前面的经验, 我们试取 $n_0=1$, 并设命题 $P(n)$: $a_n=(2^n-(-1{)}^n)/3$. 验证起始步时, 没有什么问题: $$\begin{array}{r}\frac{2^1-(-1{)}^1}{3}=\frac{3}{3}=1=a_1.\end{array}$$可是, 在验证递推步时, 我们发现, 我们无法由 $P(1)$ 推出 $P(2)$. 毕竟, 此数列的前 $2$ 项被定义为 $1$, $a_1$ 跟 $a_2$ 无关.

那么, 既然选 $n_0$ 为 $1$ 不合适, 我们能否选 $n_0$ 为 $2$? 首先, $P(2)$ 也是对的: $$\begin{array}{r}\frac{2^2-(-1{)}^2}{3}=\frac{3}{3}=1=a_2.\end{array}$$可是, 我们仍无法由 $P(n)$ 推出 $P(n+1)$ (注意, 此处已假定 $n⩾2$). 我们假定 $P(n)$ 是对的; 换句话说, 我们假定 $a_n=(2^n-(-1{)}^n)/3$. 我们要证 $a_{n+1}=(2^{n+1}-(-1{)}^{n+1})/3$. 根据此数列的定义, $a_{n+1}=a_n+2a_{n-1}$. 我们可代 $a_n$ 以归纳假定, 但 $a_{n-1}$ 不可换.

我们无妨考虑用数学归纳法证明命题 $Q(n)$: $P(n)$ 与 $P(n+1)$ 是正确的.

首先, $Q(1)$ 是对的; 我们验证过.

然后, 我们假定 $Q(n)$ 是对的. 我们要由此证明 $Q(n+1)$ 是对的. 既然 $Q(n)$ 是对的, 那么 $P(n)$ 跟 $P(n+1)$ 都是对的. 为了证明 $Q(n+1)$ 是对的, 我们要证 $P(n+1)$ 与 $P((n+1)+1)$, 即 $P(n+1)$ 与 $P(n+2)$ 都是对的. 根据假定, $P(n+1)$ 是对的. 我们只要证 $P(n+2)$ 也是对的, 即可知, $Q(n+1)$ 是对的: $$\begin{array}{rl}{a}_{n+2}=& a_{n+1}+2a_n\\ =& \frac{2^{n+1}-(-1{)}^{n+1}}{3}+2\cdot \frac{2^n-(-1{)}^n}{3}\\ =& \frac{2}{3}\cdot 2^n+\frac{1}{3}\cdot (-1{)}^n+\frac{2}{3}\cdot 2^n-\frac{2}{3}\cdot (-1{)}^n\\ =& \frac{4}{3}\cdot 2^n-\frac{1}{3}\cdot (-1{)}^n\\ =& \frac{2^{n+2}-(-1{)}^{n+2}}{3}.\end{array}$$所以, (若 $Q(n)$ 是对的, 则) $Q(n+1)$ 是对的.

根据数学归纳法原理, $Q(n)$ 对任何正整数 $n$ 都是成立的. 进而, $P(n)$ 对任何正整数 $n$ 是成立的.

当然, 我们还可考虑, 用数学归纳法证命题 $R(n)$ ($n$ 为不低于 $2$ 的整数): 对任何不超过 $n$ 的正整数 $k$, $P(k)$ 是正确的. (注意, 此处的 $n_0=2$; 并且, 我留此事为您的习题.) 这样, 我们也能证明, $P(n)$ 对任何正整数 $n$ 是成立的.

由此可见:

(1) 不是每一个跟整数相关的命题都能直接地被数学归纳法证明.

(2) 有时, 为运用数学归纳法, 我们要恰当地作辅助命题.

(3) 有时, 辅助命题的作法多于一个.

例 39.6. 设 $a$, $b$ 是正整数. 若存在正整数 $c$ 使 $a=bc$, 我们就说, $b$ 是 $a$ 的一个因子.

注意到, $1$ 是每一个正整数的因子.

显然, 每一个正整数 $a$ 都有因子 $1$, $a$ (注意, 这不一定是二个互不相同的数, 除非 $a>1$). 我们说, 这是 $a$ 的平凡的因子.

设正整数 $a>1$. 若 $a$ 没有不是平凡的因子 (也就是, $a$ 有且只有平凡的因子), 我们说, $a$ 是一个素数. 比如, $2$, $3$, $5$, $7$ 都是素数, 但 $4$, $6$, $8$, $9$ 都不是素数. (根据定义, $1$ 也不是素数.)

我们证明: 可写一个高于 $1$ 的整数为若干个素数的积. 具体地, 设命题 $P(n)$: 存在若干个素数 $p_1$, $p_2$, $\dots$, $p_k$ 使$$\begin{array}{r}n=p_1{p}_2\dots p_k.\end{array}$$那么, 我们的目标就是, 当 $n⩾2$ 时, $P(n)$ 是正确的.

我们试直接用数学归纳法证 $P(n)$. 取 $n_0=2$. 因为 $2$ 是一个素数, 故它当然是 “一个素数的积” (即自己). 但是, 我们似乎无法由 $P(n)$ 推出 $P(n+1)$, 因为, $n$ 跟 $n+1$ 的因子似乎没有 “有意思的关系”. (因子的定义涉及乘法, 而跟加法的关系不那么大. 试想: 若您知道 $2$ 是 $n$ 的因子, 那您知道 $n+1$ 有哪些不是平凡的因子的因子吗? 这或许是难的.)

根据上个例的经验, 我们试作辅助命题 $Q(n)$: $P(n)$ 与 $P(n+1)$ 是正确的. 取 $n_0=2$. 不难验证, $Q(n_0)$ 是正确的. 但是, 我们似乎仍无法由 $Q(n)$ 推出 $Q(n+1)$.

现在, 您看我的表演. 我作辅助命题 $R(n)$: 对每一个高于 $1$ 且不低于 $n$ 的整数 $i$, $P(i)$ 是正确的. 现在, 我要用数学归纳法证: 当 $n⩾2$ 时, $R(n)$ 是正确的.

取 $n_0=2$. 不难验证, $R(n_0)$ 是正确的.

现在, 设 $R(m-1)$ 是正确的. 我要由此证 $R(m)$ 也是正确的. (这跟 “设 $R(n)$ 是正确的, 由此证 $R(n+1)$ 是正确的” 的本质是一样的; 我只是换 $n$ 为 $m-1$ 而已. 毕竟, $n$, $m-1$ 只是 “编号”.)

因为 $R(m-1)$ 是正确的, 故 $P(2)$, $\dots$, $P(m-1)$ 都是正确的. 所以, 若我们能由此证明 $P(m)$ 是正确的, 则 $R(m)$ 是正确的.

若 $m$ 是一个素数, 则 $m$ 当然是 “一个素数的积” (即自己). 那, 若 $m$ 不是一个素数, 会如何? 既然 $m$ 不是一个素数, 那么, 按定义, 它就有不是平凡的因子的因子 $b$; 也就是, 存在一个高于 $1$, 且低于 $m$ 的整数 $b$, 存在一个整数 $c$, 使 $m=bc$. 不难看出, 此 $c$ 也是高于 $1$, 且低于 $m$ 的. 所以, $P(b)$, $P(c)$ 是正确的. 则存在素数 $p_1$, $\dots$, $p_u$ 使 $b=p_1\dots p_u$, 且存在素数 $p_{u+1}$, $\dots$, $p_v$ 使 $c=p_{u+1}\dots p_v$. 从而$$\begin{array}{r}m=bc=p_1\dots p_u{p}_{u+1}\dots p_v\end{array}$$也是若干个素数的积.

由此可见, $R(m)$ 是正确的.

根据数学归纳法原理, $R(n)$ 对任何高于 $1$ 的整数 $n$ 都是成立的. 进而, $P(n)$ 对任何高于 $1$ 的整数 $n$ 是成立的.