《高中竞赛教程》教案第31讲__数列的递推

-1-第12讲数列的递推本节主要内容两个基本递推：an＋1＝an＋d，an＝qan；线性递推，二阶或高阶递推的特征方程与特征根；其他递推．1．基本概念：①递归式：一个数列}{na中的第n项na与它前面若干项1na，2na，…，kna（nk）的关系式称为递归式．②递归数列：由递归式和初始值确定的数列成为递归数列．2．常用方法：累加法，迭代法，代换法，代入法等．3．思想策略：构造新数列的思想．4．常见类型：类型Ⅰ：为常数）aaanpnqanpann()0)(()()(11（一阶递归）其特例为：（1）)0(1pqpaann（2）)0()(1pnqpaann（3）)0()(1pqanpann解题方法：利用待定系数法构造类似于“等比数列”的新数列．①形如)(1nqaann的递归式,其通项公式求法为：1111111()()nnnkkkkaaaaaqk[来源:]②形如nnanpa)(1的递归式,其通项公式求法为：3211121(1)(2)(1)nnnaaaaaapppnaaa③形如)1()(1pnqpaann的递推式,两边同除以1np得111)(nnnnnpnqpapa,令nnnbpa则句可转化为①来处理.类型Ⅱ：为常数）babaaaqpqapaannn,(,)0,0(2112（二阶递归）解题方法：利用特征方程qpxx2，求其根、，构造nnnBAa，代入初始值求得BA,．①若p+q=1时，有qaann1)(1nnaa可知}{1nnaa是等比数列，先求得nnaa1，再求出na.②若p+q≠l，则存在α，β满足nnaa1)(1nnaa整理得11)(nnnaaa从而α+β=p，αβ=q，可解出α、β，这样可先求出}{1nnaa的通项表达式，再求出na.注意α、β实质是二次方程qpxx2的两个根，将方程qpxx2叫做递归式nnnqapaa12的特征方程．在数列{na}中，给出a1,a2，且nnnqapaa12，它的特征方程qpxx2的两根为α与β．如果α≠β，则nnnBAa；如果α=β则nnBAna)(，其中A与B是常数，可由初始值a1,a2求出．-2-类型Ⅲ.如果递归数列{an}满足an+1dcabaann,其中c≠0,ad－bc≠0,以及初始值a0≠f(a1),则称此数列为分式线性递归数列.我们称方程dcxbaxx的根为该数列的不动点.若该数列有两个相异的不动点p、q，则}{qapann为等比数列；若该数列仅有惟一的不动点p，则}1{pan是等差数列·5.求递归数列通项的常用方法有：换元法、特征根法、数学归纳法等．A类例题例1一给定函数)(xfy的图象在下列图中，并且对任意)1,0(1a，由关系式)(1nnafa得到的数列}{na满足)N(*1naann，则该函数的图象是()(2005年辽宁卷)（A）（Ｂ）（Ｃ）（Ｄ）分析利用递推式意义及数形结合,分析清楚函数值与自变量的关系，即可判断．解由)(1nnafa，nnaa1，得nnaaf)(，即xxf)(，故选A．例2已知数列1}{1aan中，且a2k=a2k－1+(－1)K,a2k+1=a2k+3k,其中k=1,2,3,……．（I）求a3,a5；（II）求{an}的通项公式．(2004年全国高考题)分析由于给出两个递推关系与奇数项、偶数项有关,因此因从奇数项或偶数项之间的关系入手.解（I）a2=a1+(－1)1=0,a3=a2+31=3．a4=a3+(－1)2=4,a5=a4+32=13,所以，a3=3,a5=13．(II)a2k+1=a2k+3k=a2k－1+(－1)k+3k,所以a2k+1－a2k－1=3k+(－1)k,同理a2k－1－a2k－3=3k－1+(－1)k－1,……a3－a1=3+(－1)．所以(a2k+1－a2k－1)+(a2k－1－a2k－3)+…+(a3－a1)=(3k+3k－1+…+3)+[(－1)k+(－1)k－1+…+(－1)],由此得a2k+1－a1=23(3k－1)+21[(－1)k－1],11yxO11yxO11yxO11yxO-3-于是a2k+1=.1)1(21231kka2k=a2k－1+(－1)k=2123k(－1)k－1－1+(－1)k=2123k(－1)k=1．{an}的通项公式为：当n为奇数时，an=;121)1(232121nn当n为偶数时，.121)1(2322nnna说明这种给出递推关系,求通项公式问题,一般是转化为等差数列或等比数列,或者通过观察、归纳,或者通过顺次迭代,以求通项公式.情景再现1．已知数列{an}满足a1＝1，an＝2an－1＋n－2(n≥2)，求通项an.(2004年四川省高中数学联赛)[来源:]2．设cbxxxf)(（cb,为常数），若21)2(f，且02)(xxf只有唯一实数根（1）求)(xf的解析式（2）令)(,111nnafaa求数列na的通项公式.B类例题例3(1)一次竞赛在n(n＞1)轮中共发了m枚奖章．第一轮发了1枚及余下的m－1枚的71，第2轮发了2枚及余下的71，…，直至第n轮正好发了n枚而没有余下奖章．这个竞赛共包括几轮?一共发了多少枚奖章?(第9届国际数学奥林匹克)(2)把一个圆分成n个不同的扇形(n≥2)，依次记为S1，S2，…,Sn，每个扇形都可以用红、蓝、白三种颜色中任一种涂色，要求相邻的扇形颜色互不相同，问有多少种涂法?分析第(1)题，每一轮发的奖章数具有一定规律，因而可以建立每一轮发的奖章数的关系或每一轮余下的奖章数的关系．第(2)题，设法建立涂法总数的递推关系和求得初始值，进而求得涂法总数．解(1)设竞赛进行了k轮后，余下ak枚奖章．因为第k轮发出奖章数k+17(an－1－k)具有ak＝ak－1－[k+17(ak－1－k)]即ak＝67ak－1－67k且a0=m,an=0.进一步变形为ak+6k－36=67[ak－1+6(k－1)－36]-4-从而an+6n－36=(a0－36)n)76(=(m－36)n)76(即an=(m－36)n)76(－(6n－36),又因为an=0,故(m－36)=(n－6)167nn而n－6＜6n－1,且7n与6n－1互质,m,n∈N+,故n=6,m=36.因此,这个竞赛共包括6轮,一共发了36枚奖章.(2)设涂法总数为an(n≥2)当n=2时,先对S1涂法色,有3种涂法,继而得S2只有两种涂法,因而a2=6.当时n≥3,S1有3种涂法,S2有2种涂法,S3有2种涂法,…,Sn－1有2种涂法,Sn仍有2种涂法.(不论是否S1与同色),这样共有3×2n－1种涂法,但这3×2n－1种涂法分为两类：一类是Sn与S1同色,认为Sn与S1合为一个扇形,此时涂法有an－1种涂法；另一类是Sn与S1不同色,此时涂法有an种涂法.因而有an+an－1=3×2n－1(n≥3)令pn=an2n,则2pn+pn－1=3(n≥3)于是有1np=)1(211np,(n≥3)p2=a222从而有1np=)1()21(22pn=121n于是1np121n得an=2npn=2n+(－1)n·2(n≥3)但当n=2时也适合上式,故得an=2n+(－1)n·2(n≥2)故共有种an=2n+(－1)n·2(n≥2)涂法说明这类试题经常在全国高中数学联赛及国际数学奥林匹克中出现．这两个问题都是用递推方法解决计数问题，希望读者对这类问题能够进行较为深入的钻研．例4数列{an}定义如下：a1=1，an+1=161(1+4an+na241)，求它的通项公式．分析带根号的部分不好处理，平方会导致较繁的关系式,容易想到作代换：令nbna241解设nbna241,则2412nnba,.51b于是原递推式可化为41(16124121nb2412nb+)nb即(2bn+1)2=(bn+3)2,由于bn、bn+1非负,所以2bn+1=bn+3.故bn+1－3=21(bn－3).所以bn+1－3=(bn－3)(21)n－2即2)21(3nnb-5-月份n123456……An112358……Bn111235……Fn11235813……所以2412nnba=nn212313112说明这是1981年IMO的预选题，解题的关键是换元、转化．例5设{xn}、{yn}为如下定义的两个数列：x0=1，x1=1,xn+1=xn+2xn－1，y0=1，y1=7,yn+1=2yn+3yn－1，(n=1,2,3…)，于是这两个数列的前n项为xn：1,1,3,5,11,21…,yn：1,7,17,55,161,487,….证明：除了“1”这项外,不存在那样的项,它同时出现在两个数列之中.(第二届美国中学生数学竞赛试题)分析本题题均属于线性递归数列问题，可用特征根的方法来解决．解数列{xn}的通项公式形如nnnCCx21,其中、是数列的特征方程x2=x+2的两根,即1,2,故nnnCCx)1(221.由x0=1,x1=1得C1=23,C2=13,[来源:]所以nx23×2n+13(－1)n=13[2n+1+(－1)n]同理可得数列的{yn}通项公式为yn=2×3n－(－1)n.用反证法证明两个数列无其它公共项.假设xm=yn,即13[2m+1+(－1)m]=2×3n－(－1)n,则2(3n+1－2m)=(－1)m+3(－1)n①若奇偶性相同,则①式右边为4或－4.左边=2(奇－偶)=2×奇数,故左边不是4的倍数,因此左边不等于右边.同理若m、n奇偶性不相同时左边也不等于右边.说明在求得特征方程的根以后，要依据根的重数正确写出数列通项的一般表达式，再根据初始值求得待定系数的值．链接菲波纳契数列(Fibonacci)数列的由来:Fibonacci数列的提出，当时是和兔子的繁殖问题有关的，它是一个很重要的数学模型。这个问题是：有小兔一对，若第二个月它们成年，第三个月生下小兔一对，以后每月生产一对小兔，而所生小兔亦在第二个月成年，第三个月生产另一对小兔，以后亦每月生产小兔一对，假定每产一对小兔必为一雌一雄，且均无死亡，试问一年后共有小兔几对？对于n=1，2，……，令Fn表示第n个月开始时兔子的总对数，Bn、An分别是未成年和成年的兔子（简称小兔和大兔）的对数,则Fn=An+Bn根据题设，有显然，F1=1，F2=1，而且从第三个月开始，每月的兔子总数恰好等于它前面两个月的兔子总数之和，于是按此规律我们得到一个带有初值的递推关系式：1F1,FZ)n3,(nFFF212-n1-nn若我们规定F0=1，则上式可变为1F1,FZ)n2,(nFFF102-n1-nn这就是Fibonacci数列的通常定义，也就是数列1，1，2，3，5，8，13，21，34，55，89，……，-6-这串数列的特点是：其中任一个数都是前两数之和.它的通项是Fn=51[(251)n+1－(251)n+1]，由法国数学家比内（Binet）求出的.证：∵菲波纳契数列是一个2阶的线性齐次递推关系，它的递推方程是x2－x－1=0，特征根是251∴通解是Fn=C1(251)n+C2(251)n代入初值来确定C1、C2，得方程组125125112121CCCC解这个方程组得C1=51251,C2=51251∴原递推关系的解是Fn=51[(251)n+1－(251)n+1]例6数列{an}满足a0=1，23645721nnnaa