归纳与递归

回顾 数论初步 自然数 整数及基本运算 素数 欧拉函数

提要 归纳 数学归纳法 强数学归纳法 运用良序公理来证明 递归 递归定义 结构归纳法 递归算法

数学归纳法  

数学归纳法（有效性） 良序公理 数学归纳法的有效性（归谬法） 正整数集合的非空子集都有一个最小元素 假设n P(n)不成立，则 n (P(n))成立. 令S={ n+ | P(n)}，S是非空子集. 根据良序公理，S有最小元素，记为m, m1 (m-1)S, 即P(m-1)成立. 根据归纳步骤，P(m)成立，即mS，矛盾. 因此，n P(n)成立.

数学归纳法（举例） Hk=1+1/2+…+1/k （k为正整数） 证明：H2n 1+n/2 （n为正整数） 基础步骤：P(1)为真， H2=1+1/2 归纳步骤：对任意正整数k, P(k) P(k+1). H2k+1 = H2k +1/(2k+1)+…+1/2k+1 (1+k/2)+2k(1/2k+1) =1+(1+k)/2 因此，对任意正整数n, P(n) 成立.

数学归纳法（举例） 猜测前n个奇数的求和公式，并证明之。 1=1 1+3=4 1+3+5=9 1+3+5+7=16 … 1+3+…+(2n-1)=n2（n为正整数）

运用数学归纳法时犯的错误   归纳步骤其实要求看k>=3

强数学归纳法  

强数学归纳法（一般形式） 设P(n)是与整数n有关的陈述， a和b是两个给定的 整数，且a  b. 如果能够证明下列陈述 则下列陈述成立 P(a), P(a +1), …, P(b). 对任意k  b, P(a)… P(k)P(k+1) 则下列陈述成立 对任意n  a, P(n).

强数学归纳法（有效性） { nZ | n  a }是良序的 数学归纳法的有效性（归谬法） 良序集：该集合的非空子集都有一个最小元素 假设n P(n)不成立，则 n (P(n))成立. 令S={ n | (na) P(n) }，S是非空子集. 根据良序公理，S有最小元素，记为m, m>a a, …, (m-1)S, 即P(a), …, P(m-1)成立. 根据归纳步骤，P(m)成立，即mS，矛盾. 因此，n P(n)成立.

强数学归纳法（举例） 任意整数n(n 2)可分解为（若干个）素数的乘积 用4分和5分就可以组成12分及以上的每种邮资. n = 2. P(12), P(13), P(14), P(15). 对任意k 15, P(12)… P(k)P(k+1) 算术基本定理：每个非负整数可以唯一写成非降序排列的素数之积

Odd Pie Fights Placing an odd number of people in the plane, in such a way that every pair of people has a distinct distance between them. At a signal, each person will throw a pie at the closest other person. At least one person does not get hit with a pie？ • Let P(k) be the statement “in such a fight with 2k + 1 people, at least one person is not hit”. P(0) is true because with one person, there is no one else to throw a pie at them and they are not hit. Assume that P(k) is true and look at a pie fight with 2k + 3 people. One pair of people, whom we may call x and y, have the shortest distance of any pair and thus throw pies at each other. Now look at the other 2k + 1 people. If none of them throw at x or y, they are in a 2k + 1 person pie fight and the IH says that one of them is not hit. But if they do throw at x or y, they are just removing pies from a 2k + 1 person pie fight and there is still a person not hit. (Everyone of the other 2k + 1 people who does not throw at x or y throws at their closest person among the others.)

运用良序公理来证明（举例） 设a是整数, d是正整数, 则存在唯一的整数q和r满足 证明 0  r < d a =dq+ r 令S={a-dq | 0a-dq ，qZ}，S非空. 非负整数集合具有良序性 S有最小元，记为r0 = a-dq0. 可证 0  r0 < d 唯一性证明， 0  r1 - r0 = d (q0-q1)  d，因此，q1=q0

