数学归纳法 描述一个与自然数相关的命题P(n),P,m)等 证明 归纳基础:例如P()真 归纳步骤:例如P(n)→P(n+1) 第一数学归纳法: n=0为真 假设对n为真,证对n+1为真 第二数学归纳法: n=0为真 假设对一切小于n的k为真,证明对n为真
数学归纳法 描述一个与自然数相关的命题 P(n)，P(n,m)等 证明 归纳基础：例如 P(0) 真 归纳步骤：例如 P(n) ⇒ P(n+1) 第一数学归纳法： n=0为真 假设对n为真，证对n+1为真 第二数学归纳法： n=0为真 假设对一切小于n 的 k 为真, 证明对 n 为真
数学归纳法的推广 证明命题Pmn) 针对m,n两个自然数 任意给定m(或n)对n(或m)归纳 多重归纳 归纳基础<0,n>为真,<m,0>为真 归纳步骤 假设<m-1,>,<m,n-1>为真,证<mn>为真
数学归纳法的推广 证明命题 P (m, n ) 针对 m, n 两个自然数 任意给定 m（或 n）对n ( 或 m) 归纳 多重归纳 归纳基础 <0, n’>为真， < m’,0>为真 归纳步骤 假设 < m-1, n>,< m , n-1>为真，证 <m,n >为真
上下界逼近 确定某个值(或阶) 步骤 证明这个值的上界 证明这个值的下界 如果上界与下界相等,则结束 否则改进上界或者下界,使得它们逐渐逼近
上下界逼近 确定某个值（或阶） 步骤 证明这个值的上界 证明这个值的下界 如果上界与下界相等，则结束 否则改进上界或者下界，使得它们逐渐逼近
实例 用红、蓝两色任意对Kn的边涂色,n至少是多少才能 出现一个红色的三角形,或者出现一个蓝色的三角形? 证明 (1)上界m≤6.,n=6,某顶点至少3条同色边(比如红色) (2)下界n>5.反例,n=5不可能做到 (3)n=6
用红、蓝两色任意对 Kn的边涂色，n 至少是多少才能 出现一个红色的三角形，或者出现一个蓝色的三角形？ 证明 （1）上界 n≤6. n=6，某顶点至少 3 条同色边（比如红色） （2）下界 n>5. 反例，n=5 不可能做到. （3）n=6. 实例