数学归纳法全讲解第一第二弱强双变量带示例
数学归纳法全讲解（第一、第二、弱、强、双变量）带示例
双变量数学归纳法
本文简介
博主在学习到双变量数学归纳法时候发现网上很难找到清晰明白的教程，就把自己学习和理解的一些知识和大家分享一下。博主不是数学专业，讲解也是从个人理解出发，如有错误还请各位批评指正。
本文从初高中学的数学归纳法（单变量弱归纳）开始，复习数学归纳法基本术语和步骤，然后过渡到强归纳法，用一个例子来说明强归纳和弱归纳的区别，然后再推进到两个变量甚至多变量的数学归纳法。基础较好的同学建议直接跳到双变量部分。
单变量数学归纳 induction
在讲双变量数学归纳之前，我们先来复习一下对于单变量的数学归纳法。
数学归纳法（Mathematical Induction, MI）是一种数学证明方法，通常被用于证明某个给定命题在整个（或者局部）自然数范围内成立。
数学归纳法又可以分为 弱归纳法 （也叫普通数学归纳法，第一数学归纳法）和 强归纳法 （也叫第二数学归纳法）。他们的区别在于对归纳假设的不同：
**弱归纳法假设：
n
k n=k
n
=
k 时命题成立**
**强归纳法假设：
n <
k n<=k
n
<=
k 时命题成立**
一些命题只有用强归纳法才能证明，而用弱归纳法不能证明，在下面会讲到。
弱归纳法(weak induction)
其思想为：
n
0 n=0
n
=
0 时成立，对于任意
n ∈ N ∗ n\in N^*
n
∈
N
∗ ，如果
n
k n=k
n
=
k 时成立，
n
k + 1 n=k+1
n
=
k
1 时也成立，那么可得对于所有
n ∈ N n\in N
n
∈
N 命题都成立。
证明步骤如下 ：
- 归纳奠基
- 证明在
n
0 n=0
n
=
0 时成立（只是第一个情况，如果要求
n ≥ 1 n\geq 1
n
≥
1 ，那么这一步就证明在
n
1 n=1
n
=
1 时成立）
归纳假设 ：假设在
n
k n=k
n
=
k 时成立 (
k
1 k>1
k
1 )
归纳推理 ：当
n
k + 1 n=k+1
n
=
k
1 时，由
n
k n=k
n
=
k 的情况推出
n
k + 1 n=k+1
n
=
k
1 时的情况成立 4. 总结 ：由以上可得对于所有
n ∈ N n\in N
n
∈
N ，命题成立
**例: 证明伯努利不等式
( 1 + x ) n ≥ 1 + n x (1+x)^n\geq 1+nx
(
1
x
)
n
≥
1
n
x ,
x ≥ − 1 , n ∈ N x ≥ −1, n ∈ N
x
≥
−
1
,
n
∈
N**
证明 ：
归纳奠基：当
n
0 n=0
n
=
0 时，
( 1 + x ) 0
1
1 + 0 ∗ x (1+x)^0 =1=1+0*x
(
1
x
)
0
=
1
=
1
0
∗
x , 命题成立 2. 归纳假设：假设
n
k ( k ∈ N ∗ ) n=k(k\in N^*)
n
=
k
(
k
∈
N
∗
) 时命题成立，有
( 1 + x ) k ≥ 1 + k x (1+x)^k \geq 1+kx
(
1
x
)
k
≥
1
k
x 3. 归纳推理：当
n
k + 1 n=k+1
n
=
k
1 时，
( 1 + x ) k + 1
( 1 + x ) ⋅ ( 1 + x ) k (1+x)^{k+1}=(1+x)\cdot (1+x)^k
(
1
x
)
k
1
=
(
1
x
)
⋅
(
1
x
)
k
≥ ( 1 + x ) ⋅ ( 1 + k x )
( 1 + k x + x + k x 2 )
( 1 + ( k + 1 ) ⋅ x + k x 2 ) ≥ ( 1 + ( k + 1 ) x ) \geq (1+x)\cdot (1+kx)=(1+kx+x+kx^2) =(1+(k+1)\cdot x+kx^2)\geq (1+(k+1)x)
≥
(
1
x
)
⋅
(
1
k
x
)
=
(
1
k
x
x
k
x
2
)
=
(
1
(
k
1
)
⋅
x
k
x
2
)
≥
(
1
(
k
1
)
x
)
整理得
( 1 + x ) k + 1 ≥ ( 1 + ( k + 1 ) x ) (1+x)^{k+1}\geq (1+(k+1)x)
(
1
x
)
k
1
≥
(
1
(
k
1
)
x
) 4. 总结：综上可得对于所有的
x ≥ − 1 , n ∈ N x ≥ −1, n ∈ N
x
≥
−
1
,
n
∈
N ,
( 1 + x ) n ≥ 1 + n x (1+x)^n\geq 1+nx
(
1
x
)
n
≥
1
n
x 成立。
强归纳法(strong induction)
其思想为：
n
0 n=0
n
=
0 时成立，对于任意
n ∈ N ∗ n\in N^*
n
∈
N
∗ ，如果
n ≤ k n\leq k
n
≤
k 时成立，
n
k + 1 n=k+1
n
=
k
1 时也成立，那么可得对于所有
n ∈ N n\in N
n
∈
N 命题都成立。
证明步骤如下 ：
- 归纳奠基
- 证明在
n
0 n=0
n
=
0 时成立
归纳假设 ：假设在
n ≤ k n\leq k
n
≤
k 时命题均成立 (
k
1 k>1
k
1 )
归纳推理 ：当
n
k + 1 n=k+1
n
=
k
1 时，由任意
n ≤ k n\leq k
n
≤
k 的情况推出
n
k + 1 n=k+1
n
=
k
1 时的情况成立 4. 总结 ：由以上可得对于所有
n ∈ N n\in N
n
∈
N ，命题成立
例1：强归纳证明（弱归纳无法证明）
弱归纳和强归纳证明上的主要区别在于，弱归纳证明
n
k + 1 n=k+1
n
=
k
1 时候的情况时只能用到
n
k n=k
n
=
k 时候的情况，但是强归纳可以用所有
n ≤ k n\leq k
n
≤
k 时的情况。对于需要递归证明的命题，或者牵扯到前面的情况的命题，往往只能用强归纳法证明而不能用弱归纳法证明。
例：对于任意大于等于2的正整数n，可以将n表示为若干个质数的乘积
证明：
归纳奠基：当
n
2 n=2
n
=
2 时，命题成立，因为
2 2
2 本身就是一个质数。
归纳假设：假设命题对于所有
n ≤ k , ( k
2 n\leq k, (k>2
n
≤
k
,
(
k
2 ,
k ∈ N ∗ ) k\in N^*)
k
∈
N
∗
) 成立。
归纳推理：当
n
k + 1 n=k+1
n
=
k
1 时，如果
k + 1 k+1
k
1 是质数，那么它可以被表示为它自己；如果
k + 1 k+1
k
1 不是质数，那么它一定可以被表示为两个正整数的乘积，即
k + 1
a b k+1=ab
k
1
=
ab ，其中
a a
a 和
b b
b 都是小于等于
k k
k 的正整数。根据归纳假设，
a a
a 和
b b
b 都可以被表示为若干个质数的乘积。因此，
k + 1 k+1
k
1 可以被表示为若干个素数的乘积，命题成立。 4. 总结：根据强归纳法的原理，命题对于所有
n ∈ N ∗ , n ≥ 2 n\in N^*,n\geq 2
n
∈
N
∗
,
n
≥
2 成立。
注：本例来自于ChatGPT，经博主改编整理而成。
双变量数学归纳 induction on two variables
单变量数学归纳是一维的线性结构，右侧命题的正确性可由左侧逐步推到得出：
F ( 1 ) F ( 2 ) … F ( k ) F ( k + 1 ) F(1)\quad F(2) \quad \ldots\quad F(k)\quad F(k+1)
F
(
1
)
F
(
2
)
…
F
(
k
)
F
(
k
1
)
而双变量数学归纳是二维的矩阵结构：
[ F 11 F 12 ⋯ F 1 n F 21 F 22 ⋯ F 2 n ⋮ ⋮ ⋱ ⋮ F m 1 F m 2 ⋯ F m n ] \begin{bmatrix} {F_{11}}&{F_{12}}&{\cdots}&{F_{1n}}\ {F_{21}}&{F_{22}}&{\cdots}&{F_{2n}}\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\ {F_{m1}}&{F_{m2}}&{\cdots}&{F_{mn}}\ \end{bmatrix}
F
11
F
21
⋮
F
m
1
F
12
F
22
⋮
F
m
2
⋯
⋯
⋱
⋯
F
1
n
F
2
n
⋮
F
mn
证明思想1 ：如果对于任意
m m
m ，如果
n
1 n=1
n
=
1 时成立，且
n
k n=k
n
=
k 时由
F ( m , k ) F(m,k)
F
(
m
,
k
) 可推得
F ( m , k + 1 ) F(m,k+1)
F
(
m
,
k
1
) 成立；且对于任意
n n
n ，如果
m
1 m=1
m
=
1 时成立，且
m
k m=k
m
=
k 时由
F ( k , n ) F(k,n)
F
(
k
,
n
) 可推得
F ( k + 1 , n ) F(k+1,n)
F
(
k
1
,
n
) 成立，那么命题对于所有
F ( m , n ) F(m,n)
F
(
m
,
n
) 成立。
这种方法相当于把
m m
m 和
n n
n 分开考虑，把二维降成一维。相当于在矩阵中对每一行从左往右推，和每一列从上往下推，这样就可以扩展到整个矩阵。
证明步骤如下 ：
- 归纳奠基
- 证明
F ( 1 , n ) F(1,n)
F
(
1
,
n
) 和
F ( m , 1 ) F(m,1)
F
(
m
,
1
) 对
∀ m , n ∈ N \forall m,n\in N
∀
m
,
n
∈
N 成立
归纳假设 ：假设对
∀ m , n ∈ N \forall m,n\in N
∀
m
,
n
∈
N ,
F ( k 1 , n ) F(k_1,n)
F
(
k
1
,
n
) ，
F ( m , k 2 ) F(m,k_2)
F
(
m
,
k
2
)
( k
2 , k ∈ N ∗ ) (k>2,k\in N^*)
(
k
2
,
k
∈
N
∗
) 均成立
归纳推理 ：由上述情况推出对
∀ m , n ∈ N \forall m,n\in N
∀
m
,
n
∈
N ，
F ( k 1 + 1 , n ) F(k_1+1,n)
F
(
k
1
1
,
n
) 和
F ( m , k 2 + 1 ) F(m,k_2+1)
F
(
m
,
k
2
1
) 时的情况均成立 4. 总结 ：由以上可得对于所有
F ( m , n ) F(m,n)
F
(
m
,
n
) ，命题成立
证明思想2 ：也可以把
m m
m 和
n n
n 放在一起考虑，首先证明
F ( m , 1 ) F(m,1)
F
(
m
,
1
) 和
F ( 1 , n ) F(1,n)
F
(
1
,
n
) 成立，如果由
F ( m − 1 , n ) F(m-1,n)
F
(
m
−
1
,
n
) 和
F ( m , n − 1 ) F(m,n-1)
F
(
m
,
n
−
1
) 能够推出
F ( m , n ) F(m,n)
F
(
m
,
n
) ,那么即可证明对所有
F ( m , n ) F(m,n)
F
(
m
,
n
) 成立。
这种方法在矩阵中相当于由每个元素的左
1 1
1 元素和上
1 1
1 元素推出当前元素，于是每个元素都会最终推到第一行和第一列，即在base case里已经证明过的
F ( m , 1 ) F(m,1)
F
(
m
,
1
) 和
F ( 1 , n ) F(1,n)
F
(
1
,
n
) 。
证明步骤如下 ：
- 归纳奠基
- 证明
F ( 1 , n ) F(1,n)
F
(
1
,
n
) 和
F ( m , 1 ) F(m,1)
F
(
m
,
1
) 成立
归纳假设 ：假设
F ( k 1 − 1 , k 2 ) F(k_1-1,k_2)
F
(
k
1
−
1
,
k
2
) ，
F ( k 1 , k 2 − 1 ) F(k_1,k_2-1)
F
(
k
1
,
k
2
−
1
)
( k 1 , k 2
2 , k 1 , k 2 ∈ N ∗ ) (k_1,k_2>2,k_1,k_2\in N^*)
(
k
1
,
k
2
2
,
k
1
,
k
2
∈
N
∗
) 成立
归纳推理 ：当
m
k 1 , n
k 2 m=k_1, n=k_2
m
=
k
1
,
n
=
k
2
时，由上述情况推出
F ( k 1 , k 2 ) F(k_1,k_2)
F
(
k
1
,
k
2
) 时的情况成立
总结 ：由以上可得对于所有
F ( m , n ) F(m,n)
F
(
m
,
n
) ，命题成立
证明思想3 ：同证明思想2，但是把推理步骤变成：假设
F ( m , n ) F(m,n)
F
(
m
,
n
) 成立，由此推
F ( m + 1 , n ) F(m+1,n)
F
(
m
1
,
n
) 和
F ( m , n + 1 ) F(m,n+1)
F
(
m
,
n
1
) 成立。相当于从矩阵中每一个元素推它的右边和下边。这个和思想
2 2
2 用哪个就看哪个更好证明了。在实际证明中感觉这个用得比前两种方法多一些。
证明步骤如下 ：
- 归纳奠基
- 证明
F ( 1 , n ) F(1,n)
F
(
1
,
n
) 和
F ( m , 1 ) F(m,1)
F
(
m
,
1
) 成立
归纳假设 ：假设
F ( k 1 , k 2 ) F(k_1,k_2)
F
(
k
1
,
k
2
)
( k 1 , k 2
2 , k 1 , k 2 ∈ N ∗ ) (k_1,k_2>2,k_1,k_2\in N^*)
(
k
1
,
k
2
2
,
k
1
,
k
2
∈
N
∗
) 成立
归纳推理 ：由上述情况推出
F ( k 1 + 1 , k 2 ) F(k_1+1,k_2)
F
(
k
1
1
,
k
2
) 和
F ( k 1 , k 2 + 1 ) F(k_1,k_2+1)
F
(
k
1
,
k
2
1
) 时的情况均成立 4. 总结 ：由以上可得对于所有
F ( m , n ) F(m,n)
F
(
m
,
n
) ，命题成立
以上描述均为弱归纳推理，如果是强归纳推理，只需在假设时把“
=
= ”换成“
≤ \leq
≤ ”即可，和单变量中弱归纳和强归纳的区别相同，再此不再赘述。
例2：斐波那契数列
斐波那契数列（Fibonacci Series）由递归定义，其定义为：
F ( n + 2 )
F ( n + 1 ) + F ( n ) F(n+2)=F(n+1)+F(n)
F
(
n
2
)
=
F
(
n
1
)
F
(
n
)
其中
F ( 0 )
0 , F ( 1 )
1 , n ∈ N F(0)=0, F(1)=1, n\in N
F
(
0
)
=
0
,
F
(
1
)
=
1
,
n
∈
N
试证明对于任意
m , n ∈ N m,n\in N
m
,
n
∈
N ,
F n + m + 1
F n F m + F n + 1 F m + 1 F_{n+m+1}=F_nF_m+F_{n+1}F_{m+1}
F
n
m
1
=
F
n
F
m
F
n
1
F
m
1
提示：斐波那契数列每一项都依赖前两项，所以要用强归纳推理，或者用弱归纳推理但在base case和假设时候都要用连续两项。
证明如下 ：
归纳奠基：
当
m
0 m=0
m
=
0 时，
F n + 1
F n ⋅ F 0 + F n + 1 ⋅ F 1
F n + 1 F_{n+1}=F_n\cdot F_0+F_{n+1}\cdot F_1 =F_{n+1}
F
n
1
=
F
n
⋅
F
0
F
n
1
⋅
F
1
=
F
n
1
成立
当
n
0 n=0
n
=
0 时，
F m + 1
F 0 ⋅ F m + F 1 ⋅ F m + 1
F m + 1 F_{m+1}=F_0\cdot F_m+F_1\cdot F_{m+1} =F_{m+1}
F
m
1
=
F
0
⋅
F
m
F
1
⋅
F
m
1
=
F
m
1
成立 2. 归纳假设：
假设对所有
m ≤ k 1 , n ≤ k 2 , F ( m , n ) m\leq k_1,n\leq k_2,F(m,n)
m
≤
k
1
,
n
≤
k
2
,
F
(
m
,
n
) 均成立。 3. 归纳推理：
法一：对任意
m m
m , 由
2 2
2 得
当
n
k − 1 n=k-1
n
=
k
−
1 时，
F m + k
F k − 1 F m + F k F m + 1 F_{m+k}=F_{k-1}F_m+F_{k}F_{m+1}
F
m
k
=
F
k
−
1
F
m
F
k
F
m
1
成立
当
n
k n=k
n
=
k 时，
F m + k + 1
F k F m + F k + 1 F m + 1 F_{m+k+1}=F_{k}F_m+F_{k+1}F_{m+1}
F
m
k
1
=
F
k
F
m
F
k
1
F
m
1
成立
则当
n
k + 1 n=k+1
n
=
k
1 时，
F m + k + 2
F m + k + 1 + F m + k F_{m+k+2}=F_{m+k+1}+F_{m+k}
F
m
k
2
=
F
m
k
1
F
m
k
= F k − 1 F m + F k F m + 1 + F k F m + F k + 1 F m + 1 =F_{k-1}F_m+F_{k}F_{m+1}+F_{k}F_m+F_{k+1}F_{m+1}
=
F
k
−
1
F
m
F
k
F
m
1
F
k
F
m
F
k
1
F
m
1
= ( F k − 1 + F k ) F m + ( F k + F k + 1 ) F m + 1 =(F_{k-1}+F_k)F_m+(F_{k}+F_{k+1})F_{m+1}
=
(
F
k
−
1
F
k
)
F
m
(
F
k
F
k
1
)
F
m
1
= F k + 1 F m + F k + 2 F m + 1 =F_{k+1}F_m+F_{k+2}F_{m+1}
=
F
k
1
F
m
F
k
2
F
m
1
成立。
同理可得对
m m
m ，当
m
k + 1 m=k+1
m
=
k
1 时命题亦成立 4. 总结：综上可得，…
剩下两种方法不想写了，留给大家当家庭作业，证明和这个差不多的，都是由前面两项相加推出来再后面一项就好了，就是把法一里面比如任意
m m
m 的，换成
m
k 2 m=k_2
m
=
k
2
，然后
m m
m ，
n n
n 可以一起写，其他都是一样的。
xxxxx
欢迎评论区留言~ 如果觉得这篇博客对你有帮助的话就点个赞吧(◍•ᴗ•◍)
参考文献 References
- [1]
- [2][4]
- [3]