归纳与递推(含解答)

数学归纳法与递推关系数学归纳法和递推关系是数学中常用的证明方法和问题解决思路。

在数学归纳法中，我们使用基础情况和归纳假设来推导出结论，而递推关系则是通过前一项和通项公式的关系来逐项计算得到整个数列或数列的某一项。

本文将详细介绍数学归纳法和递推关系的定义、使用方法和实例。

一、数学归纳法的定义与使用方法数学归纳法是一种证明方法，用于证明满足一定条件的数学陈述在所有情况下都成立。

它基于两个关键步骤：基础情况的证明和归纳假设的使用。

以下是数学归纳法的详细步骤：1. 基础情况的证明：首先，我们需要证明当n等于某一确定值时，数学陈述是成立的。

这一步通常是最简单的，只需验证特定情况下的正确性。

2. 归纳假设的使用：假设当n=k时，数学陈述成立，然后用这个假设来证明当n=k+1时，数学陈述也成立。

这一步是关键，通过归纳假设，我们可以利用前一项结论推导出后一项的正确性。

3. 结论的得出：通过基础情况和归纳假设的使用，我们可以得出数学陈述在所有情况下都成立的结论。

数学归纳法常用于证明数列性质、算术等级和不等式等问题。

它是一种简单而强大的证明工具，往往能够快速解决一些复杂的数学问题。

二、递推关系的定义与使用方法递推关系是一种通过前一项和通项公式的关系来计算数列的方法。

使用递推关系可以通过已知项计算出数列中的其他项，或者求解特定项的数值。

以下是递推关系的定义和使用方法：1. 递推关系的定义：递推关系通过数列中前一项的值和通项公式的关系来计算数列中其他项的值。

通项公式是一个表达式，能够用来计算数列中任意项的值。

2. 使用递推关系计算数列：对于已知的前几项和通项公式，我们可以使用递推关系来计算数列中的其他项。

首先，确定前一项的值，然后根据递推关系和通项公式计算出下一项的值，如此往复，直到获得所有需要的项。

3. 求解特定项的数值：如果我们只想求解数列中某一特定项的数值，同样可以使用递推关系和通项公式。

根据已知的前几项和递推关系，我们可以逐步计算出目标项的值。

第七讲归纳与递推1、早在公元前300多年前，古希腊著名科学家欧几里德就在他的旷世名著<几何原本》一书中记载了几何学中最基本、最引人人胜的一条著名定理：“三角形的内角和等于180度”，我们的问题是：①四边形的内角和等于多少度（见下图）?答：五边形的内角和等于多少度（见下图）?答：②进一步，如果把多边形的边数记作n，你能够归纳出n边形的内角和的计算公式吗？答：公式为__ __．③在家庭装修中，经常采用各种正多边形（注：正多边形就是各条边均相等且各内角也相等的多边形）的瓷砖搭配出各式各样的地面图案．小明家装修时采用了三种正多边形瓷砖铺地面，这三种型号的瓷砖可以围绕着地面上的一点既不重叠又不产生漏洞的拼接起来．其中一种型号是正方形，另一种型号是正六边形，你知道第三种型号的多边形瓷砖的边数是多少吗？请写出你的计算过程．2、一条直线分一个平面为两部分，二条直线最多分一张平面为四部分，问：五条直线最多分一个平面为多少部分？3、将一个圆形纸片用直线划分成大小不限的若干小纸片，如果要分成不少于50个小纸片，至少要画多少条直线？请说明．、一个长方形把平面分成两部分，那么三个长方形最多把平面分成部分．5、 n个平面最多钝将空间分成多少个部分？6、如下图所示，第一个三角形的面积是256，取三角形的3条边的中点，连成一个三角形，将中间的三角形挖去，得到第二个图，再将第二个图中每个三角形按照前一个做法得到第三个图，如此下去……，求第五个图形的面积是。

