数学归纳法.doc

数学归纳法 摘 要：数学归纳法是一种非常重要的数学证明方法,典型的用于确定一个表达式在所有自然数范围内是成立的或者用于确定一个其他形式在一个无穷数列是成立的.本文通过直接证法引入数学归纳法,并介绍了数学归纳法的两个基本步骤及原理.初等数论研究的是关于整数的问题,故应用数学归纳法证明初等数论中的有关的命题是重要的途径. 关键词：数学归纳法;初等数论;不定方程;整除;同余 1 引论 1.1 直接证法 众所周知,数学上的许多命题都与自然数有关.这里所指的,往往是指任意的一个自然数.因此,这样的一个命题实际上也就是一个整列命题.要证明这样一整列命题成立,当然可以有多种不同的方法. 其中常用的方法是置的任何具体值而不顾,而把它看成是一个任意的自然数,也就是说,假定它只是任何自然数都具备的共同性质,并且在这样的基础上进行推导、运算.如果我们在推导运算中没有遇到什么难以克服的困难,那么我们就有可能用这种方法来完成命题的证明了.这种方法就是习惯上所说的直接证法.如下例： 例1 已知,满足 ,. 证明 . 证 由条件知,,,不全为零; 由条件知这个实数中既有正数也有负数.记 ,. 则和都不是空集,它们互不相交,且={1,2,3,,}. 若再记=,=, 就有 +=0,-=1. 因此知=-=.采用所引入的符号,就有 . 由和的定义和性质知是若干非负数之和,是若干负数之和,因此就有 ===. 可见命题的结论是成立的. 在这个证明中,我们没有考虑究竟是几的问题,只是把精力花费在对命题条件的推敲和剖析上.这种证法就是直接证法． 1.2 数学归纳法 有时,我们也会碰到一些与有关的命题,对于它们很难从任意的入手,那么我们就只能另辟蹊径,也就是所谓的数学归纳法.如下例： 例2 证明对于每个不小于的自然数,都可以找到一个正整数,使它可以表示为自身的个互不相同的正约数之和． 分析 显然,我们很难对任意一个不小于的自然数,直接去找到出相应的来.面对这样的情形,较为稳妥的做法只能是先从,,找起.经过不多的几步探索,就可以发现,有 . 而且,,恰好是的个互不相同的正约数,因此可将取作.在此基础上,又可发现有 . 而且,,,恰好又是的个互不相同的正约数,因此又可取．循环下去,便知可依次取,,．这也就告诉我们：如果取定了,那么接下去就只要再取就行了. 证 当时, . 假设当时成立,即可以表示成自身的个互不相同的正约数 之和,即 . 取定,则： . 若记,则显然有,即互不相同且是的正约数. 故由第一类数学归纳法得此命题正确. 由上所述,数学归纳法可以处理像例2那样不宜于采用直接证法的问题,也可以处理一些可以通过直接证法来解决的问题.如下例: 例3 证明:对任何自然数,数能被整除. 若用直接证法,则如下： 证 按照的奇偶性,可以将上式表示两种不同的形式. 当为奇数时,有 . 当为偶数时,有 . 于是上述两式中,第一个括号内的指数都是奇数,第二个括号内的指数都是偶数. 而当为奇数,则有 . 当为偶数,则可整除. 当,,,可根据上式得出两式是的倍数.从而命题得证. 若用数学归纳法,则如下： 证 当时,能被整除. 假设时,能被8整除. 则当时,我们有 =. 所以就有 . 由于对任何自然数,数和都是奇数,所以其和恒为偶数. 从而一定是的整数.即可被整除. 由第一类数学归纳法,对任何自然数,数都可被整除. 1.3 初等数论 初等数论是数的规律,特别是整数性质的数学分支,它是数论中的最古老的分支.其它的组合数论、解析数论、代数数论、几何数论、超越数论都是在初等数论的基础发展起来的. 初等数论是一门十分重要的数学基础课,小学阶段就有初等数论的影子.初等数论不仅是师范院校数学专业,大学数学各专业的必修课,也是计算科学,密码学等许多相关专业所需的课程. 2 数学归纳法的原理 2.1 第一类数学归纳法 定理1 设是关于自然数的命题,如果满足:(1)成立;(2)假设当时,命题成立,可以推出成立,则命题对一切自然数都成立. 证 假设命题仍不能对一切自然数≥成立,那么如果记 . . 则有.但因已证成立,知,即有. 由于是非空的自然数集合,所以由自然数的最小数原理,有最小数. 由于,所以,即有. 由于是中最小的数,所以,从而. 故当时成立. 记,则由条件(2)知时成立,则与矛盾. 故为空集.也就是说,有对一切自然数都成立. 例4 设,,,试证： 时,. 证 当时,结论显然成立. 假设时结论成立,即当,,时, . 现证等于时结论成立. 由于 又因，故上式： . 即,但,故推得. 由第一数