1、第十四讲 递推方法递推方法是人们从开始认识数量关系时就很自然地产生的一种推理思想.例如自然数中最小的数是 1，比 1 大 1 的数是 2，接下来比 2 大 1的数是 3，由此得到了自然数数列：1，2，3，4，5，.在这里实际上就有了一个递推公式，假设第 n 个数为 an，则a n+1=an+1即由自然数中第 n 个数加上 1，就是第 n+1 个数。由此可得a n2=a n 11，这样就可以得到自然数数列中任何一个数再看一个例子：例 1 平面上 5 条直线最多能把圆的内部分成几部分？平面上 100 条直线最多能把圆的内部分成几部分？解：假设用 ak表示 k 条直线最多能把圆的内部分成的部分数.这
2、里k0，1，2，.如图可见。a 01a 1=a0+12a 2=a12=4a3=a 23=7a4=a3+4 11归纳出递推公式 an 1a n+n. （1）即画第 n1 条直线时，最多增加 n 部分.原因是这样的：第一条直线最多把圆分成两部分，故 a12.当画第二条直线时要想把圆内部分割的部分尽可能多，就应和第一条直线在圆内相交，交点把第二条直线在圆内部分分成两条线段，而每条线段又把原来的一个区域划分成两个区域，因而增加的区域数是 2，正好等于第二条直线的序号.同理，当画第三条直线时，要想把圆内部分割的部分数尽可能多，它就应和前两条直线在圆内各有一个交点.两个交点把第三条线在圆内部分成三条线段.
3、而每条线段又把原来一个区域划分成两个区域.因而增加的区域部分数是 3，正好等于第三条直线的序号，.这个道理适用于任意多条直线的情形.所以递推公式（1）是正确的.这样就易求得 5 条直线最多把圆内分成：a5=a4+5 11=516（部分）。要想求出 100 条直线最多能把圆内分成多少区域，不能直接用上面公式了，可把上面的递推公式变形：a n=an-1+n=nn-2（n-1）n=a n-3+（n-2）（n-n）+n公式（2）也称为数列 1，2，4，7，11，16，的通项公式.一般来说，如果一个与自然数有关的数列中的任一项 an可以由它前面的 k（n-1）项经过运算或其他方法表示出来，我们就称相邻项
4、之间有递归关系，并称这个数列为递归数列.如果这种推算方法能用公式表示出来，就称这种公式为递推公式或递推关系式.通过寻求递归关系来解决问题的方法就称为递推方法.许多与自然数有关的数学问题都常常具有递推关系，可以用递推公式来表达它的数量关系.如何寻求这个递推公式是解决这类问题的关键之一，常用的方法是“退”到问题最简单情况开始观察.逐步归纳并猜想一般的速推公式.在小学生阶段，我们仅要求学生能拨开问题的一些表面现象由简到繁地归纳出问题的递推公式就行了，不要求严格证明.当然能证明更好.所谓证明，就是要严格推出你建立的关系式适合所有的 n，有时，仅仅在前面几项成立的关系式，不一定当 n 较大时也成立。例
5、2 平面上 10 个两两相交的圆最多能将平面分割成多少个区域？平面上 1993 个圆最多能将平面分割成多少个区域？解：设平面上 k 个圆最多能将平面分割成 ak部分.我们先“退”到最简单的情形.如图可见a 1=2，a 2=4221，a38=422，a4=14=8+23，a n=an-1+2（n-1 ）.（3 ）（3）是这个问题的递推公式.再把它变形为当 n 较大时也能方便求出结果的公式：a na n-1+2（n-1）a n-2+2（n-2）+（n-1 ）a n-3 2（n-3）+（n-2）+（n-1 ）=a 1+2（1+2+3+ +n-2+n-1）a 10=102-10+2=92（个），a 1
6、993=19932-19932=3970058（个）。关于这个递推公式成立的正确性分析与例 1 完全类似.比如，第一个圆显然将平面分为两个区域；当画第二个圆时，应与原来的一个圆有两个交点，即被第一个圆截成两段弧，而每一段弧将原来的每一个区域分成两个区域，故区域数增加了 2，即增加了原来圆的个数的 2 倍；当画第三个圆时，应与原来的两个圆共有4 个交点，圆弧被截成 4 段，而每段弧又将原来的每个区域分成两个区域，所以区域增加了 4，即原来圆的个数的 2 倍，同理类推，说明递推公式应该是a n=an-1+2（n-1 ）。例 3 在一个圆周上按下面规则标上一些数：第一次先把圆周二等分，三次把 4 段
7、圆弧分别二等分，并在 4 个分点旁边标上两个相邻分点旁所去，当第八次标完数以后，圆周上所有已标的数的和是多少？解：解：我们一般地设第一次所标的两数分别为 a、b，用 Sk表示第 k 次标完后各分点所标数的和.如图可见S 1ab，S 2S 1+2S13S 13（ab）。原因是这样的：S 2 是两类分点旁的标数和，一类是原来分点所标数的和 S1，另一类是新增分点所标数的和，它正好是由原来各分点所标的数向左加一次，又向右加一次的和，故新增分点旁所标数的和恰好是原来所有数之和的 2 倍 2S1，因此有S2=S 1 2S1=3S1，同理类推S3=S 2+2S23S 2=32S1，S432S 1232S
8、132S 1，S n=3n-1S1=3n-1（a b ） （4）（4）式为递推公式：S n3S n-1 在 S1=ab 时已解出的表达式.所谓解出，即 Sn直接依赖于 n 与 S1而计算出.不再是 Sn依赖于 Sn-1，S n-1 又依赖于 Sn-2这样的形式。例 4 假设刚出生的雌雄一对小兔过两个月就能生下雌雄一对小兔，此后每月生下一对小兔.如果养了初生的一对小兔，问满一年时共可得多少对兔子？解：我们先退到开始的简单情况来推算，从中归纳出递推关系.如图：第一个月：只有 1 对小兔。第二个月：一对小兔长成一对大兔，但尚不会生殖.仍只有一对兔子。第三个月：这对大兔生了一对小兔，这时共 2 对兔子
9、。第四个月：大兔又生了一对小兔，而上月出生的小兔正在长大，这时共 3 对兔子。第五个月：这时已有两对大兔可以生殖（原来的大兔和第三个月出生的小兔），于是生了两对小兔，这时共有 5 对兔子。把推算的结果列成一张表由表中可见满一年时可得 144 对兔子。如果要算的时间长，这种方法就有困难了，现在我们来找递推关系。用u n表示第 n 个月时的兔子对数，则u n：1，1，2，3，5，8，13，21，34，。容易发现递推公式是u n=un-1+un-2。现在说明这个递推公式是正确的.因为第 n 个月时的兔子对分两类，一类是第 n-1 个月时的兔子对，另一类是当月新生的兔子对，而这些小兔对数恰好是第 n-
10、2 个月时的兔子对数 un-2。有了上面的递推公式就可以写出u n的第 12 项为 144 对.这正是本题要求的满一年时的小兔总对数。数列u n称为斐波那契数列（Fibonacci，11701250，是意大利数学家）.由于数列u n具有许多重要的奇特性质.因而受到数学家们的极大关注，并把数列u n取名为斐波那契数列.例 5 传说在印度的佛教圣地贝拿勒斯圣庙里安放着个一个黄铜板，板上插着三根宝石针，在第一根宝石针上，从下到上穿着由大到小的 64 片中心有孔的金片.每天都有一个值班僧侣按下面规则移动金片：把金片从第一根宝石针移到其余的某根宝石针上.要求一次只能移动一片，而且小片永远要放在大片的上面
11、.当时传说当 64片金片都按上面的规则从第一根宝石针移到另一根宝石针上时，世界将在一声霹雳中毁灭.所以有人戏称这个问题叫“世界末日”问题（也称为“Hanoi 塔 ”问题），当然，移金片和世界毁灭并无联系，这只是一个传说而已，但说明这是一个需要移动很多很多次才能办到的事情.解这个问题的方法在算法分析中也常用到.究竟按上述规则移动完成 64 片金片需要移动多少次呢？解：设有 n片金片，把从第一片金片至第 k 片金片按题目要求由第 I 根宝石针移到另一根宝石针共需移动 ak次。先对 4 片金片的简单情形用下列的几组图来表示移动过程中的各种状态，并计数，归纳出递归关系式。这节的前几个例子都是“退”到简
12、单的特殊情况来归纳出一般规律.在这个例子里，我们将先用一般推理得出递推公式，再以n=64 代入，便可解决我们这个例题.这种从一般到特殊来解决问题的方法也是数学上的一种常用方法。我们可以这样来想：为了移动第 n 片到第根宝石针上，我们必须先把它上面的 n-1 片按题目的规则采用某种程序移到第根宝石针上，这需要移动 an-1 次.然后才能把最下面第 n 片（最大的），称到第根宝石针上.最后再经过 an-1 次才能把第根宝石针上的 n-1 片金片按上面规则采用同样程序移到第根宝石针上.因此把 n 片金片按题中的规则全部移到另一根宝石针上共应移a n=2an-1+1（次）. （5）这就是递推公式。为了
13、求得 n=64 时 a64的值，我们当然不能一次次地由 a1=1，a 2=3，a3=7 ，直到算出 a64.现在我们设法把递推公式（5）变形为可以直接计算 a64的形式。a n=2an-1+1=2（2a n-21）+1=2 2an-2+21=2 2（2a n-3+1）+2+123a n-322+2 1+1=2 n-1a1 2n-2+2n-3+21=1 2 22+2n-22 n-1，a n2a n-an=2 （1+2+22+2 n-1）-（1+2+2 n-1）=2 n-1，a 642 64-1。a 64是一个非常大的数.如果按每移动一片次需一秒钟算，把64 片金片从一根宝石针移到另一根宝石针上大约需要 5800 亿年。