7、在一张长方形纸片内有n个点，加上四个顶点共，n+4个点，这些点中任意三点都不在同一条直线上，（1）n=4时，将长方形纸片剪开，最多可以剪成多少个以这些点为顶点的三角形（画出一个示意图即可作答）．(2)n=2010时，最多可以剪成多少个以这些点为顶点的三角形？并作简要说明．(注意：(1)、(2)中任意两个三角形不重叠）8、在一个圆周上标出一些数，第一次先把圆周二等分，在两个分点旁分别标上和，如图a所示；第二次把两段半圆弧二等分，在分点旁标上相邻两分点旁所标两数的和，如图b 所示，=＋；第三次把4段圆弧二等分，并在4个分点旁标上相邻两分点旁所标两数的和，如图c所示，1=＋，1=＋；如此继续下去，当第八次标完数以后，圆周上所有已标的数的总和是____．9、小凯家住二楼，从一楼到二楼的楼梯共有9阶，小凯上楼时每步可跨1阶、跨2阶、或跨3阶．请问他共有多少种不同的方法上楼？10、仅由数字1和2组成一些数，其中至少有两个数字1相连的数称为“学而思数”，如11，112，1211等都是“学而思数”，而12212就不是“掌而思数”．那么所有六位的学而思数共多少个？11、用1×2小长方形或1×3的小长方形覆盖2×6的方格网（如下图所示），共有不同的盖法。

数学归纳法与递推关系式在数学中，有一种经典的证明方法叫做“归纳法”。

归纳法常常用来证明一些关于自然数的命题，也常常和“递推关系式”一起出现。

什么是归纳法？归纳法是指证明一个命题对于所有自然数都成立，只需证明命题对于第一个自然数成立，且证明命题对于任何自然数成立的前提下，可推导出命题对于这个自然数加一成立，那么命题对于所有自然数都成立。

以一个简单的例子来说明归纳法的过程：命题：对于任何正整数n，2 + 4 + 6 + ... + 2n = n(n+1)证明：当n=1时，2+4=6=1(1+1)，命题成立。

假设命题对于某个正整数k成立，则将n=k+1代入命题：2 + 4 + 6 + ... + 2(k+1) = (k+1)(k+2)由于命题对于n=k成立，因此有：2 + 4 + 6 + ... + 2k = k(k+1)将此式两边同时加上2(k+1)，得到：2 + 4 + 6 + ... + 2k + 2(k+1) = k(k+1) + 2(k+1)整理得：2 + 4 + 6 + ... + 2(k+1) = (k+1)(k+2)由此可知，命题对于n=k+1成立。

因此，根据归纳法的原理，命题对于所有正整数n都成立。

什么是递推关系式？在数学中，递推关系式是指一个数列的通项公式中所包含的递推关系，它使得对于一个数列的前几项，可以通过前面的一些项来推出后面的项。

例如，斐波那契数列就是经典的递推数列。

斐波那契数列的第一项是1，第二项是1，从第三项开始，每一项都等于前两项之和。

根据这个关系，可以得到斐波那契数列的通项公式：f(n) = f(n-1) + f(n-2)其中f(n)表示第n项斐波那契数。

类似地，很多数列都可以通过递推关系式来定义。

归纳法和递推关系式的联系归纳法和递推关系式之间有密切的联系。

在使用归纳法证明某个命题时，往往需要使用递推关系式。

例如，考虑斐波那契数列求和的问题。

设S是斐波那契数列前n项的和，即：S = f(1) + f(2) + f(3) + ... + f(n)显然有：S + f(n+1) = f(1) + f(2) + f(3) + ... + f(n) + f(n+1)由于斐波那契数列的递推关系式为：f(n+1) = f(n) + f(n-1)因此，有：S + f(n+1) = f(n) + f(n-1) + f(n+1)即：S + f(n+1) = f(n+2)于是，可以得到：S = f(n+2) - f(n+1)这样，就得到了斐波那契数列前n项的和的通项公式：f(1) + f(2) + f(3) + ... + f(n) = f(n+2) - f(n+1)这个例子说明，在使用归纳法证明某个命题时，如果需要借助递推关系式来推导，可以先列出递推式，然后再尝试使用归纳法来证明。

归纳与递推知识点：从简单情形中摸索规律，再从理解上证明规律的一般性：是人们认识客观法则的重要方法。

简单说：从最简单的情形寻找到规律，用这个规律来解决题目的问题。

1、将正方形纸片由下往上对折，再由左向右对折，称作完成一次操作，按照上述规则完成五次操作以后，剪去所得小正方形的左下角。

问：当展开这张正方形纸片后，一共有多少个小洞孔？2、练习：按照上述例题中的方法操作五次后，在所得到的小正方形的中央戳1个洞，展开这张正方形纸片后，一共有多少个小洞孔？3、在方格纸上画折线段，小方格的边长是1，折线上每一直线段都按照螺旋形依次编号为①、②、③、.......，问：（1）编号65的直线段有多长？（2）长为28的直线段，它的编号是多少号？4、20条直线最多将平面分成多少个部分？5、练习：在一个平面内，20条直线最多可以有多少个交点？6、一个楼梯共有10个台阶，我们规定上楼时，每次只能跨上1个台阶或者是2个台阶，问从地面到最上层共有多少种不同的跨法？7、练习：用10个1×2的长方形取覆盖满2×10的方格网，一共有多少种不同的覆盖方法？8、在三角形ABC内有200个点，以三角形的顶点和这100个点为顶点，可把三角形剖分成多少个小三角形？9、练习：四边形内有100个点，以四边形的4个顶点和里面的100个点为三角形的顶点，最多能剪出多少个小三角形？10、在数2、3之间，第一次写上2和3的和5，第二次在2和5之间写上2与5的和7，同时在3和5之间写上3与5的和8。

即每次都在相邻两个数之间写上这2个数的和，那么这样的过程重复6次。

问所有的数之和是多少？11、练习：在4和5之间，第一次写上两个数的和9，第二次在4、9之间，9、5之间协商13、14，每次都在相邻两个数之间写上两个数的和，这样的过程重复了5次，问所有数的和是多少？12、将1991写成K个自然数的和形式，问这K个自然数的乘积最大是多少？13、练习：将200分解成一些数的和，使得这些自然数的乘积最大是多少？14、平面上10个两两相交的圆最多可以将平面分成多少个区域？平面上1993个圆最多可以将平面分成多少个区域？15练习：平面上20个两两相交的圆最多可以把这些圆分割成多少个部分？16、把1、2、3、.......1991排成一个圆圈，从1起隔一个隔一个的划去（即去2留1，取4留3，.....），直到剩下最后一个数，这个数是多少？17练习：把1、2、3、.......2000排成一个圆圈，从1起隔一个隔一个的划去（即去1留2，去3留4，.....），直到剩下最后一个数，这个数是多少？18、把1、2、3、.......1024排成一个圆圈，从1起隔一个隔一个的划去（即去2留1，取4留3，.....），直到剩下最后一个数，这个数是多少？19、练习：把1、2、3、.......2048排成一个圆圈，从1起隔一个隔一个的划去（即去1留2，去3留4，.....），直到剩下最后一个数，这个数是多少？20、某个计算机接收信息的速度为每秒钟2800字节，发送信息的速度为每秒钟3800字节。

叠加、 叠乘、迭代递推、代数转化数列的递推关系式求数列的通项公式的方法大约分为两类：一类是根据前几项的特点归纳猜测出a n 的表达式,然后用数学归纳法证明；另一类是将递推关系,用代数法、迭代法、换元法,或是转化为根本数列〔等差或等比〕的方法求通项．第一类方法要求学生有一定的观察能力以与足够的结构经验,才能顺利完成,对学生要求高．第二类方法有一定的规律性,只需遵循其特有规律方可顺利求解．在教学中,我针对一些数列特有的规律总结了一些求递推数列的通项公式的解题方法．一、叠加相消．类型一：形如a 1+n ＝a n + f <n>, 其中f <n> 为关于n 的多项式或指数形式〔a n〕或可裂项成差的分式形式．——可移项后叠加相消．例1：数列｛a n ｝,a 1＝0,n ∈N +,a 1+n ＝a n ＋〔2n －1〕,求通项公式a n ． 解：∵a 1+n =a n ＋〔2n －1〕∴a 1+n =a n ＋〔2n －1〕 ∴a 2－a 1 =1 、a 3－a 2=3 、…… a n －a 1-n =2n －3 ∴a n = a 1＋<a 2－a 1>＋<a 3－a 2>＋…＋<a n －a 1-n >=0＋1＋3＋5＋…＋<2n －3> =21[1＋<2n －3>]< n －1>=< n －1>2n ∈N + 练习1：⑴.数列｛a n ｝,a 1=1, n ∈N +,a 1+n =a n ＋3 n, 求通项公式a n ．⑵.数列｛a n ｝满足a 1＝3,)1(21+=-+n n a a n n ,n ∈N +,求a n ．二、叠乘相约．类型二：形如)(1n f a a n n =+.其中f <n> =p pc mn b mn )()(++ 〔p ≠0,m ≠0,b –c = km,k ∈Z 〕或 n n a a 1+=kn 〔k ≠0〕或nn a a 1+= km n< k ≠ 0, 0＜m 且m ≠ 1>． 例2：数列｛a n ｝, a 1=1,a n ＞0,< n ＋1> a 1+n 2－n a n 2＋a 1+n a n =0,求a n ． 解：∵< n ＋1> a 1+n 2－n a n 2＋a 1+n a n =0 ∴ [<n ＋1> a 1+n －na n ]<a 1+n ＋a n >= 0∵ a n ＞0 ∴ a 1+n ＋a n ＞0 ∴ <n ＋1> a 1+n －na n =0 ∴11+=+n n a a n n ∴nn n n n nn a a a a a a a a a a n n n n n n n 11212312111232211=⨯⨯⨯--⨯--⨯-=⨯⨯⨯⨯⨯=-----练习2：⑴数列｛a n ｝满足S n =2na n < n ∈N *>, S n 是{ a n }的前n 项和,a 2=1,求a n ． ⑵.数列｛a n ｝满足a 1+n = 3 na n < n ∈N *>,且a 1=1,求a n ． 三、逐层迭代递推．类型三：形如a 1+n = f <a n >,其中f <a n >是关于a n 的函数.——需逐层迭代、细心寻找其中规律．例3：数列｛a n ｝,a 1=1, n ∈N +,a 1+n = 2a n ＋3 n,求通项公式a n ． 解： ∵a 1+n = 2 a n ＋3 n∴ a n =2 a 1-n ＋3 n-1=2<2 a 2-n ＋3n-2>＋3n-1= 22<2 a 3-n ＋3n-3>＋2·3n-2＋3n-1=……=2 n-2<2 a 1＋3>＋2 n-3·3 2＋2n-4·3 3＋2n-5·3 4＋…＋22·3 n-3＋2·3 n-2＋3n-1=2n-1＋2n-2·3＋2n-3·3 2＋2n-4·3 3＋…＋22·3n-3＋2·3n-2＋3n-1练习3:⑴.假如数列｛a n ｝中,a 1=3,且a 1+n =a 2n 〔n ∈N +〕,求通项a n .⑵.数列｛a n ｝的前n 项和S n 满足S n =2a n +()n1-,n ∈N +,求通项a n ． 四、运用代数方法变形,转化为根本数列求解．类型四：形如1+n n a a = 1++n n qa pa ,〔pq ≠ 0〕．且0≠n a 的数列,——可通过倒数变形为根本数列问题．当p = －q 时,如此有：pa a n n 1111=-+ 转化为等差数列； 当p ≠ －q 时,如此有：ppa q a n n 111+-=+．同类型五转化为等比数列． 例4：假如数列｛a n ｝中,a 1=1,a 1+n =22+n na a n ∈N +,求通项a n ． 解： ∵221+=+n n n a a a又,011>=a ∴0>n a ,∴n n a a 12111+=+∴21111=-+n n a a ∵111=a∴数列{ a n }是首项为1,公差为21的等差数列． ∴na 1=1＋()121-n ∴a n =12+n n ∈N +练习4：f <n> =x x +32,数列{ a n }满足 a 1=1,a n =23f <a 1-n >,求a n ． 类型五：形如a 1+n ＝pa n + q ,pq ≠0 ,p 、q 为常数． 当p ＝1时,为等差数列；当p ≠1时,可在两边同时加上同一个数x,即a 1+n + x = pa n + q + x⇒a 1+n + x = p<a n +p x q +>, 令x =p x q +∴x =1-p q时,有a 1+n + x = p<a n + x >, 从而转化为等比数列 {a n +1-p q} 求解． 例5：数列{a n }中,a 1=1,a n =21a 1-n + 1,n= 1、2、3、…,求通项a n ． 解：∵ a n = 21a 1-n + 1 ⇒ a n －2 =21<a 1-n －2>又∵a 1－2 = -1≠0 ∴数列{ a n －2}首项为-1,公比为21的等比数列．∴ a n －2 = -11)21(-⨯n 即 a n = 2 －2n-1 n ∈N +练习5：⑴. a 1=1,a n = 2 a 1-n + 3 <n = 2、3、4…> ,求数列{a n }的通项．⑵. 数列｛a n ｝满足a 1=21,a 1+n =12+n n a a ,求a n ．类型六：形如a 1+n ＝pa n + f <n>,p ≠0且 p 为常数,f <n>为关于n 的函数． 当p ＝1时,如此 a 1+n ＝a n + f <n> 即类型一．当p ≠1时,f <n>为关于n 的多项式或指数形式〔a n〕或指数和多项式的混合形式． ⑴假如f <n>为关于n 的多项式〔f <n> = kn + b 或kn 2+ bn + c,k 、b 、c 为常数〕,——可用待定系数法转化为等比数列．例6：数列{ a n }满足a 1=1,a 1+n = 2a n ＋n 2,n ∈N +求a n ． 解：令a 1+n + x[a<n+1>2+ b<n+1> + c] = 2<a n + an 2+ bn + c>即 a 1+n = 2 a n + <2a –ax>n 2+ <2b -2ax – bx>n +2c –ax –bx – cx 比拟系数得：⎪⎩⎪⎨⎧=---=--=-0202212cx bx ax c bx ax b ax a ⇒⎪⎪⎪⎩⎪⎪⎪⎨⎧-+=-=-=x bx ax c x ax b x a 22221⇒ 令x = 1,得：⎪⎩⎪⎨⎧===321c b a ∴ a 1+n + <n+1>2+2<n+1> + 3 = 2<a n + n 2+2n + 3> ∵ a 1+1+2×1+3 = 7令b n = a n + n 2+2n + 3 如此 b 1+n = 2b n b 1= 7 ∴数列{ b n }为首项为7,公比为2德等比数列∴ b n = 7× 21-n 即 a n + n 2+2n + 3 = 7× 21-n ∴ a n = 7× 21-n －< n 2+2n + 3 > n∈N +⑵假如f <n>为关于n 的指数形式〔a n〕． ①当p 不等于底数a 时,可转化为等比数列； ②当p 等于底数a 时,可转化为等差数列． 例7：〔同例3〕假如a 1=1,a n = 2 a 1-n + 31-n ,<n = 2、3、4…> ,求数列{a n }的通项a n ．解: ∵ a n = 2 a 1-n + 31-n ∴ 令a n + x ×3n= 2<a 1-n +x ×31-n > 得 a n = 2 a 1-n －x ×31-n令-x ×3n= 3n⇒x = -1 ∴ a n －3n= 2<a 1-n －31-n > 又 ∵ a 1－3 = - 2∴数列{n n a 3-}是首项为-2,公比为2的等比数列． ∴n n a 3-=-2·21-n 即a n = 3n -2nn ∈N +例8：数列{ a n }中,a 1=5且a n =3a 1-n + 3n-1 <n = 2、3、4…> 试求通项a n ．解： a n =3a 1-n + 3n -1 ⇒ a n +-=--)21(3211n a 3n⇒132132111+-=---n n n n a a ⇒{n n a 321-}是公差为1的等差数列．⇒nn a 321-=3211-a +<1-n > = 3215-+<1-n > = n +21 ⇒a n = <213)21+⨯+n n n ∈N +⑶假如f <n>为关于n 的多项式和指数形式〔a n 〕的混合式,如此先转换多项式形式在转换指数形式．例如上面的例8．练习6:⑴.数列{a n }中a 1= 1,a 1+n = 3 a n + n ,+∈N n ; 求{a n }的通项．⑵设a 0为常数,且a n = 31-n －2 a 1-n <n ∈N +且n ≥ 2 >．证明：对任意n ≥ 1,a n =51[3n + <-1>1-n 2n ] +<-1>n 2na 0． 类型七：形如a 2+n = p a 1+n + q a n < pq ≠ 0, p 、q 为常数且p 2+ 4q > 0 >,——可用待定系数法转化为等比数列．例9: 数列{a n }中a 1= 1, a 2= 2且n n n a a a 212+=++ ,+∈N n ; 求{a n }的通项． 解:令a 2+n +x a 1+n = <1+x> a 1+n + 2 a n ⇒ a 2+n +x a 1+n = <1+x>< a 1+n + x+12a n >令x =x+12⇒x 2+ x – 2 = 0 ⇒x = 1或 -2当x = 1时,a 2+n + a 1+n =2<a 1+n + a n > 从而a 2+ a 1= 1 + 2 = 3 ∴数列{ a 1+n + a n }是首项为3且公比为2的等比数列. ∴ a 1+n + a n = 312-⨯n …………①当x = - 2时, a 2+n - 2a 1+n = - <a 1+n -2a n > , 而 a 2- 2a 1= 0 ∴ a 1+n - 2a n = 0 …………② 由①、②得:a n = 21-n , +∈N n练习7：⑴: a 1= 2, a 2= 35, n n n a a a 323512-=++ ,<n = 1、2、3、……>,求数列{ a n }的通项．⑵数列：1、1、2、3、5、8、13、……,根据规律求出该数列的通项． 五、数列的简单应用.例10:设棋子在正四面体ABCD 的外表从一个顶点移向另外三个顶点时等可能的.现抛掷骰子,根据其点数决定棋子是否移动,假如投出的点数是奇数,如此棋子不动；假如投出的点数是偶数,棋子移动到另外一个顶点.假如棋子初始位置在顶点A,如此:⑴投了三次骰子,棋子恰巧在顶点B 的概率是多少? ⑵投了四次骰子,棋子都不在顶点B 的概率是多少? ⑶投了四次骰子,棋子才到达顶点B 的概率是多少？ 分析：考虑最后一次投骰子分为两种情况①最后一次棋子动；②最后一次棋子不动． 解：∵ 事件投一次骰子棋子不动的概率为21；事件投一次骰子棋子动且到达顶点B 的概率为3121⨯ =61． ⑴．投了三次骰子,棋子恰巧在顶点B 分为两种情况①.最后一次棋子不动,即前一次棋子恰在顶点B ；②.最后一次棋子动,且棋子移动到B 点．设投了i 次骰子,棋子恰好在顶点B 的概率为p i ,如此棋子不在顶点B 的概率为<1- p i >．所以,投了i+1次骰子,棋子恰好在顶点B 的概率：p 1+i = p i ×21+ <1- p i >×61i = 1、2、3、4、…… ∴ p 1+i = 61 + 31×p i ∵ p 1= 3121⨯=61∴ p 2=92∴ p 3=5413⑵．投了四次骰子,棋子都不在顶点B,说明前几次棋子都不在B 点,应分为两种情况①最后一次棋子不动；②最后一次棋子动,且不到B 点．设投了i 次骰子,棋子都不在顶点B 的概率为i p ',如此投了i+1次骰子,棋子都不在顶点B 的概率为：1+'i p = i p '×21+ i p '×21×<1﹣31> i = 1、2、3、4、…… 即：1+'i p = 65i p ' 又∵1p '= 21+21×<1﹣31> = 65∴4p ' = <65>4 ⑶．投了四次骰子,棋子才到达顶点B ；说明前三次棋子都不在B 点,最后一次棋子动且 到达顶点B ．设其概率为P 如此： P =3121⨯×3p ' = 61×<65>3= 1296125答：〔略〕．例11：用砖砌墙,第一层〔底层〕用去了全部砖块的一半多一块；第二层用去了剩下的一半多一块,…,依次类推,每层都用去了上层剩下的一半多一块.如果第九层恰好砖块用完,那么一共用了多少块砖？分析：此题围绕两个量即每层的砖块数ai 和剩下的砖块数bi,关键是找出ai和bi的关系式,通过方程<组>求解．解：设第i层所用的砖块数为ai ,剩下的砖块数为bi<i = 1、2、3、4、…… >如此b9=0,且设b为全部的砖块数,依题意,得a 1=21b+ 1,a2=21b1+ 1,…… ai=21b1-i+ 1 …………①又 b1-i = ai+ bi……………②联立①②得 b1-i -bi=21b1-i+ 1 即bi=21b1-i- 1∴ bi + 2 =21<b1-i+ 2> ∴ b9+2 = <21>9<b+ 2 > ∴ b+2 = 2×29∴ b= 1022练习8：⑴十级台阶,可以一步上一级,也可以一步上两级；问上完十级台阶有多少种不同走法？⑵. 三角形内有n个点,由这n个点和三角形的三个顶点,这n + 3个点可以组成多少个不重叠<任意两个三角形无重叠局部>的三角形？⑶．甲、乙、丙、丁四人传球,球从一人手中传向另外三个人是等可能的.假如开始时球在甲的手中．假如传了n次球,球在甲手中的概率为an ；球在乙手中的概率为bn.<n = 1、2、3、4、…… >.①问传了五次球,球恰巧传到甲手中的概率a5和乙手中的概率b5分别是多少？②假如传了n次球,试比拟球在甲手中的概率an 与球在乙手中的概率bn的大小.③传球次数无限多时,球在谁手中的概率大？参考答案练习1：⑴. an =21<3 n-1> ⑵. an=nn2+练习2：⑴. an= n -1 ⑵. an= 32)1(-n n练习3：⑴. an = 321-n <提示：可两边取对数> ⑵. a n=32[22-n+ <-1>1-n]练习4：an =23+n练习5：⑴ an= 21+n-3 ⑵ an=12211+--nn练习6：⑴可得a1+n +21<n+1>+41= 3<an+21n +41> 从而an=47×31-n-<21n +41> ⑵ <略>练习7：⑴an = 3 -132-nn, ⑵由得a2+n= a1+n+ an⇒ an=55[<251+>n-<251->n]练习8：⑴∵a2+n = a1+n+ an, a1= 1,a2= 2,∴a10= 89 ⑵∵a1+n= an+ 2 ,a1= 3 ∴an= 2n+1⑶①∵a1+n =31<1 - an> b1+n=31<1 - bn> a1= 0 b1=31∴a5=8120； b5=24361.②可解得an =41-41×1)31(--n bn=41+121×1)31(--n∴当n为奇数时, an <41<bn；当n为偶数时,an>41>bn③当n →∞时,an →41,bn→41故球在各人手中的概率一样大．。