运用良序公理来证明（举例） 在循环赛胜果图中，若存在长度为m（m3）的回 路，则必定存在长度为3的回路。 备注： ai  aj 表示ai赢了aj 证明 设最短回路的长度为k //良序公理的保证 假设 k3 a1  a2  a3 …  ak a1 若a3 a1, 存在长度为3的回路，矛盾。 若a1  a3, 存在长度为(k-1)的回路，矛盾。

递归

递归定义（N上的函数） 递归地定义自然数集合N上的函数。 举例，阶乘函数F(n)=n!的递归定义 基础步骤：指定这个函数在0处的值； 递归步骤：给出从较小处的值来求出当前的值之规则。 举例，阶乘函数F(n)=n!的递归定义 F(0)=1 F(n)=nF(n-1) for n>0

Fibonacci 序列 Fibonacci 序列 {fn} 定义如下 其前几个数 证明：对任意n  0， 其中， f0 = 0, fn = fn – 1 + fn – 2, 对任意n  2. 其前几个数 0, 1, 1, 2, 3, 5, 8, … 证明：对任意n  0， 其中，

归纳证明: Fibonacci 序列 验证：当n=0,1时，陈述正确。 对于k+1, 注意：2 =  + 1，且n + 1 = n + n – 1 对任意n  1. Show that whenever n ≥ 3, f_n > α^{n−2}, where α = (1 + √5)/2.

递归定义（集合） 递归地定义集合。 举例，正整数集合的子集S 基础步骤：指定一些初始元素； 递归步骤：给出从集合中的元素来构造新元素之规则； 排斥规则（只包含上述步骤生成的那些元素）默认成立 举例，正整数集合的子集S xS 若xS且yS，则 x+yS。

递归定义（举例） 字母表上的字符串集合*。 字符串的长度（ *上的函数l）。 复合命题的合式公式。 基础步骤：* （表示空串）; 递归步骤：若 * 且x  ，则x * 。 字符串的长度（ *上的函数l）。 基础步骤：l()=0; 递归步骤：l(x) = l() +1, 若 * 且x   复合命题的合式公式。 基础步骤：T, F, s都是合式公式，其中s是命题变元; 递归步骤：若E和F是合式公式，则 (E)、(EF)、 (EF)、 (EF)和(EF)都是合式公式。

结构归纳法 关于递归定义的集合的命题，进行结构归纳证明。 结构归纳法的有效性源于自然数上的数学归纳法 基础步骤：证明对于初始元素来说，命题成立; 递归步骤：针对生产新元素的规则，若相关元素满足命题， 则新元素也满足命题 结构归纳法的有效性源于自然数上的数学归纳法 第0步（基础步骤） 第k步推出k+1步（归纳步骤）

结构归纳法（举例） l(xy) = l(x) + l(y), x和y属于 * 。 证明 设P(y)表示：每当x属于 * ，就有l(xy) = l(x) + l(y) 。 基础步骤：每当x属于 * ，就有l(x) = l(x) + l() 。 递归步骤：假设P(y)为真，a属于 , 要证P(ya)为真。 即：每当x属于 * ，就有l(xya) = l(x) + l(ya) P(y)为真，l(xy) = l(x) + l(y) l(xya)= l(xy)+1= l(x) + l(y)+1=l(x) + l(ya)

广义归纳法（举例） 递归定义am,n 归纳证明 am,n= m+n(n+1)/2 a0,0 = 0 0 1 3 am,n= am-1,n +1 (n=0, m>0) am,n= am,n-1 +n (n>0) 归纳证明 am,n= m+n(n+1)/2 0 1 3 1 2 4 2 3 5 除了自然数上的数学归纳法 均可称为广义归纳法

递归算法 举例：欧几里德算法 递归算法的正确性 （数学归纳法） 递归算法的复杂性 （时间、空间） function gcd(a, b) // ab0, a>0 if b=0 return a else return gcd(b, a mod b) An algorithm is called recursive if it solves a problem by reducing it to an instance of the same problem with smaller input.

欧几里德算法的复杂性 log10 α ≈ 0.208 > 1/5

作业 见课程网站