数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,1
3 数学推理
Mathematical Reasoning
3.1 推理与证明方法
3.2 数学归纳方法
Mathematical Induction
3.3 递推方法数学归纳方法
7/31/2009 11:28 AM 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
数学归纳方法
7/31/2009 11:28 AM 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）的最小集合。
数学归纳方法
7/31/2009 11:28 AM 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
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,5
EXAMPLE 1
pp.191 example 5
1 + 2 + 22 +… + 2n = 2n+1 - 1
数学归纳方法
7/31/2009 11:28 AM 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
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,7
EXAMPLE 2
证明：任意一个大于 1 的自然数或为质数,或能表示为若干个质数的乘积 。
数学归纳方法
7/31/2009 11:28 AM 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
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,9
EXAMPLE 3
pp,195 Example 11
数学归纳方法
7/31/2009 11:28 AM 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
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,11
3 数学推理
Mathematical Reasoning
3.1 推理与证明方法
3.2 数学归纳方法
3.3 递归方法
Recursive Definition
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,12
DEFINITION 1
定义 1 如果一个对象部分地由自己所组成,
或 者 按 它 自 己 定 义,则 称 为 是 递归 的
（ Recursion） 。
递归定义的函数 f：
f的定义域：非负整数集
1、递归基础,f(0)
2、递归步骤,f(n)=g(f(k)),k<n,n>=0
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,13
自然数阶乘 n!就是采用递归方法计算出来的 。
令 f (n) = n!,则 f(n)可以表示为：
f (0) = 1
f (n) = n·f (n–1) n>0
Example 1
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,14
菲波那契数 /Fibonacci
F(0) = 0,F(1) = 1
F(n) = F (n–1) + F (n–2) n>1
由上述公式,我们得到：
F (2) = 1,F (3) = 2,F (4) = 3，
F (5) = 5,F (6) = 8,……
利用菲波那契数可以推算出兔子繁衍规律。
Example 2
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,15
PP,205 Example 6
Example 3
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,16
递归定义的集合：
1,3? S
2,X? S Y? S → X + Y? S
S是能够被 3整除的正整数集合 。
Example 4
∧
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,17
Well-formed formulae
1,命题公式的定义
2,谓词公式的定义
3,数集上的 { +,-,*,/,?}
Example 5
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,18
小 结
1、数学归纳方法基础，步骤一般 /强，无限 /有限
2、递归方法基础，步骤数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,19
进一步的思考
1、以可数集为对象的应用
2、与算法的关系数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,20
练 习
pp.199 5,48,57
pp.209 2(b),(d),8,25
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,1
3 数学推理
Mathematical Reasoning
3.1 推理与证明方法
3.2 数学归纳方法
Mathematical Induction
3.3 递推方法数学归纳方法
7/31/2009 11:28 AM 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
数学归纳方法
7/31/2009 11:28 AM 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）的最小集合。
数学归纳方法
7/31/2009 11:28 AM 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
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,5
EXAMPLE 1
pp.191 example 5
1 + 2 + 22 +… + 2n = 2n+1 - 1
数学归纳方法
7/31/2009 11:28 AM 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
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,7
EXAMPLE 2
证明：任意一个大于 1 的自然数或为质数,或能表示为若干个质数的乘积 。
数学归纳方法
7/31/2009 11:28 AM 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
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,9
EXAMPLE 3
pp,195 Example 11
数学归纳方法
7/31/2009 11:28 AM 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
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,11
3 数学推理
Mathematical Reasoning
3.1 推理与证明方法
3.2 数学归纳方法
3.3 递归方法
Recursive Definition
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,12
DEFINITION 1
定义 1 如果一个对象部分地由自己所组成,
或 者 按 它 自 己 定 义,则 称 为 是 递归 的
（ Recursion） 。
递归定义的函数 f：
f的定义域：非负整数集
1、递归基础,f(0)
2、递归步骤,f(n)=g(f(k)),k<n,n>=0
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,13
自然数阶乘 n!就是采用递归方法计算出来的 。
令 f (n) = n!,则 f(n)可以表示为：
f (0) = 1
f (n) = n·f (n–1) n>0
Example 1
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,14
菲波那契数 /Fibonacci
F(0) = 0,F(1) = 1
F(n) = F (n–1) + F (n–2) n>1
由上述公式,我们得到：
F (2) = 1,F (3) = 2,F (4) = 3，
F (5) = 5,F (6) = 8,……
利用菲波那契数可以推算出兔子繁衍规律。
Example 2
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,15
PP,205 Example 6
Example 3
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,16
递归定义的集合：
1,3? S
2,X? S Y? S → X + Y? S
S是能够被 3整除的正整数集合 。
Example 4
∧
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,17
Well-formed formulae
1,命题公式的定义
2,谓词公式的定义
3,数集上的 { +,-,*,/,?}
Example 5
数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,18
小 结
1、数学归纳方法基础，步骤一般 /强，无限 /有限
2、递归方法基础，步骤数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,19
进一步的思考
1、以可数集为对象的应用
2、与算法的关系数学归纳方法
7/31/2009 11:28 AM Deren Chen,Zhejiang Univ,20
练 习
pp.199 5,48,57
pp.209 2(b),(d),8,25
