小学五年级奥数 第十四讲：归纳与递推的方法
我敬佩的一个人300字-北京大学考研成绩查询
http:小学奥数辅导网
小学五年级奥数 第十四讲：归纳与递推的方法
递推方法是人们从开始认识数量关系时就很自然地产生的一种推理思想。例如
自然数中最小的数是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，„。
如图可见
http:京翰教育
http:小学奥数辅导网
归纳出递推公式（1）
即画第n+1条直线时，最多增加n部分。原因是这样的：
第一条直线最多把圆
分成两部分，故a1=2。当画第二条直线时，要想把圆内部分割的部分尽可能多，
就
应和第一条直线在圆内相交，交点把第二条直线在圆内部分分成两条线段，而每条
线段又把原
来的一个区域划分成两个区域，因而增加的区域数是2，正好等于第二
条直线的序号。同理，当画第三条
直线时，要想把圆内部分割的部分数尽可能多，
它就应和前两条直线在圆内各有一个交点。两个交点把第
三条直线在圆内部分成三
条线段。而每条线段又把原来一个区域划分成两个区域。因而增加的区域部分数
是
3，正好等于第三条直线的序号，„。这个道理适用于任意多条直线的情形，所以递
推公式(
1)是正确的。这样就易求得5条直线最多把圆内分成：
要想求出100条直线最多能把
圆内分成多少区域，不能直接用上面的公式了，
可把上面的递推公式变形：
http:京翰教育
http:小学奥数辅导网
公式(2)也称为数列1，2，4，7，11，16，„的通项公式。
一般来说，如果一个与自然数有关的数列中任一项 an可以由它前面的k(≤n-1)
项经过运算或其
他方法表示出来，我们就称相邻之间有递归关系，并称这种公式为
递推公式或递推关系式。通过寻求递归
关系来解决问题的方法就称为递推方法。许
多与自然数有关的数学问题都常常具有递推关系，可以用递推
公式来表达它的数量
关系。如何寻求这个递推公式是解决这类问题的关键之一，常用的方法是“退”到<
br>问题最简单情况开始观察，逐步归纳并猜想一般的递推公式。在小学阶段，我们仅
要求学生能拨开
问题的一些表面现象由简到繁地归纳出问题的递推公式就行了，不
要求严格证明。当然能证明更好。所谓
证明，就是要严格推出你建立的关系式适合
所有的n，有时，仅仅在前面几项成立的关系，不一定当n较
大时也成立。
例2 平面上10个两两相交的圆最多能将平面分割成多少个区域?平面上1993
个圆最多能将平面分割成多少个区域?
解：设平面上k个圆最多能将平面分割成ak部分，我们先“退”到最简单的情
形。如图可见：
http:京翰教育
http:小学奥数辅导网
(3)是这个问题的递推公式。再把它变形为当n较大时也能方便求出结果的公
式：
http:京翰教育
http:小学奥数辅导网
关于这
个递推公式成立的正确性分析与例1完全类似。比如，第一个圆显然将
平面分为两个区域;当画第二个圆
时，应与原来的一个圆有两个交点，即被第一个圆
截成两段弧，而每一段弧将原来的每一个区域分成两个
区域，故区域数增加了2，
即增加了原来圆的个数的2倍;当画第三个圆时，应与原来的两个圆共有4个
交点，
圆弧被截成4段，而每段弧又将原来的每个区域分成两个区域，所以区域增加了4，
即原
来圆的个数的2倍，„，同理类推，说明递推公式应该是：
例3 在一个圆周上按下面
规则标上一些数：第一次先把圆周二等分，在两个分
点旁标上12和13，如图(a)。第二次把两段半
圆弧
二等分，在分点旁标上相邻两分点旁所标两数的和，如图(b)，标上。
第三次把4段圆
弧分别二等分，并在4个分点旁边标上两个相邻分点旁所标数的和，
如图(c)，分别标上和
后
，圆周上所有已标的数的和是多少?
http:京翰教育
。如此继续下去，当第八次标完数以
http:小学奥数辅导网
<
br>解：我们一般地设第一次所标的两数分别为a、b，用Sk表示第k次标完后各
分点所标数的和。
如图可见：
原因是这样的：S2是两类分点旁的标数和，一类是原来分点所标数的和S1，
另
一类是新增分点所标数的和，它正好是由原来各分点所标的数向左加一次，又向右
加一次的和
，故新增分点旁所标数的和恰好是原来所有数之和的2倍2 S1，因此有：
(
4)式为递推公式：Sn=3Sn-1在S1=a+b时已解出的表达式。所谓解出，即Sn
直接直接依
赖于n与S1而计算出，不再是Sn依赖于Sn-1，Sn-1又依赖于Sn-2这
样的形式。
http:京翰教育
http:小学奥数辅导网
例4 假设刚出生的雌雄一对小兔过两个月就能生下雌雄一对小兔，此后每月生
下一对小兔。如果养了初
生的一对小兔，问满一年时共可得多少对兔子?
解：我们先退到开始的简单情况来推算，从中归纳出递推关系。如图：
第一个月：只有1对小兔;
第二个月：一对小兔长成一对大兔，但尚不会生殖，仍只有一对兔子;
第三个月：这对大兔生了一对小兔，这时共2对兔子;
第四个月：大兔又生了一对小兔，而上月出生的小兔正在长大，这时共3对兔
子;
第五个
月：这时已有两对大兔可以生殖(原来的大兔和第三个月出生的小兔)，
于是生了两对小兔，这时共有5
对兔子。
„
http:京翰教育
http:小学奥数辅导网
把推算的结果列成一张表：
月一 二 三 四 五 六 七 八 九 十 十十十„„
份一 二 三
数
兔1 1 2 3 5 8 13 21 34 55 89
144 233 „„
子
对
数
由表中可见满一年时可得144对兔子。
如果要算的时间长，这种方法就有困难了，现在我们来找递推关系。
用{Un｝表示第n个月时的兔子对数，则：
{Un｝：1，1，2，3，5，8，13，21，34，„，
容易发现递推公式是：
现在说明这个递推公式是正确的。因为第n个月时的兔子对分两类，一类是第
n-1个月时
的兔子对，另一类是当月新生的兔子对，而这些小兔对数恰好是第n-2
个月时的兔子对数Un-2。
有了上面的递推公式就可以写出{Un｝的第12项为
144对，这正是本题要求的
满一年时的小兔总对数。
数列{Un｝称为斐波那契数列(
Fibonacci,1170～1250，是意大利数学家)。由于
数列{Un｝具有许多重要的奇特
性质，因而受到数学家们的极大关注，并把数列{Un｝
取名为斐波那契数列。
例5 传
说在印度的佛教圣地贝拿勒斯圣庙里安放着一个黄铜板，板上插着三根
宝石针，在第一根宝石针上，从下
到上穿着由大到小的64片中心有孔的金片，每天
都有一个值班僧侣按下面规则移动金片：把金片从第一
根宝石针移到其余的宝石针
上。要求一次只能移动一片，而且小片永远要放在大片的上面。当时传说当6
4片金
片都按上面的规则从第一根宝石针移到另一根宝石针上时，世界将在一声霹雳中毁
灭。所
以有人戏称这个问题叫“世界末日”问题(也称为“Hanoi塔”问题)。当然，
移金片和世界毁灭并
无联系，这只是一个传说而已，但说明这是一个需要移动很多
很多次才能办到的事情。解这个问题的方法
在算法分析中也常用到。究竟按上述规
则移动完这64片金片需要移动多少次呢
http:京翰教育
http:小学奥数辅导网
解：设有n片
金片，把从第一片金片至第k片金片按题目要求由第一根宝石针
移到另一根宝石针共需ak次。
先对4片金片的简单情形，用下列的几组图来表示移动过程中的各种状态，并
计数，归纳出递归关系式
。
这节的前几个例子都是“退”到简单的特殊情况来归纳出一般规律，在这个例
子里，我们将先用一般推理得出递推公式，再以n=64代入，便可解决我们这个例题。
这种从一般到
特殊来解决问题的方法也是数学上的一种常用方法。
http:京翰教育
http:小学奥数辅导网
我们可以这样来想：为了移动第n片到第Ⅲ根
宝石针上，我们必须先把它上面
的n-1片按题目的规则采用某种程序移到第Ⅱ根宝石针上，这需要移动
an-1次，然
后才能把最下面第n片(最大的)，移到第Ⅲ根宝石针上。最后再经过an-1次才能把
第Ⅱ根宝石针上的n-1片金片按上面规则采用同样程序移到第Ⅲ根宝石针上。因此
把n片金片
按题中的规则全部移到另一根宝石针上共应移：
这就是递推公式。（五）
为了求得 n=64 时 a64的值，我们当然不能一次次地由a1=1,a2=3,a3=7,„直
到算出a64。现在我们设法把递推公式(5)变形为可以直接计算a64的形式。
a64是一个非常大的数，如果按照每移动一片需一秒钟算，把64片金片从一根
宝石针移到另一根宝石针上大约需要5800亿年。
习 题 十 四
1，请你根据下列各个数之间的关系，在括号里填上恰当的数：
(1)1，5，9，13，17，( )。
http:京翰教育
http:小学奥数辅导网
(2)0.625, 1.25, 2.5,
5, ( ).
(3)210,316，422,528，„„，()58。
(4)198，297，396，495，( )，( )。
2，将自然数1，2，3，„，按图
排列，在“2”处转第一个弯，“3”处转第二
个弯，“5”处转第三个弯，„。问哪个数处转第二十个
弯?
3，请用递推方法求出甲、乙、丙、丁四人站成一排照相，共有多少种不同站法?
4，上一段12级楼梯，规定每一步只能上一级或两级，问要登上第12级楼梯共
有多少种不同走法?
5，有10个村庄，用别用A1，A2，A3，„，A10表示，某人从A1出发按箭头方
向绕一圈最后经由 A10再回到A1，有多少种不同走法?
注：每点(村)至多过一次，两村之间，可以走直线，也可走圆周上弧线，但都
必须按箭头方向走。
http:京翰教育