《专题4.4 递推和归纳署+盛锦.docx》由会员分享，可在线阅读，更多相关《专题4.4 递推和归纳署+盛锦.docx（6页珍藏版）》请在课桌文档上搜索。
1、4. 4递推和归纳署递推和归纳是处理与正整数相关的命题时常用的方法.其基本思想是从小的推出下一个或者大 的成立.强调前后者之间的联系.例1已知有2个人，如果每两人一组，试问：有多少种不同的分组方式？【解】先取定一个人，他与其余2-1个人均可组成一组，故有2-1种方式；再考虑剩下2一2 人,取定一人后，他有2-3种方式组队.依此类推，于是共有（2-l）x（2-3）Xl即（2-1）! 种不同的组队方式.例2已知某台阶有10级，每次可以向上跨一级或两级台阶.试问：走完10级台阶有多少种走法？【解】不妨设走完级台阶有凡种走法，则要走到第级，要么从第级上一级，要么从第 一2级跨两级.于是可以得到递推关系
2、式：q=4+4（n3）,而4=1, =2,所以 % =6+4 =3, 4 = a2 + 3 = 5 , a5 =a3+a4 = 8, 4 =34, a9=55 , a10 = 89 ,故走完 10级台阶有89种走法.例3圆周上两个点将圆周分成两半，在这两点玉写上数1.然后将两段半圆弧等分土写上相邻两数 之和；再把四段圆弧分别等分，仍然在分点上写上相邻两数之和.如此下去，问：第六步后，圆周上所 有点之和是多少？【解】不妨设第步后，圆周上所有点之和为&考虑从第-1步到第步的过程：添上去的新数都 等于相邻两数之和，且原来的数都被计算了两遍，即新数之和为2i，所以4=为+2,=34, 又4=2,所以4
3、=6, 3=18, 4=54, 5=162, 6 =486,即第六步后，圆周上所有数字之和 为 486.例4四人进行篮球训练，互相传球.要求每人接球后马上传给别人，开始由甲开球，并作第一次 传球.第五次传球后，球又回到甲手中.试问；有多少种不同的传球方式？【解】设第次传球后，球回到甲手中的传球方式有勺种，考虑前-1次传球，每次传球都有三种 选择，故所有传球方式共有3T种.注意到，只有第次传球后，球不甲手上，那么第次才能传给 甲，所以，q=3T-,（九2）由4=0,可依次算得出=3-q=3, a3=32-a2=6, 4=33-6 = 21, 5 = 34 -a4 = 60 ,所以共有60种可能的
4、传球方式.【注】从上面的处理可看出只有恰当建立前后者之间的关系式才能方便地用递推方法解决.例5条直线最多能把平面分成多少部分？【解】不妨设条直线最多能把平面分成份，考虑第条直线，它最多与前面-1条均相交，那 么它被分成了段，被分成的每一条线段(或者射线)，都可以将平面多分出一个部分，所以 an=an-+n 于是 4.1 =4.2+( T)，4.2=4-3+5-2)，% =。2 + 3，生=+ 2 ,将上面一1个式子相加，有=q+2 + 3+ ，结合q =2,可得rt=2 + 2 + 3 + . +二犷十十2 ,所以条直线最多可以将平面分成0三士2个部分.22例6用1或2两个数字写位数，其中任意
5、相邻的两个位置不全为1.记这样的位数的个数为 /().求F(IO)的值.【解】符合条件的位数可以分为如下两类：(1)首位为2,则以后的-1位符合条件的个数为/(九一1)；(2)首位为L则第二位必为2,之后-2位符合条件的个数为了(一2),于是/() = /(-一2).且/=2, /(2) = 3,所以可以递推得到/(10) = 144.【注】这里 与例2样，均为斐波那契数列.例7已知有排成一行的10个方格，现用红、黄、蓝三色涂每个格子，每格涂一色，要求任意相邻 的格子不同色，且首尾两格也不同色.试问：有多少种不同的涂法？【解】直接考虑一般情形，不妨设一行个格子的涂法有凡种，那么显然q=3, 4
6、=6, %=6,当4时，将格子编号，第1个格与第一 1格不相邻.(1).若第-1格与第1格颜色不同，此时第格只有一种颜色可以选择，且前-1个格子满足首 尾两个不同色，故这种情况有种涂法.若第-1格与第1格颜色相同，此时第-2格与第1格颜色不同，于是前-2个格子满足首尾 两个不同色，于是前-2个格子有。吁2种涂法，而另一方面，第个格子此时有两种选择，于是这种情 况有2,种涂法.故4=i+4_2(N4),递推可知QK)= 2+ 2.例8空间n个平面最多可将空间分成多少个部分？【解】显然，当这个平面满足以下条件时，所分割的部分数是最多的：1 .这，个平面两两相交；2 .没有三个以上的平面交于一点;3
7、 .这个平面的交线任两条都不平行.由于一般情况不易考虑，不妨从简单的、特殊的情况入手来寻找规律.设个平面分空间的部分数 为见 ,易知：当 =1时，an = 2 ；当 =2时，。“=4；当九=3时，%=8；当 =4时，情况有些复杂，我们以一个四面体为模型来观察，可知二 15；从以上几种情况，很难找串般性的规律，而且当的值继续增大时，情况更复杂.那么，我们把问 题再进一步简单化，将空间问题退化到平面问题：条直线最多可将平面分割成多少个部分？（这条 直线中，任两条不平行，任三条不相交同一点），设条直线最多可将平面分割成个部分，那么由例 5的结论知么=g （ + + 2）.回到原问题，用类似思路来解决
8、空间的问题.设4个平面将空间分割成4个部分，再添加上第Z + 1个平面，这个平面与前Z个平面相交有4条交线，这左条交线，任意三条不共点，任意两条不平 行，因此这第A: + 1个平面就被这左条直线分割成4个部分.而这4个部分平面中的每一个，都把它所 通过的那一部分空间分割成两个较小的空间.所以，添加上这第左+ 1个平面后就把原有的空间数增加4 个部分.由此得递推关系式：4.I =4+4，即一对=仇.当A = I, 2,九一1时，我们得到如下九一 1个关系式：a2-ai = Zj1 , ai-a2=b2,4 一% = 4I,将这一1个式子相加，得=q+（4+4+d）.因为么=；（川+ + 2）且q
9、=2,所以%=2g(+l + 2) + g(2?+2 + 2)+ +；(- 1)? +一 1 + 2(7-1) + 2(i-1)n142 (n-l)(2n-l) + -i(n-l)= + 5_1)仆+ 尸+： + 6综上所述，n个平面最多可将平面分割成+5 + 6）个部分.练习4. 41 .平面上5个圆最多能把平面分成多少部分？2 .设41, 2，“这个数取值为O或 1记满足4%, a2ai, a3a4f a4 a5 的序列（q,q, ,4）个数为/（）.求/（10）的值.3 .求满足以下条件的数列的个数：项数为6,每一项为0或1或2,并且0不能为2的前一项也不 能为2的后一项.4 .平面上有
10、100条直线，其中20条互相平行.问这100条直线最多能将平面分成多少部分？X = 82, y = 24, z = 44,X = 85, , J = 20, z = 45,5 .已知：，,A3C内部有2011个点，以顶点A、B、C和这2011个点为顶点能把原三角形分割成 多少个小三角形？X = 73, fx = 76, x = 79,y = 36, y = 32, 易知 fJV + -2 J= （x） + 6.所以若整数。可以表示为/（x）的形式，那么。+ 6攵（4为自然数）也可以表示为/（x）的形式.当0x,时，/() = 0:当x;时，/(x) = l ：当;x;时，/(x) = 2;当g
11、x 时,/（力=3；且=所以16中，有4个数可以表示为f(x)的形式.而2004 = 6x334,所以共有334x4 = 1336个 数可以表示成2司+ 4司+6司的形式.练习4. 41 . 一个圆最多分成两个部分；两个圆最多分成四个部分；三个圆最多分成八个部分.现在考虑第四个圆.要使分成的部分尽量多，第四个圆必须与前三个都有两个交点，因此有6个交 点，将第四个圆周分成6段，每段圆弧都可以增加一个部分.所以四个圆最表可以分成8+6 = 14份.同理，五个元最多可以分成14 +8 = 22个部分【注】事实上，用例5的方法，也可以算出个圆最多可以将平面分成的份数的情形.这里a” = 2l2+22+
12、32+ +(-l)2 = 2 一 + 2 .2 .显然，/(1) = 2, /(2) = 3, /(3) = 5.记当”=0时，满足条件的序列数为g()，当为 =1时满足条件的序列数为/?().则 f() = g () + () -当一为奇数时,有6() = (九一 1), g(7?) = /(77-1)：当为偶数时，有g(九) = g(- 1)，(w) = (-1).于是可以得到为奇数时，5) = g() +力() = /(h-1) + (2-1) = /(-l)/(n-2)；当几为偶数时，/() = g() +力() = g(1) + /(/?-1) = /(w-2)+/( 1).故/()
13、为斐波那契数列，于是/(10) = 144.3 .考虑一般情形，记满足条件且项数为的数列个数为，.其中以0为末项的数列有与个，以1 为末项的数列有a个，以2为末项的数列有C“个.于是=4+a+f容易发现 an = % + b,f , bn = a”+ ,1 + CCfl= .1 + %.所以力一 2力T 一 力_2 = 0 (因为 = an-2 +bn-2 + %-2 = -2)而工=3,人=7,所以6=2394 .首先，20条平行直线将平面分成了 21份.设另外加上左条直线，连同这20条，将平面最多分成 4个部分.考虑加上第左+ 1条直线时的情况.它与前20 +左是条有20+左个交点，所以%
14、=%+21 +&， =_+21 + (攵-1), %=_2+21 + (A-2)，%=q+21 + l,将上述后2-1个式子相加，有必=q+21(A-l) +乂又q=42,所以I 41cli =+ A + 21 ,故,0 = 4861 .习题解答【注】这里与前面例题不同的地方仅仅在于递推开始时初始状态稍有改变，基本方法仍然相同.5.设内部有个点时能分割成4个小三角形.考虑从-1个点到个点的过程.(1)如果第个点在某小三角形的内部，那么将这个点与小三角形三顶点相接，一分为三，故增加了 两个；(2)如果第个点在某两个小三角形的公共边上，则这两个小三角形的顶点与这个点相连，分别将它 们都一分为二，故也增加了两个.于是4=%t+2,且 = 1,所以%=2 + 1.当 = 2011时，ll =4023,即能把原三角形 分割成4023个小三角形.
