数学归纳法基本原理及其变体和证明
文章目录
数学归纳法最小数原理记号说明
第一数学归纳法标准形式一般化形式(推广)
第二数学归纳法例👺
逆向归纳法例
refs
数学归纳法
数学归纳法是一种重要数学证明方法,它帮助我们认识客观事物,由有限到无穷,实现质的飞跃数学归纳是变形的演绎法,而非"不完全归纳"数学归纳法依据最小数原理
最小数原理
任何非空的正整数集必有一个最小数
从最大的正整数集
N
+
=
{
1
,
2
,
⋯
,
}
\mathbb{N^{+}}=\{1,2,\cdots,\}
N+={1,2,⋯,}其他正整数集(不妨记为S)是
N
+
\mathbb{N^{+}}
N+的子集
记号说明
设
P
(
n
)
P(n)
P(n)表示一个与正整数有关的命题推广的讲,
P
(
n
)
P(n)
P(n)表示一个与整数有关的命题(不仅限于正整数)
第一数学归纳法
第一数学归纳法可利用最小数原理证明的
标准形式
第一数学归纳法:
(1):
P
(
1
)
P(1)
P(1)成立(2): 在
P
(
k
)
P(k)
P(k)成立的前提下,导出
P
(
k
+
1
)
P(k+1)
P(k+1)成立满足上述两点则
P
(
n
)
P(n)
P(n)对于任何正整数成立 证明:利用反证法
由最小数原理,假设满足(1),(2)的情况下,存在一个最小正整数
n
0
n_0
n0,使得命题
P
(
n
0
)
P(n_0)
P(n0)不成立👺由条件(1),
P
(
1
)
P(1)
P(1)成立,所以
n
0
≠
1
n_0\neq{1}
n0=1;即
n
0
⩾
2
n_0\geqslant{2}
n0⩾2于是
n
0
−
1
n_0-1
n0−1是正整数又因为
n
0
n_0
n0是使
P
(
n
)
P(n)
P(n)不成立的最小正整数,所以
P
(
n
0
−
1
)
P(n_0-1)
P(n0−1)成立由条件(2),
P
(
n
0
−
1
)
P(n_0-1)
P(n0−1)成立一定有
P
(
n
0
)
P(n_0)
P(n0)的成立👺综上,我们得到两个矛盾的结果:
P
(
n
0
)
P(n_0)
P(n0)既成立又不成立,所以不存在这样的正整数
n
0
n_0
n0使得
P
(
n
0
)
P(n_0)
P(n0)不成立所以第一数学归纳法得证
一般化形式(推广)
设
n
0
n_0
n0为整数(
n
0
n_0
n0可以是负整数或零或正整数),若满足
(1):
P
(
n
0
)
P(n_0)
P(n0)成立(2):在
P
(
k
)
(
k
⩾
n
0
)
P(k)(k\geqslant{n_0})
P(k)(k⩾n0)成立的假定下,可以推导出
P
(
k
+
1
)
P(k+1)
P(k+1)成立则
P
(
n
)
P(n)
P(n)对于一切大于等于
n
0
n_0
n0的整数
n
n
n成立 证明与标准形式的过程类似
第二数学归纳法
设
(1):
P
(
1
)
P(1)
P(1)成立(2):在
P
(
m
)
,
(
m
∣
1
<
m
⩽
k
)
P(m),(m|1 P(m),(m∣1 P ( k + 1 ) P(k+1) P(k+1)成立 则 P ( n ) P(n) P(n)对于一切正整数成立Note:条件(2)可以更加强调的等价描述为:在 P ( m ) , ( ∀ m ∈ { m ∣ 1 < m ⩽ k } ) P(m),(\forall{m}\in\{m|1 P(m),(∀m∈{m∣1 P ( k + 1 ) P(k+1) P(k+1)成立证明:(依然使用反证法,并借助最小数原理) 设 P ( n ) P(n) P(n)对于某些正整数不成立(为便于讨论,我们关注其中的第一个)根据最小数原理,比存在使得 P ( n ) P(n) P(n)不成立的最小正整数 k k k即正整数 k k k是使命题 P ( n ) P(n) P(n)不成立的最小正整数( P ( k ) P(k) P(k)不成立)👺由条件(1)可知 P ( 1 ) P(1) P(1)成立,所以 k > 1 k>1 k>1(或者说 k ⩾ 2 k\geqslant{2} k⩾2),于是 k − 1 k-1 k−1是正整数( k − 1 ⩾ 1 k-1\geqslant{1} k−1⩾1)因为 k k k是使得命题 P ( n ) P(n) P(n)不成立的最小正整数,所以 P ( m ) , m = 1 , 2 , ⋯ , k − 1 P(m),m=1,2,\cdots,k-1 P(m),m=1,2,⋯,k−1均成立再由条件(2),可知 P ( ( k − 1 ) + 1 ) P((k-1)+1) P((k−1)+1)即 P ( k ) P(k) P(k)一定成立👺综上,得出两个相互矛盾的结果: P ( k ) P(k) P(k)既不成立又成立 例👺 利用第二数学归纳法证明第 n n n个质数 p n < 2 2 n p_n<2^{2^{n}} pn<22n 知识预备:设 p i , i = 1 , 2 , ⋯ p_i,i=1,2,\cdots pi,i=1,2,⋯是质数,且 p i < p i + 1 p_i pi p i , i = 1 , 2 , ⋯ , m p_i,i=1,2,\cdots,m pi,i=1,2,⋯,m都不是整数 x x x的因子,那么 x x x的质因子 p > p i p>p_i p>pi,当然也有 p > p m p>p_m p>pm(或者说 p ⩾ p m + 1 p\geqslant p_{m+1} p⩾pm+1) 证明: (1):当 n = 1 n=1 n=1时, p 1 = 2 < 2 2 1 = 4 p_1=2<2^{2^{1}}=4 p1=2<221=4,显然命题成立(2):当 1 ⩽ n ⩽ k 1\leqslant{n}\leqslant{k} 1⩽n⩽k时命题成立,即 p i < 2 2 i , i = 1 , 2 , ⋯ , k p_i<2^{2^{i}},i=1,2,\cdots,k pi<22i,i=1,2,⋯,k;构造连乘式有: ∏ i = 1 k p i \prod_{i=1}^{k}p_i ∏i=1kpi< ∏ i = 1 k 2 2 i \prod_{i=1}^{k}2^{2^{i}} ∏i=1k22i= 2 ∑ i = 1 k 2 i 2^{\sum_{i=1}^{k}2^{i}} 2∑i=1k2i= 2 2 k + 1 − 2 2^{2^{k+1}-2} 22k+1−2= 2 2 k + 1 ⋅ 2 − 2 2^{2^{k+1}}\cdot{2^{-2}} 22k+1⋅2−2< 2 2 k + 1 2^{2^{k+1}} 22k+1令 L L L= ( ∏ i = 1 k p i ) + 1 (\prod_{i=1}^{k}p_i)+1 (∏i=1kpi)+1则: L L L ⩽ \leqslant ⩽ 2 2 k + 1 − 2 2^{2^{k+1}-2} 22k+1−2< 2 2 k + 1 2^{2^{k+1}} 22k+1设 L L L的质因子为 p p p,显然 p < 2 2 k + 1 p<{2^{2^{k+1}}} p<22k+1 p i , i = 1 , 2 , ⋯ , k p_i,i=1,2,\cdots,k pi,i=1,2,⋯,k都不是 L L L的质因子(因为 L % p i = 1 , i = 1 , 2 , ⋯ , k L\%p_i=1,i=1,2,\cdots,k L%pi=1,i=1,2,⋯,k(意思是 L L L除以 p i p_i pi的余数是1))所以 p > p k p>p_k p>pk,所以 p ⩾ p k + 1 p\geqslant{p_{k+1}} p⩾pk+1因此 p k + 1 ⩽ p < 2 2 k + 1 p_{k+1}\leqslant{p}<2^{2^{k+1}} pk+1⩽p<22k+1,即 p k + 1 < 2 2 k + 1 p_{k+1}<2^{2^{k+1}} pk+1<22k+1可见,当 n = k + 1 n=k+1 n=k+1时命题成立, 由(1),(2),根据第二数学归纳法知命题成立 Note:这个例子中,我们构造了一个数 L = ( ∏ i = 1 k p i ) + 1 L=(\prod_{i=1}^{k}p_i)+1 L=(∏i=1kpi)+1,并通过判定它的质因子 p p p的取值范围来得到 n = k + 1 n=k+1 n=k+1时命题的成立性 逆向归纳法 对于命题 P ( n ) P(n) P(n),若(1): P ( n k ) P(n_k) P(nk)对无穷多个 n i < n i + 1 , i = 1 , 2 , ⋯ n_i ni n i + 1 − n i ⩾ 1 n_{i+1}-n_{i}\geqslant{1} ni+1−ni⩾1,不一定取等号)(2):在 P ( k + 1 ) P(k+1) P(k+1)成立的假定下,可以推出 P ( k ) P(k) P(k)成立则 P ( n ) P(n) P(n)对于一切正整数 n n n成立证明: 任意取定正整数 n n n,则小于 n n n的正整数只有有限个( n − 1 n-1 n−1个)因为数列 { n i } i = 1 ∞ \{n_i\}_{i=1}^{\infin} {ni}i=1∞中有无穷多个正整数,所以 ∃ n i 0 \exist\ n_{i_0} ∃ ni0 s.t. n i 0 ⩾ n n_{i_0}\geqslant{n} ni0⩾n由(1)可知 P ( n i 0 ) P(n_{i_0}) P(ni0)成立.由(2), P ( n i 0 ) P(n_{i_0}) P(ni0) ⇒ \Rightarrow ⇒ P ( n i 0 − 1 ) P(n_{i_0-1}) P(ni0−1) ⇒ \Rightarrow ⇒ ⋯ \cdots ⋯ ⇒ \Rightarrow ⇒ P ( n ) P(n) P(n)这个过程经过有限步( n i 0 − n n_{i_0}-n ni0−n)能够完成所以 P ( n ) P(n) P(n)对 P ( n ) P(n) P(n)任意正整数都成立 例 逆向归纳法可以证明几何-算数均值不等式可参考refs列出的教材 refs 高中人教版@2007@选修4-5不等式选讲