浙江大学：《离散数学》课程教学资源（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