数学归纳法解决递推问题数学归纳法是解决递推问题的重要方法之一，递推问题在许多计算机科学和数学领域都有很大应用。

在面试或考试中，简单的递推问题则需要用到数学归纳法进行证明。

让我们从以下三个问题开始探讨归纳法在递推问题中的应用。

1. 求解递推式对于一个递推式，如：$a_0 = 2$，$a_{n+1} = 2a_n + 1$。

我们希望求出其$n$项之和，即$\sum_{i=0}^n a_i$。

用归纳法解决这个问题。

首先，当$n=0$时，$\sum_{i=0}^0 a_i = a_0 = 2$，显然成立。

假设当$n=k$时，$\sum_{i=0}^k a_i$成立，即$\sum_{i=0}^ka_i = 2^{k+1} - 1$。

则当$n=k+1$时， $\sum_{i=0}^{k+1} a_i = \sum_{i=0}^k a_i + a_{k+1} = 2^{k+1} - 1 + 2a_k + 1 = 2^{k+2} - 1$。

因此，$\sum_{i=0}^n a_i = 2^{n+1} - 1$，得证。

2. 青蛙跳台阶有一只青蛙，要跳上一个$n$级的台阶。

青蛙每次可以跳1级或2级，求青蛙跳到$n$级台阶的跳法数量。

