奥数：第十四讲递推方法

《奥数：第十四讲递推方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十四讲递推方法　　递推方法是人们从开始认识数量关系时就很自然地产生的一种推理思想.例如自然数中最小的数是1，比1大1的数是2，接下来比2大1的数是3，…由此得到了自然数数列：1，2，3，4，5，….在这里实际上就有了一个递推公式，假设第n个数为an，则　　an+1=an+1　　即由自然数中第n个数加上1，就是第n+1个数。由此可得　　an＋2=an＋1＋1，　　这样就可以得到自然数数列中任何一个数　　再看一个例子：例1平面上5条直线最多能把圆的内部分成几部分？平面上100条直线最多能把圆的内部分成几部分？　　解：　　假设用ak表示k条直线最多能把圆

2、的内部分成的部分数.这里k＝0，1，2，….如图可见。　　a0＝1　　a1=a0+1＝2　　a2=a1＋2=4　　a3=a2＋3=7　　a4=a3+4＝11　　…　　归纳出递推公式an＋1＝an+n.（1）　　即画第n＋1条直线时，最多增加n部分.原因是这样的：第一条直线最多把圆分成两部分，故a1＝2.当画第二条直线时要想把圆内部分割的部分尽可能多，就应和第一条直线在圆内相交，交点把第二条直线在圆内部分分成两条线段，而每条线段又把原来的一个区域划分成两个区域，因而增加的区域数是2，正好等于第二条直线的序号.同理，当画第三条直线时，要想把圆内部分割的部

3、分数尽可能多，它就应和前两条直线在圆内各有一个交点.两个交点把第三条线在圆内部分成三条线段.而每条线段又把原来一个区域划分成两个区域.因而增加的区域部分数是3，正好等于第三条直线的序号，….这个道理适用于任意多条直线的情形.所以递推公式（1）是正确的.这样就易求得5条直线最多把圆内分成：　　a5=a4+5＝11=5＝16（部分）。　　要想求出100条直线最多能把圆内分成多少区域，不能直接用上面公式了，可把上面的递推公式变形：　　∵an=an-1+n=nn-2＋（n-1）＋n　　=an-3+（n-2）＋（n-n）+n　　　　　　　公式（2）也称为数列1

4、，2，4，7，11，16，…的通项公式.　　一般来说，如果一个与自然数有关的数列中的任一项an可以由它前面的k（≤n-1）项经过运算或其他方法表示出来，我们就称相邻项之间有递归关系，并称这个数列为递归数列.如果这种推算方法能用公式表示出来，就称这种公式为递推公式或递推关系式.通过寻求递归关系来解决问题的方法就称为递推方法.许多与自然数有关的数学问题都常常具有递推关系，可以用递推公式来表达它的数量关系.如何寻求这个递推公式是解决这类问题的关键之一，常用的方法是“退”到问题最简单情况开始观察.逐步归纳并猜想一般的速推公式.在小学生阶段，我们仅要求学生能拨

5、开问题的一些表面现象由简到繁地归纳出问题的递推公式就行了，不要求严格证明.当然能证明更好.所谓证明，就是要严格推出你建立的关系式适合所有的n，有时，仅仅在前面几项成立的关系式，不一定当n较大时也成立。例2平面上10个两两相交的圆最多能将平面分割成多少个区域？平面上1993个圆最多能将平面分割成多少个区域？　　解：设平面上k个圆最多能将平面分割成ak部分.我们先“退”到最简单的情形.如图可见　　a1=2，a2=4＝2＋2×1，　　a3＝8=4＋2×2，　　a4=14=8+2×3，　　…　　an=an-1+2（n-1）.（3）　　（3）是这个问题的递推公

6、式.再把它变形为当n较大时也能方便求出结果的公式：　　an＝an-1+2（n-1）　　＝an-2+2[（n-2）+（n-1）]　　＝an-3＋2[（n-3）+（n-2）+（n-1）]　　＝…=a1+2（1+2+3+…+n-2+n-1）　　　　∴a10=102-10+2=92（个），　　a1993=19932-1993＋2=3970058（个）。　　关于这个递推公式成立的正确性分析与例1完全类似.比如，第一个圆显然将平面分为两个区域；当画第二个圆时，应与原来的一个圆有两个交点，即被第一个圆截成两段弧，而每一段弧将原来的每一个区域分成两个区域，故区域数增

7、加了2，即增加了原来圆的个数的2倍；当画第三个圆时，应与原来的两个圆共有4个交点，圆弧被截成4段，而每段弧又将原来的每个区域分成两个区域，所以区域增加了4，即原来圆的个数的2倍，…，同理类推，说明递推公式应该是　　an=an-1+2（n-1）。例3在一个圆周上按下面规则标上一些数：第一次先把圆周二等分，三次把4段圆弧分别二等分，并在4个分点旁边标上两个相邻分点旁所去，当第八次标完数以后，圆周上所有已标的数的和是多少？　　解：　　解：我们一般地设第一次所标的两数分别为a、b，用Sk表示第k次标完后各分点所标数的和.如图可见　　S1＝a＋b，S2＝S1+

8、2S1＝3S1＝3（a＋b）。　　原因是这样的：S2是两类分点旁的标数和，一类是原来分点所标数的和S1，另一