浙江大学：《离散数学》课程教学资源（PPT课件讲稿）第三章 推理与证明方法（3.2）数学归纳方法

数学归纳方法 3数学推理 Mathematical Reasoning 3.1推理与证明方法 32数学归纳方法 Mathematical induction 33递推方法 2/24/202111:37PM Deren Chen Zhejiang univ

数学归纳方法 2/24/2021 11:37 PM Deren Chen, Zhejiang Univ. 1 3 数学推理 Mathematical Reasoning 3.1 推理与证明方法 3.2 数学归纳方法 Mathematical Induction 3.3 递推方法

Definition 1 数学归纳方法 数学归纳法的公式表示: IP(1)∧Vm(m≥1∧P(m)→P(m+1)→VnP(an) 1、归纳基础:P(1) 2、归纳步骤:Vm(m≥1∧P(m)→P(m+1) 2/24/202111:37PM Deren Chen Zhejiang univ 2

数学归纳方法 2/24/2021 11:37 PM Deren Chen, Zhejiang Univ. 2 数学归纳法的公式表示： [P(1) ∧ m(m  1 ∧ P(m) → P(m+1))] →  n P(n) 1、归纳基础：P(1) 2、归纳步骤： m (m  1 ∧ P(m) → P(m+1)) Definition 1

皮亚诺公理 数学归纳方法 (1)0∈N; (2)对每一个n∈N,唯一定义了一个自然数n',n'称为n的后邻; (3)不同的自然数,其后邻也不同 (4)没有一个自然数的后邻是0 (5)如果有一个子集MN满足: ①0∈M;②n∈M时必n∈M,则M=N 自然数全体N通过皮亚诺公理的五条公理组成。 这些公理缺一不可,其中性质(5)称为归纳公理,并指出了自然数 是满足公理(1)~(4)的最小集合。 2/24/202111:37PM Deren Chen Zhejiang univ 3

数学归纳方法 2/24/2021 11:37 PM Deren Chen, Zhejiang Univ. 3 皮亚诺公理 （1）0∈N； （2）对每一个n∈N，唯一定义了一个自然数n'，n'称为n的后邻； （3）不同的自然数，其后邻也不同； （4）没有一个自然数的后邻是0； （5）如果有一个子集MN满足： ① 0∈M；② n∈M时必n'∈ M, 则M = N 自然数全体N通过皮亚诺公理的五条公理组成。 这些公理缺一不可，其中性质（5）称为归纳公理，并指出了自然数 是满足公理（1）~（4）的最小集合

Definition 2 数学归纳方法 数学归纳法的一般公式表示 IP(k)∧m(m≥k∧P(m)→P(m+1)→VnP(n) 1、归纳基础:P(k 2、归纳步骤:Vm(m≥k∧P(m)→P(m+1)) 2/24/202111:37PM Deren Chen Zhejiang univ

数学归纳方法 2/24/2021 11:37 PM Deren Chen, Zhejiang Univ. 4 数学归纳法的一般公式表示： [P(k) ∧ m(m  k ∧ P(m) → P(m+1))] →  n P(n) 1、归纳基础：P(k) 2、归纳步骤： m (m  k ∧ P(m) → P(m+1)) Definition 2

EXAMPLE1 数学归纳方法 pp 191 example 5 1+2+22+,+2n=2n+1-1 2/24/202111:37PM Deren Chen Zhejiang univ

数学归纳方法 2/24/2021 11:37 PM Deren Chen, Zhejiang Univ. 5 EXAMPLE 1 pp.191 example 5 1 + 2 + 2 2 +… + 2 n = 2 n+1 - 1

Definition 3 数学归纳方法 第二数学归纳法: IP(n0)∧Vk(k>n0∧P(m0)∧P(n0+1)∧…∧P(k) →P(k+1)→ynP(m) 1、归纳基础:P(n) 2、归纳步骤:Vk(k>n∧P(mo)∧P(n0+1) ∧…∧P(k)→P(k+1) 2/24/202111:37PM Deren Chen Zhejiang univ

数学归纳方法 2/24/2021 11:37 PM Deren Chen, Zhejiang Univ. 6 第二数学归纳法： [P(n0 ) ∧ k ( k > n0 ∧ P(n0 ) ∧ P(n0+1) ∧ … ∧ P(k) → P(k+1)) ]→  n P(n) 1、归纳基础：P(n0 ) 2、归纳步骤： k ( k > n0 ∧ P(n0 ) ∧ P(n0+1) ∧ … ∧ P(k) → P(k+1)) Definition 3

EXAMPLE2 数学归纳方法 证明:任意一个大于1的自然数或为质数,或 能表示为若干个质数的乘积。 2/24/202111:37PM Deren Chen Zhejiang univ

数学归纳方法 2/24/2021 11:37 PM Deren Chen, Zhejiang Univ. 7 EXAMPLE 2 证明：任意一个大于1 的自然数或为质数，或 能表示为若干个质数的乘积

Definition 4 数学归纳方法 有限数学归纳法:对于m≤n≤n1的P(m) 有限数学归纳法的前推公式表示: P(n0)∧yn(m0≤n≤n1-1∧P(n)→P(n+1)→ yn(n≤n≤nk→P(n) 1、归纳基础:P(m) 2、归纳步骤:Vn(n0≤n≤n-1∧P(m)→P(n+1) 2/24/202111:37PM Deren Chen Zhejiang univ

数学归纳方法 2/24/2021 11:37 PM Deren Chen, Zhejiang Univ. 8 有限数学归纳法：对于n0  n  nk 的 P(n) 有限数学归纳法的前推公式表示： [P(n0 ) ∧ n(n0  n  nk -1 ∧ P(n)) → P(n+1))] →  n (n0  n  nk → P(n)) 1、归纳基础：P(n0 ) 2、归纳步骤： n(n0  n  nk -1 ∧ P(n)) → P(n+1))] Definition 4

EXAMPLE 3 数学归纳方法 pp 195 Example 11 2/24/202111:37PM Deren Chen Zhejiang univ

数学归纳方法 2/24/2021 11:37 PM Deren Chen, Zhejiang Univ. 9 EXAMPLE 3 pp. 195 Example 11

Definition 5 数学归纳方法 有限数学归纳法:对于m≤n≤n1的P(m) 有限数学归纳法的后推公式表示: P(n1)∧vn(m0+1≤n≤nk∧P(m)→P(n-1)→ yn(n≤n≤nk→P(n) 1、归纳基础:P(nk) 2、归纳步骤:Vm(n0+1≤n≤nk∧P(n)→P(n-1) 2/24/202111:37PM Deren Chen Zhejiang univ

数学归纳方法 2/24/2021 11:37 PM Deren Chen, Zhejiang Univ. 10 有限数学归纳法：对于n0  n  nk 的 P(n) 有限数学归纳法的后推公式表示： [P(nk ) ∧ n(n0 +1  n  nk ∧ P(n)) → P(n-1))] →  n (n0  n  nk → P(n)) 1、归纳基础：P(nk ) 2、归纳步骤： n(n0 +1  n  nk ∧ P(n)) → P(n-1)) Definition 5