我们假设青蛙跳到第$k$级台阶的跳法数量为$a_k$。

显然当$n=1$时，$a_1=1$；当$n=2$时，$a_2=2$。

对于$n>2$的情况：（1）当青蛙第一次跳1级时，就跳到了第$n-1$级，此时剩下跳法为$a_{n-1}$种；（2）当青蛙第一次跳2级时，就跳到了第$n-2$级，此时剩下跳法为$a_{n-2}$种。

因此，跳到$n$级台阶的跳法数量就是$a_n=a_{n-1}+a_{n-2}$。

接下来，用数学归纳法证明$a_n=F_{n+1}$，其中$F_i$代表第$i$个斐波那契数。

（1）当$n=1$时，$F_{1+1}=F_2=1$，$a_1=1$，显然成立。

（2）假设当$n=k$时成立，即$a_k=F_{k+1}$。

如何由递推公式求通项公式高中数学递推数列通项公式的求解是高考的热点之一，是一类考查思维能力的题型，要求考生进行严格的逻辑推理。

找到数列的通项公式，重点是递推的思想：从一般到特殊，从特殊到一般；化归转换思想，通过适当的变形，转化成等差数列或等比数列，达到化陌生为熟悉的目的。

下面就递推数列求通项的基本类型作一个归纳，以供参考。

