PowerPointPresentation-南京大学.ppt

上传人:ga****84 文档编号:381004 上传时间:2018-09-29 格式:PPT 页数:16 大小:870.50KB
下载 相关 举报
PowerPointPresentation-南京大学.ppt_第1页
第1页 / 共16页
PowerPointPresentation-南京大学.ppt_第2页
第2页 / 共16页
PowerPointPresentation-南京大学.ppt_第3页
第3页 / 共16页
PowerPointPresentation-南京大学.ppt_第4页
第4页 / 共16页
PowerPointPresentation-南京大学.ppt_第5页
第5页 / 共16页
点击查看更多>>
资源描述

1、数学归纳法离散数学归纳与递归南京大学计算机科学与技术系内容提要 数学归纳法 强数学归纳法 运用良序公理来证明数学归纳法数学归纳法(有效性) 良序公理 正整数集合的非空子集都有一个最小元素 数学归纳法的有效性(归谬法) 假设 n P(n)不成立 ,则 n (P(n)成立. 令S= n+ | P(n),S是非空子集. 根据良序公理,S有最小元素,记为m, m1 (m-1)S, 即P(m-1)成立. 根据归纳步骤,P(m)成立,即mS,矛盾. 因此, n P(n)成立.数学归纳法(举例) Hk=1+1/2+1/k (k为正整数) 证明:H2n 1+n/2 (n为正整数) 基础步骤:P(1)为真, H

2、2=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为正整数) 运用数学归纳法证明(练习)运用数学归纳法时犯的错误强数学归纳法强数学归纳法(一般形式) 设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).强数学归纳法(有效性) nZ | n a 是良序的 良序集:该集合的非空子集都有一个最小元素 强数学归纳法的有效性(归谬法) 假设 n P(n)不成立 ,则 n (P(n)成立. 令S= n | (na) P(n) ,S是非空子集. 根据良序公理,S有最小元素,记为m, mb a, , (m-1)S, 即P(a), , P(m-1)成立, 其中 m-1 b. 根据归纳步骤,P(m)成立,即mS,矛盾. 因此, n P(n)成立.

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 学术论文资料库 > 毕业论文

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。