第三章递推关系

1、第三章第三章 递推关系递推关系recurrence relationrecurrence relation1 1 差分差分差分差分02110( )( )(1)( )0,1,( )( )k( )(1)( )( ).nkkknf nf nf nf nnf nf nf nf nf nf n 定定义义差差分分) )设设是是任任一一数数列列，令令一一级级差差分分二二级级差差分分级级差差分分通通常常称称为为零零级级差差分分， 叫叫差差分分算算子子00 ( ) ( )(1)0,().(2)( ( )( )( )( ).(3)( ( )( )(1)( )( )( )nnf ng nCCf ng nf ng n

2、f n g nf ng ng nf n 定理设和是两个数列，则定理设和是两个数列，则为常数为常数11( )();(2)( )( ).kkkEEE f nf nkIII f nIf nf n 定义 （）称算子 为移位算子，若 满足定义 （）称算子 为移位算子，若 满足称算子 为恒等算子，若 满足）=称算子 为恒等算子，若 满足）=(1);(2),.IIEI EI 定理设 是差分算子、移位算子或是恒等算子，则定理设 是差分算子、移位算子或是恒等算子，则牛顿公式牛顿公式00000.(1)(),(0,1,2,);(2)()( 1),(0,1,2,)nnnjjnnnnjjjEIInEInjnEIEnj

3、约约定定：定定理理（牛牛顿顿公公式式）( )3 ,( )1nkf nf nk例设求例设求0( 1)sin()nn kknkxk 例求和例求和( )sin()f kkx 解令解令00( 1)sin()( 1)( )nnn kn kkknnkxf kkk 则则0( 1)(0)nn kkknE fk ()(0)(0)nnEIff ()( )2 sinsin22nnnxn xf kkx 通过归纳法通过归纳法()(0)2 sinsin22nnnxn xf 故故0( 1)sin()()2 sinsin22nn kknnnkxkxn x 即即多项式的差分多项式的差分( )(1)( )( )0.kkf nnm

4、 mkmf nnmkkmf n 定定理理设设是是 的的次次多多项项式式，则则当当时时，是是 的的次次多多项项式式；当当时时，00( )1( )(0).1nmjkjf nnmnf kfj 定理设是 的次多项式，则定理设是 的次多项式，则00( )(0)nnkkkf kE f 0()(0)nkkIf 00(0)nkjkjkfj0(0)nnjjkjkfj 01(0)1njjnfj 01(0)1mjjnfj 0(1)(2).nkk kk 例求和例求和008300822814600(1)(2)( )nnkkk kkf k301(0)1jjnfj 43211151586344646nnnnnn练习练习21

5、311.2.nknkkk 1( )( )( ).kkf nf nf nnk 定理如果不恒等于零，而定理如果不恒等于零，而恒等于零，则是 的 次多项式恒等于零，则是 的 次多项式1010( )( ) ( )( )1.kknnnif nf nf nnsf ink 推论如果不恒等于零，而推论如果不恒等于零，而恒等于零，则数列的前 项和恒等于零，则数列的前 项和是 的一个次多项式是 的一个次多项式0 ( )51,3,7,13,21( )nf nf nn 例试求一数列，使其前 项依次是例试求一数列，使其前 项依次是，其通项是 的多项式且次数最低.，其通项是 的多项式且次数最低.1371321246822

6、200解差分表为解差分表为0( )(0)(0)nniinf nE ffi 20(0)iinfi 2(0)(0)(0)2nfn ff 212(1)1nn nnn零的差分零的差分0|mrmrnOn 定定义义令令称称为为零零的的差差分分. .1,( 1)mmrm krkm rmOkk 定理设都是正整数，则定理设都是正整数，则()mrmrnEIn证明证明0( 1)mm kkrkmE nk 0( 1)()mm krkmnkk 0( 1)mmrm krkmOkk 所以所以组合意义：把组合意义：把r件相异物分给件相异物分给m个人，使得每人至少个人，使得每人至少分得一件物件的不同分配方法数分得一件物件的不同分

7、配方法数.11,()mrmrmrm rOmOO 定理设都是正整数，则定理设都是正整数，则!.mmmOm推论设 为正整数，则推论设 为正整数，则31nkk 例求例求3331111njkjnkOj 3233322111234(1)4nnnOOOn n 2 2 递推关系递推关系递推关系的建立和迭代解法nn例平面上有 条直线，其中无两线平行也无三线例平面上有 条直线，其中无两线平行也无三线共点，求平面被这 条直线分成多少个不连通的区域.共点，求平面被这 条直线分成多少个不连通的区域.1122nnaanna (1)112nn nan (2)(2)m mn n例用种颜色去涂1棋盘，每格涂例用种颜色去涂1棋

8、盘，每格涂一种颜色，相邻格子异色，首末两格也异色，求不同一种颜色，相邻格子异色，首末两格也异色，求不同的涂色方法数.的涂色方法数.112(1)3(1)nnnaam mnam m (1)( 1) (1)2nnnammn 常系数线性齐次的递推关系常系数线性齐次的递推关系121122,0, ().kknnnkn ka aakaua ua ua unkk 定定义义设设是是 个个常常数数且且则则递递推推关关系系称称为为 阶阶常常系系数数线线性性齐齐次次递递推推关关系系011220 ()(0,1,2,).nnnnnkn knnnnbba ba ba bnkbubn 如如果果数数列列满满足足，则则称称数数列

9、列或或是是递递推推关关系系的的一一个个解解01101122001111, ,.knnnnnkn kkkkb bbvua ua ua uvb vbvb 定理任意给出 个常数有且仅有定理任意给出 个常数有且仅有一个数列它是递推关系一个数列它是递推关系的解，且满足条件的解，且满足条件特征方程没有重根的常系数特征方程没有重根的常系数线性齐次递推关系的解法线性齐次递推关系的解法12121112200.kkkkknnnkn kxa xa xaxaua ua ua u 定定义义方方程程称称为为递递推推关关系系 的的特特征征方方程程，它它的的根根称称为为递递推推关关系系的的特特征征根根1122 .nnnnnk

10、n kququa ua ua uq 定理设 是非零复数，则是递推关系定理设 是非零复数，则是递推关系一个解当且仅当 是递推关系的特征根一个解当且仅当 是递推关系的特征根11221( )(1,2, ) (1,2, ) ( )(0,1,2,).ninnnkn kisniiiug nisua ua ua uc isuc g nn 定理设都是递推关系定理设都是递推关系的解，为任意常数，则的解，为任意常数，则也是递推关系的解也是递推关系的解112212112212 , ,.nnnkn kknnnnkkkua ua ua ukq qquc qc qc qc cc定理如果递推关系定理如果递推关系的 个特征根

11、彼此相异，则的 个特征根彼此相异，则是递推关系的通解，其中为任意常数是递推关系的通解，其中为任意常数01212301,2,0 22(3),.nnnnnnuuuuuuunu 例已知：且例已知：且求数列的通项公式求数列的通项公式32220 xxx特征方程特征方程1, 1,2 特征根特征根123( 1)2nnnuccc通解为通解为212( 1)233nnnu 由初始条件解得由初始条件解得5135130,1,2,22.nnnnana例设例设试求出关于的一个递推关系式试求出关于的一个递推关系式12513513,22nnxx令令12125,3xxx x则则212530 xxxx即和是的两个根.即和是的两个

12、根.1253nnnaaa于是于是2211112(0)133.nnnan例求证能被整除例求证能被整除121 1112 144nnna 1215515842nnnnaaaan可以证明满足递推关系可以证明满足递推关系01133|,133|aa因为因为133|nan 所以所以特征方程有重根的常系数线性特征方程有重根的常系数线性齐次递推关系的解法齐次递推关系的解法01( )( )( ),( )( )( )( )kkf xxf xxfxf xf xf xf x 符符号号设设是是 的的多多项项式式，令令令令，. .( )0( )0(2)( )0(01).jf xxqf xm mqf xmjjm 定理设是 的

13、多项式，是方程定理设是 的多项式，是方程的重根，则 是方程的重根，则 是方程的重根的重根( )()( )( )mf xxqh xxqh x证明其中不整除证明其中不整除1( )()( )() ( )mf xx xqmh xxq h x 1122(2) (0,1,2,1).nnnkn kjnnqua ua ua um mun qjm定理设 是递推关系定理设 是递推关系的重特征根，则的重特征根，则都是解都是解1( )0kkk iiif xxa x 证明特征方程为证明特征方程为( )( )()n kqf xmqxf x nkm 是的重根是的重根是的重根是的重根( )0( )0(01)jn kjn kq

14、xf xmjxf qjm 所以是的重根，即所以是的重根，即11( ) ()kjn kjnn iiikjnjn iiixf xxa xn xa nix 又又11221212123121122 ,(1,2, )( )(1,2, ), ( )( )( )iiinnnkn ktiieiiiiieiiiennnnttua ua ua utq qqq iteh ncc nc nc nitcccuh n qh n qh n q 定理设递推关系定理设递推关系有 个相异的特征根其中有 个相异的特征根其中是 重根，令是 重根，令其中是任意常数，则递推关系的通解为其中是任意常数，则递推关系的通解为123401238

15、22249(4)1,3,5,5.nnnnnaaaaanaaaa 例解递推关系例解递推关系两类常系数线性非齐次两类常系数线性非齐次递推关系的解法递推关系的解法121122011220,0,( )( )( ),kknnnkn knnnnnkn knna aakaf nnua ua ua uf nnkkbba ba ba bf nnkb 定定义义设设是是 个个常常数数，是是以以非非负负整整数数 为为自自变变量量的的实实函函数数，则则递递推推关关系系称称为为 阶阶常常系系数数线线性性非非齐齐次次递递推推关关系系. .如如果果树树立立满满足足则则称称数数列列是是递递推推关关系系的的一一个个解解，能能表表

16、示示出出递递推推关关系系全全部部解解的的表表达达式式叫叫做做递递推推关关系系的的通通解解. .112211221122(0,1,2,)( )( ).nnnnnkn knnnnnkn knnnnnnkn kub nua ua ua uf nnkuBua ua ua unkuBbua ua ua uf n 定理设是递推关系定理设是递推关系的一个解，是的一个解，是的通解，则是递推关系的通解，则是递推关系的通解的通解11221122( ),( )(0,1,2,),.nnnnkn knnnkn kinnf ncacaaua ua ua uiua ua ua uf nuAn anA 定理设其中 和 均是非

17、零常数，如果定理设其中 和 均是非零常数，如果是递推关系是递推关系的 重特征根，则递推关系的 重特征根，则递推关系有特解有特解其中 是待定常数其中 是待定常数120127295622,44nnnaaannaa 例解递推关系例解递推关系12562(2)nnnaaann解：递推关系解：递推关系特征方程特征方程2560 xx1223nnnacc通解为通解为因为上特征方程无特征根因为上特征方程无特征根1，因此原递推关系有特解，因此原递推关系有特解,.naAnBAB其中 和 为待定系数其中 和 为待定系数带入原递推关系中，化简得到带入原递推关系中，化简得到111,24AB原递推关系的通解为原递推关系的通

18、解为121112324nnccn通过初值得到通解为通过初值得到通解为1113 2324nnn1230123324634,2,2.nnnnaaaannaaa 例解递推关系例解递推关系12333nnnnaaaa解递推关系的通解为解递推关系的通解为2123nacc nc n因为因为1是上递推关系的三重特征根是上递推关系的三重特征根所以，原递推关系有特解所以，原递推关系有特解3()nAnBAB ，其中 和 为待定系数，其中 和 为待定系数1,5AB代入得到代入得到代入初值得到原递推关系的通解为代入初值得到原递推关系的通解为234417215nannnn 1201432 ,2,8nnnnaaaaa例解递

19、推关系例解递推关系1243nnnaaa解递推关系的通解为解递推关系的通解为123nnacc因为2 不是上递推关系的特征根，因为2 不是上递推关系的特征根，2nnaA 故原递推关系有特解故原递推关系有特解代入得到代入得到4 2nna 通过初值得到通过初值得到15 34 2nnna 3 Fibonacci3 Fibonacci数数0(0)(1)1 ( )(1)(2)(2)( )Fibonacci( )Fibonacci.nfff nf nf nnf nf n 定定义义由由初初始始条条件件及及其其递递推推关关系系所所确确定定的的数数列列叫叫做做数数列列，叫叫做做数数011 ( )115115( )(

20、0)2255nnnf nFibonaccif nn 定理设是数列，则定理设是数列，则020 ( ) ( )nnkf nFibonaccinkf nk 定理设是数列，则定理设是数列，则0( )(2)1nkf kf n 定理定理()( ) ()(1) (1)f nmf n f mf nf m定理定理(20).Fibonaccif例求数例求数4 两类两类Stirling数数一一 第一类第一类Stirling数数01( )1,( )(1)(1)(1,2,)( )( , )( )nnknxxxx xxnnxxnS n kxxStirling 定义设 为实变元，令定义设 为实变元，令称为变元 的 次降阶乘

21、.称为变元 的 次降阶乘.以表示中的展开式中的的系数，以表示中的展开式中的的系数，称为第一类数.称为第一类数.111(1, )( ,1)( , ).(1)S nkS n knS n knk定理定理1( )()( )( )( )nnnnxxnxx xn x 1( ,2)(2).S nn 例求的计数公式例求的计数公式S S1 1(n,k)(n,k)的组合意义的组合意义1( 1)( , ).n kknS n k 定定理理恰恰可可表表示示成成 个个互互不不相相交交的的轮轮换换乘乘积积的的元元置置换换共共有有第二类第二类StirlingStirling数数012( ) ,( ) ,( ) ,( ).nnxxxxx引引理理可可由由线线性性表表示示00(0,1,2, ) ( )( ) ,(0,1,2, )kknnkkkkkkkkab knaxbxabkn 引理设与均为实数，且引理设与均为实数，且则则012( ) ,( ) ,( ) ,( ).nnxxxxx定理可由线性