类型一：1()nna a f n 或1()n na g n a 分析：利用迭加或迭乘方法。

即：112211()()+()nnnnna a a a a a a a ……或121121n n n nna a a a a a a a ……例1.(1)已知数列na 满足11211,2nna a a nn，求数列n a 的通项公式。

（2）已知数列n a 满足1(1)1,2nn n a a s ，求数列n a 的通项公式。

解：（1）由题知：121111(1)1nna a nnn n nn 112211()())n n n n na a a a a +(a -a a (1)111111()()()121122n n nn ……312n（2）2(1)n n s n a 112(2)nn s na n两式相减得：12(1)(2)n nna n a na n 即：1(2)1n na n n a n 121121n n nn n a a a a a a a a (121)121nn n n……n类型二：1(,(1)0)nn a pa q p q pq p 其中为常数，分析：把原递推公式转为：1(),1nnq a tp a t p其中t=，再利用换元法转化为等比数列求解。

例2.已知数列n a 中，11,123n n a a a ，求n a 的通项公式。

解：由123nn a a 可转化为：132(3)n na a 令3,nn b a 11n+1n则b =a +3=4且b =2b n b 1是以b =4为首项，公比为q=2的等比数列11422n n bn即123n na 类型三：1()(nn a pa f n 其中p 为常数)分析：在此只研究两种较为简单的情况，即()f x 是多项式或指数幂的形式。

加法原理与归纳递推（一）如下图，从甲地到乙地有2条路，从乙地到丙地有4条路，从甲地到丁有3条路可走，从丁地到丙地也有3条路，请问从甲地到丙地共有多少种不同走法？【温故知新】加法原理：分类计数，类类独立乘法原理：分步计数，步步相关关联词区分：可以……也可以……加法原理先……再……又……乘法原理【例1】如图，图中有25个小方格，要把5枚不同的硬币放在方格里，使得每行、每列只出现一枚硬币，那么共有种放法。

【例2】用红蓝两色来涂图中的小圆圈，要求关于中间那条竖线对称，问共有多少中不同的涂法？【例3】某件工作需要钳工2人和电工2人共同完成，现成钳工3人、电工3人、电工3人，另有1人钳工、电工都会。

从7人中挑选4人完成这项工作，共有多少种方法？【例4】在1到500的自然数中，不含数字0和1的数字有多少个？【例5】利用数字1，2，3，4，5共可组成（1）多少个数字不重复的三位数？（2）多少个数字不重复的三位偶数？（3）多少个数字不重复的偶数？【例6】由数字0，1，3，9可以组成多少个小于1000的自然数？【例7】用数字0，1，2，3，4，5可以组成多少个小于2000的没有重复数字的自然数？【例8】用0，1，2，3四位数码可以组成多少个没有重复数字的四位偶数？课后练习：加乘原理与归纳递推（二）图形染色【例1】如下图，A,B,C,D,E五个区域分别用红、黄、蓝、白、黑五种颜色种的某一种染色，要使相邻的区域染不同的颜色，共有多少中不同的染色方法？【例2】将图中的八个部分用红、黄、蓝、绿这4种不同的颜色染色，而且相邻的部分不能使用用一种颜色，不相邻的部分可以使用用一种颜色。

请问：这幅图共有多少种不同的染色方法？【例3】地图上有A,B,C,D四个国家（如下图），现有红黄蓝绿四种颜色给地图染色，使相邻国家的颜色不同，但不是每种颜色都必须要用，问有多少种染色方法？【例4】用四种不同的颜色对下图的五个字染色，要求相邻的区域的字染不同的颜色，但不是每种颜色都必须要用。

小学五年级奥数第十四讲：归纳与递推的方法递推方法是人们从开始认识数量关系时就很自然地产生的一种推理思想。

例如自然数中最小的数是1，比1大1的数是2，接下来比2大1的数是3，…由此得到了自然数数列：1，2，3，4，5，…。

在这里实际上就有了一个递推公式，假设第n 个数为an，则即由自然数中第n个数加上1，就是第n+1个数。

由此可得：这样就可以得到自然数数列中任何一个数。

再看一个例子：例1 平面上5条直线最多能把圆的内部分成几部分?平面上100条直线最多能把圆的内部分成几部分解：假设用ak表示k条直线最多能把圆的内部分成的部分数。

这里k=0，1，2，…。

如图可见归纳出递推公式（1）即画第n+1条直线时，最多增加n部分。

原因是这样的：第一条直线最多把圆分成两部分，故a1=2。

当画第二条直线时，要想把圆内部分割的部分尽可能多，就应和第一条直线在圆内相交，交点把第二条直线在圆内部分分成两条线段，而每条线段又把原来的一个区域划分成两个区域，因而增加的区域数是2，正好等于第二条直线的序号。

同理，当画第三条直线时，要想把圆内部分割的部分数尽可能多，它就应和前两条直线在圆内各有一个交点。

两个交点把第三条直线在圆内部分成三条线段。

而每条线段又把原来一个区域划分成两个区域。

因而增加的区域部分数是3，正好等于第三条直线的序号，…。

这个道理适用于任意多条直线的情形，所以递推公式(1)是正确的。

这样就易求得5条直线最多把圆内分成：要想求出100条直线最多能把圆内分成多少区域，不能直接用上面的公式了，可把上面的递推公式变形：公式(2)也称为数列1，2，4，7，11，16，…的通项公式。

一般来说，如果一个与自然数有关的数列中任一项 an可以由它前面的k(≤n-1)项经过运算或其他方法表示出来，我们就称相邻之间有递归关系，并称这种公式为递推公式或递推关系式。

通过寻求递归关系来解决问题的方法就称为递推方法。

许多与自然数有关的数学问题都常常具有递推关系，可以用递推公式来表达它的数量关系。