递推关系解析课件.ppt

1、1第三章第三章 递推关系递推关系3.1 3.1 基本概念基本概念012012,() (,)0.nninaaaaaa inF aa aa , 对数列一个关于 对数列一个关于和某些的方程式,称为.记和某些的方程式,称为.记定义3.1.1 定义3.1.1 关式关式作作递推系递推系01212, (,),nnnnn kaaaaknkaF aaak ,递推关系式也可这样描述:递推关系式也可这样描述:对数列是某个自然数,对数列是某个自然数,若对所有的均有若对所有的均有则称上式为该数列的 阶递推则称上式为该数列的 阶递推定义 定义 关系式.关系式.2递推关系的分类:递推关系的分类: 递推关系(常数项为零) 递

2、推关系(常数项为零) (1)按常数项分(1)按常数项分递推关系(常数项不为零递推关系(常数项不为零次次次次) )齐齐非齐非齐(2)na 递推关递推关线性线性非线非线系 系 按的运算分按的运算分递推关系递推关系性性(3)na 递递常系数常系数变系变系推关系推关系按的系数分按的系数分递推关系递推关系数数(4) 递递一元一元多元多元推关系推关系按数列的多少分按数列的多少分递推关系递推关系312001111(,) ,nnnn kkkaF aaaadadad () 含有初始条件的递推() 含有初始条件的递推定义3.定义3.关关系称为定解问题,其一般形式为系称为定解问题,其一般形式为题题 定解问定解问1.

3、21.2nkkan注注 一般说来, 阶递推关系需要有 个初始条件一般说来, 阶递推关系需要有 个初始条件 才能确定唯一的解.一个数列的递推关系和 才能确定唯一的解.一个数列的递推关系和 初始条件一起称为数列的.所谓解 初始条件一起称为数列的.所谓解 一个数列的定解问题就是要找出数列通项 一个数列的定解问题就是要找出数列通项 : :定解问定解问 关于 的一 关于 的一题题般表达式。般表达式。4AA,B,CACnnna() 个圆盘按从大到小的顺序依() 个圆盘按从大到小的顺序依次套在柱上,规定每次只能从一根柱子上搬动一次套在柱上,规定每次只能从一根柱子上搬动一个圆盘到另一根柱子上,且要求在搬动过程

4、中不允个圆盘到另一根柱子上,且要求在搬动过程中不允许大盘放到小盘上,而且只有三根柱子可供许大盘放到小盘上,而且只有三根柱子可供使用.求将 个盘子从柱移到柱上所需要搬动使用.求将 个盘子从柱移到柱上所需要搬动圆盘的圆盘的Hanoi塔问Hanoi塔问例例最小次数最小次数题题1 1. .ABC5ABCABCABC61211,1, 3, 3,:A1BACBCnnaannana 解 易知对于搬动圆盘的算解 易知对于搬动圆盘的算 法如下 法如下第一步,将套在柱的上面个盘移到柱上,第一步,将套在柱的上面个盘移到柱上, 需搬动次; 需搬动次;第二步,将柱上最大一个盘移到柱上,只需第二步,将柱上最大一个盘移到柱

5、上,只需 搬动一次; 搬动一次;第三步,再从柱上将 -1个盘移到柱上,也第三步,再从柱上将 -1个盘移到柱上,也 需次. 需次.11121,21 1 nnnnnaaaaaa 于是,得递推关系的定解问题为于是,得递推关系的定解问题为一元非齐次常系一元非齐次常系数线性递推关系数线性递推关系700nnabab例2例2 ()两军打仗,每支军队在 ()两军打仗,每支军队在每天战斗结束时都清点人数,用和 分别表示每天战斗结束时都清点人数,用和 分别表示在战斗打响前第一支和第二支军队的人数,用在战斗打响前第一支和第二支军队的人数,用和分别表示第一支和第二支军队在第n天战斗和分别表示第一支和第二支军队在第n天

6、战斗结束时的人数,假设一支军队每天所减少的人数结束时的人数,假设一支军队每天所减少的人数与另一支军队在每天战斗开始前与另一支军队在每天战斗开始前蓝开斯特战斗蓝开斯特战斗的人数的人数方程方程成比例.成比例.11111111 nnnnnnnnnnnnnaaAbaaAbbbBabbBa即即则两支军队在第 天战斗结束时的人数满足递推则两支军队在第 天战斗结束时的人数满足递推关系式:关系式:二元线性递二元线性递推关系组推关系组8 nnabcnaana、 、 、在信道上传输仅用这3个字母组成的在信道上传输仅用这3个字母组成的长度为的字母串，规定有两个连续出现的串长度为的字母串，规定有两个连续出现的串不能传

7、输，用表示这个信道允许传输长度为 的不能传输，用表示这个信道允许传输长度为 的字母串的个数，试建立序列的字母串的个数，试建立序列的例3 例3 递推关系.递推关系.123,8,3.a,b,c,aaab ac ba bb bc cacb ccan 解 长度为1的字母串有所以长度为解 长度为1的字母串有所以长度为2且没有两个 相邻的字母串有2且没有两个 相邻的字母串有所以下设所以下设22,nnabcaana 2 2 如果字母串中第一个字母是那么第二个字母 如果字母串中第一个字母是那么第二个字母只能是 或其余的字母可以有种方式选择, 因此只能是 或其余的字母可以有种方式选择, 因此以 开头的长为 的字

8、母串有个.以 开头的长为 的字母串有个.9121222, 3 3, 8 nnnaaanaa 于是得递推关系于是得递推关系111nn-n-babnacna 如果字母串中第一个字母是 ,则其余字母 如果字母串中第一个字母是 ,则其余字母可以有种选择,所以以 开头的长为 的字母可以有种选择,所以以 开头的长为 的字母串有个, 同样, 以 开头的长为 的字母串有串有个, 同样, 以 开头的长为 的字母串有个.个.1020 nknknnkarka 设 设求所满足的递求所满足的递例4例4推关系.推关系.2,12 122nnmnnm 解 当 为偶数时,令则解 当 为偶数时,令则1012220mmkkmnkk

9、mkmmkmarrrkkm 于是于是1111002122mmkjkjmkmjrrrkj112212101mkmkmmkmkmrrkkm 111121212101mmkkmkkmmkmkmrrrkkm 12100212211mmkjmkjmkmjmrrrrkjm 121222001212nnkjkknnnknjrrrkjaran当 为奇数时,类似地可证上述递推关系成立.当 为奇数时,类似地可证上述递推关系成立.1201, 2 1, 1 nnnnaaaranaa 因此, 所满足的递推关系是因此, 所满足的递推关系是133.2 3.2 常系数线性递推关系常系数线性递推关系1122112212 0 (

10、0) ( ) (0),( )nnnkn kknnnkn kkkac ac ac acac ac ac af ncc cckkf n阶常系数线性递推关系:阶常系数线性递推关系:阶常系数线性递推关系:阶常系数线性递推关系:齐次齐次非非其中是常其中是常齐次齐次数为自由项.数为自由项. 解此类递推关系的一种简单而有效的方法 解此类递推关系的一种简单而有效的方法是是特征根法特征根法. .143.2.1 3.2.1 解的性质解的性质(1)(2)1122(1)(2)11 0 ,nnnnnkn knnbbac ac ac ar ,rr br b 2222 若和是齐次递推关系 若和是齐次递推关系的两个解是任意常

11、数,则也是该的两个解是任意常数,则也是该递推关递推关性质1 性质1 系的解.系的解. 一般地,齐次线性递推关系的任意有限个 一般地,齐次线性递推关系的任意有限个解的任意线性组合也是该递推关系的解.解的任意线性组合也是该递推关系的解.15(1)(2)1122(1)(2)1122 ( ) 0nnnnnkn knnnnnkn kddac ac ac af nddac ac ac a 若和是递推关系 若和是递推关系的的性质2 性质2 解,则是递推关系解,则是递推关系的解.的解.16112211221122 0 ( ) ( )nnnnnkn knnnkn knnnnnkn kbdac ac ac aac

12、 ac ac af ndbac ac ac af n 分别分别 若和是递推关系 若和是递推关系和和性质3性质3的解 则是的解 则是 , ,的解.的解.17(1)11221(2)11222(1)(2)112212 ( ) ( ) ( )( )nnnnkn knnnnkn knnnnnkn kdac ac ac af ndac ac ac afnddac ac ac af nfn 若是递推关系 若是递推关系的解, 是递推关系的解, 是递推关系的解, 则的解, 则性质4性质4是递推关系是递推关系 的解.的解.叠加原理183.2.2 3.2.2 解的结构解的结构110nkkkqqxc xc 这说明是递

13、推关系(*)的解是方程这说明是递推关系(*)的解是方程的根.的根.1122 0 nnnnnkn kaqac ac ac a 将代入递推关系将代入递推关系(*)(*)1212 0nnnn kkqc qc qc q得得1212, 0n kkkkkqqc qc qc 两端除以得两端除以得19121211122 ( ) 0 C( )=0kkkkknnnkn kC xxc xc xcxcac ac ac ax 定义3.2.1 定义3.2.1 称多项式称多项式为齐次递推关系为齐次递推关系(*)(*)的,相应的方程称为(*)的的,相应的方程称为(*)的,特征方程的根称为(*,特征方程的根称为(*特征多特征多

14、) 的) 的项式项式特征方程特征根特征方程特征根. . 0, kc 因所以0不是递推关系(*)的因所以0不是递推关系(*)的 注:注:特征根.特征根.20 nnaqq 是递推关系(*)的非零解是递推关系(*)的非零解是递推关系(*是递推关系(*定理定理)的)的3.2.13.2.1特征根.特征根.(1)(2)( )(1)(2)( )12(1)(2)( )1212, ,snnnsnnnsnsnnsnsaaaar ar ar ar ar ar ar rr(*)(*) 设是齐次递推关系 设是齐次递推关系(*)的不同解,且的任何解都可以表为(*)的不同解,且的任何解都可以表为则称为递推关则称为递推关定义

15、3.2.定义3.2.系(*)的系(*)的通解.其中为通解.其中为2 2 任意常数.任意常数.213.2.3 3.2.3 特征根法特征根法1.特征根是单根的情形1.特征根是单根的情形12112212, ,knnnnkkkq qqaA qA qA qA AA 设是递推关系(*)的不相等的 设是递推关系(*)的不相等的特征根, 则特征根, 则是(*)是(*)定理 定理 的通解, 其中是任意常数.的通解, 其中是任意常数.1122 niinnnnkkqqaA qA qA q:因 是(*)的特征根,所以是(*)的解,于是:因 是(*)的特征根,所以是(*)的解,于是是是证证(*)的解.(*)的解.220

16、0111112, , ,nnkknnnnkbbkbdbdbdbqqq 设是递推关系(*)的任一解,则 由 个初始 设是递推关系(*)的任一解,则 由 个初始条件唯一确定,下面条件唯一确定,下面只需证明线性表出即可.只需证明线性表出即可.能由能由1122121201122112111221, (,)nnnnkkkkkkkkkkkkbA qA qA qA AAAAAdA qA qA qdA qA qA qd 令 令待定 代入初始条件,得待定 代入初始条件,得这是一个关于这是一个关于的齐次线性方的齐次线性方程组程组12,kA AA2312111112111 ()0kjiij kkkkkqqqqqqq

17、q 此方程组的系数行列式是范得蒙行列式此方程组的系数行列式是范得蒙行列式12,nnnnkaqqq所以线性方程组有唯一解,故能由所以线性方程组有唯一解,故能由线性表出.线性表出.2412346nnnnaaaa 求 求例1例1递推关系的通解.递推关系的通解.32123 460,1,2,3xxxqqq 解 特征方程为解 特征方程为解得特征根 解得特征根 A( 1)B2C3nnnna A,B,CA,B,C所以通解为所以通解为为任意常数.为任意常数.25121222 (3) 3, 8 nnnaaanaa 例2 例2 求定解 求定解212 22013, 13xxqq解 特征方程为解 特征方程为得特征根 得

18、特征根 (13)(13)nnnaAB所以,通解为所以,通解为2622(13)(13)3 (13)(13)8ABAB 代入初值,得代入初值,得 (13)(13)nnna 3+2 33-2 33+2 33-2 36666故,所求定解为故,所求定解为, B 3+2 33-2 33+2 33-2 3A=A=6666解得 解得 272.特征根是重根的情形2.特征根是重根的情形121210kkkkkqxc xc xcxc 设 是特征方程设 是特征方程 的二重根,的二重根,121211212( )( )( )kkkkkn knnnn knkC xxc xc xcxcCxxC xxc xc xc x 令 令

19、1212( )( )n knnnn knkqCxxC xxc xc xc x则 也是则 也是 的二重根,的二重根,28q于于是是 也也是是1211( )(1)()nnn knkCxnxc nxcnk x 的根,的根,因而也是因而也是11( )(1)()nnn knkxCxnxc nxcnk x的根,的根,故有故有11(1)()0nnn kknqc nqcnk qnnanq 这说明也是原递推关系的解.这说明也是原递推关系的解.29211121122)0, (),nnnknnnknnkknkkqxkqnqn qnqkaA qA nqA nqAA nA nqA AA C(C(1 1 一般地,如果 是

20、特征方程的 重根, 一般地,如果 是特征方程的 重根,则都是原递推关系的 个则都是原递推关系的 个线性无关的解.因而线性无关的解.因而 也是原递推关系的解,为任意常数.也是原递推关系的解,为任意常数.nnqq ,nq由上讨论可知,如果 是特征方程的二重根,由上讨论可知,如果 是特征方程的二重根,则是原递推关系的解.则是原递推关系的解.3011221211112111212222112,), () () +()tttiiknnkknkkntttktq qqqkkkaAA nAnqAA nAnqAA nA nq t ti ii=1i=1( ( 设是递推关系(*)的所有不相 设是递推关系(*)的所有

21、不相等的特征根,其 的重数为 重则递推等的特征根,其 的重数为 重则递推关系的通解为关系的通解为定理 定理 313.特征根为复根的情形3.特征根为复根的情形12 cos()sin()cos()sin()()cos()()sin()cos()sin()iinnninninnnnnnnqeqeAq + BqAeBeAninBninABni ABnAnAn ，若特征方程有一对共轭复根：若特征方程有一对共轭复根：那么，通解中会出现项那么，通解中会出现项cos()sin()nnnn由此可知，和也分别由此可知，和也分别是递推关系的解，此二解是线性无关的.是递推关系的解，此二解是线性无关的.32sin()t

22、an().cos()nnnnn （因常数（因常数22cos()sin(). cos()sin().nn1nnn1AnAnaAnAn 故通解中含有项 故通解中含有项 即即112112)cos() ()sin()nmmmmqmqmAA nA nnBB nB nn 一般情形,若 是重复根,则 也是重复根, 一般情形,若 是重复根,则 也是重复根,从而通解中必含有下面的项:从而通解中必含有下面的项:33常系数线性齐次递推关系通解的组成项常系数线性齐次递推关系通解的组成项一对一对m重复根重复根一对单复根一对单复根复根复根q q为为m m重根重根q q为单根为单根实根实根通解中对应的项通解中对应的项特征根

23、特征根,iiqeqe ,iiqeqe nAq112()mnmAA nA nq 112112()cos()()sin()nmmnmmAA nA nnBB nB nn 12cos()sin()nAnAn 341201220 01 nnnaaaaa ， 求定解 求定解例3例32 220qq解 特征方程为解 特征方程为2412qi 解得特征根解得特征根24 ，所以 所以 352cossin44nnnAB （） （）（） （）于是，通解为于是，通解为 2sin4nnna A=0A=0，B=1，B=1，（）（）解得故定解为解得故定解为0 222122AAB （）（）代入初始条件，有代入初始条件，有363.

24、2.4 3.2.4 非齐次方程非齐次方程1111 ( ) (1) (0,( )0,) 0 (2)nnkn kknnkn kac ac af ncf nnkac ac a：常系数线性非齐次递推关系的一般形式为常系数线性非齐次递推关系的一般形式为对应的齐次方程为:对应的齐次方程为:*, nnnnnaaaaa 设是(1)式的一个解是(2)式 设是(1)式的一个解是(2)式的通解, 则(1)的通解, 则(1)定理3.2.2定理3.2.2式的通解为式的通解为37*( ), nf na 对某些特殊的自由项求(1)的特解 对某些特殊的自由项求(1)的特解可用待定系数法.可用待定系数法.1. )(f nbb

25、为常数为常数*(1) .(2) .mnnmaAnaA 若1是重特征根, 则可令若1是重特征根, 则可令若1不是特征根, 则可令若1不是特征根, 则可令23nnn-aaa -13+12=3-13+12=3 求递推关 求递推关4 4系系例例的通解.的通解.313120qq解 特征方程为 解 特征方程为 特征根为1,3,-4, 其中1是单根,特征根为1,3,-4, 其中1是单根,38*, 13 (2)12 (3)3naAnAnA nA n 所以可令特解形式为代入原递推关系所以可令特解形式为代入原递推关系310310AA 得 得 *310nan 于是是原递推关系的一个特解,于是是原递推关系的一个特解,

26、1231233 3( 4)10nnnaBBBnB ,B ,B故所求通解为故所求通解为其中为任意常数.其中为任意常数.391121 1 nnaaa HanoiHanoi 求解塔问 求解塔问例5例5题题*20, 2, , nqqaA A=2A+1 A=-1,A=2A+1 A=-1,解 特征方程为得特征根因1不是解 特征方程为得特征根因1不是特征根,所以可令特解形式为代入原递推特征根,所以可令特解形式为代入原递推关系,得关系,得21,1,21.nnnnaBBa于是递推关系的通解为代入初始条件,于是递推关系的通解为代入初始条件,得故所求定解为得故所求定解为4011221, 21,nnnnaaaa另解

27、由 另解 由 1212320 1, 3 nnnaaaaa 两式相减, 得与原递推关系同解的齐次递推关系两式相减, 得与原递推关系同解的齐次递推关系(*)(*)12320 1, 2qqq2 2 q q(*)的特征方程为(*)的特征方程为2 , 21.nnnnaABaA=-1, B=1, A=-1, B=1, (*)的通解为代入初始条件, 得(*)的通解为代入初始条件, 得故原递推关系的解为故原递推关系的解为41 (2. () ) nf nbb 为常数为常数*.(2) .mnnnnbmaAn bbaAb (1) 若 是重特征根, 则可令(1) 若 是重特征根, 则可令若 不是特征根, 则可令若 不

28、是特征根, 则可令12442nnnnaaa例6例6 求的通解.求的通解.*222nnqaAn 解 易知是二重特征根, 可设特解形式为解 易知是二重特征根, 可设特解形式为 2121231,21 222 ,2,.nnnnAaBB nnB BB 代入递推关系求得故通解为代入递推关系求得故通解为其中为任意常数其中为任意常数4221212( 2)( 3)4.,nnnnaBBB B 故所求通解为故所求通解为为任意常数.为任意常数.12 5642 4nnnnaaa 求递推关系 求递推关系 例7例7 的通解. 的通解.2*12560, 2, 3, 4 .nnqqqqaA 解 因特征方程为所以特征根解 因特征

29、方程为所以特征根可设特解形式为可设特解形式为1245 46 442 4nnnnAAA代入递推关系,得代入递推关系,得3)42 168AA5 5(1+(1+4 4即即因因4 4不是不是特征根特征根433. () )( )(nrrPf nbnrnnbP 是 的 次多项式, 为常数是 的 次多项式, 为常数*(1) ( ).(2) ( ).mnnrnnrbman b Q nbab Q n 若 是重特征根, 则可令若 是重特征根, 则可令若 不是特征根, 则可令若 不是特征根, 则可令( )( )rrQ nP n其中是与同次的多项式.其中是与同次的多项式.124(1)nnnaaan n 求 求例8例8

30、的通解.的通解.1223,23,qq 解 易知特征根为解 易知特征根为*2naAnBnC因1不是特征根,故可设特解形式为因1不是特征根,故可设特解形式为 44212121( 23)( 23)(331)18,.nnnaBBnnB B 因此,递推关系的通解为因此,递推关系的通解为其中为任意常数其中为任意常数2266(2)2(433 )AnAB nABCnn代入原递推关系,得代入原递推关系,得111 , , 6618ABC 比较系数,有比较系数,有450.nnkSk 例例 求 求9 910, 0 nnnSSSnS 解 显然满足非齐次定解问题解 显然满足非齐次定解问题11212, 1, 21nnnnn

31、nnSSnSSnSSS由两式相减,得由两式相减,得123123012, 21,330 0, 1, 3 nnnnnnnSSSSSSSSSS 同理再与上式相减,可同理再与上式相减,可得齐次定解问题得齐次定解问题46210, 211(1).222nABCn nSnn 解得 解得 故 故 323331(1)qqqq 该齐次递推关系的特征多项式为该齐次递推关系的特征多项式为22()( 1)()nnqSABnCnABnCn所以特征根 = 1是三重根,于是通解为所以特征根 = 1是三重根,于是通解为0, 1, 243AABCABC代入初始条件,得代入初始条件,得473.2.5 3.2.5 一般递推关系的线性

32、化一般递推关系的线性化2100 1 nnnane aa 解 解1010定解问题定解问题例例2121, lnlnlnnnnnnane aaann 解 由原递推关系得 两边取对数解 由原递推关系得 两边取对数210ln,ln 0 nnnnbabbnnb 令得递推关系令得递推关系4810ln (1)0 nnbbnb 先解递推关系先解递推关系(1)ln !nbn 可可得得( (1 1) )的的解解 210 (2)0 nnbbnb 再解递推关系再解递推关系(2)(1)(21)6nn nnb 可得(2)的解 可得(2)的解 49(1)(21)ln !6nn nnbn于是由叠加原理 于是由叠加原理 (1)(

33、21)6 !n nnnan e 从而, 原递推关系的解为从而, 原递推关系的解为5010(1)2 , 1 273 nnnnanana 例11例11题题 解定解问 解定解问10, 2 0 nnnnnbnabbb 解 令得解 令得1, 易知特征根为因2不是特征根, 所以可设易知特征根为因2不是特征根, 所以可设*2 ,nnbA 特解为 特解为 nb代入 的递推关系,可得代入 的递推关系,可得23A 511022( 1), 1 3273 nnnanna 从而原递推关系的解为从而原递推关系的解为11*2222,( 1)333nnnnnnbbB于是 故通解 于是 故通解 1112, 3222( 1)2(

34、 1)333nnnnnBb 代入初始条件,得所以代入初始条件,得所以 5210!, 1 2 nnananna 解定解 解定解1212问题问题例例10, !1, 1 2 nnnnabnbbnb 解 令则有解 令则有2,nbn解得 解得 故原递推关系的解为故原递推关系的解为 (2) !.nann53221021, 1, (0) 2 nnnaanaa 解定解 解定解1313问题问题例例5 21, 5 21nnnnba解得 从而原递推关系的解为解得 从而原递推关系的解为210, 21, 1 4 nnnnbabbnb 解 令则有解 令则有543.3 3.3 用母函数法解递推关系用母函数法解递推关系0(

35、),( )( ),( ).nnnnnnaG xa xG xG xG xxxa 先作出的母函数先作出的母函数将给定的递推关系为关于的方程(代将给定的递推关系为关于的方程(代数方程或微分方程),从中解出再将数方程或微分方程),从中解出再将展开成 的幂级数,于是的系数就是递推关系展开成 的幂级数,于是的系数就是递推关系的的基:基:转化转化解解本思想本思想5512 562 , 2nnnnaaan 解递推关系 解递推关系例1例1122222 562nnnnnnnnnnnnnxna xaxaxx解 用乘以上式的两端并对 从2到求和,得解 用乘以上式的两端并对 从2到求和,得2210256(2 )nnnnn

36、nnnnnna xxa xxa xx即 即 0( )nnnA xa x 令 令 562010 ( )5 ( )6( )1 (12 )12A xaa xx A xax A xxx 则有则有220104( )156(5)12xA xxxaaaxx 即即201022(5)4( )156(156)(12 )aaaxxA xxxxxx所以所以5712,1312ccxx 令右边第一项为令右边第一项为2222241213(156)(12 )(12 )(543 )(64 )(156)(12 )xABCxxxxxxABCABC xAB xxxx 对于右边第二项,令对于右边第二项,令054302, 4, 2644

37、ABCABCABCAB 比较两边分子的系数,得比较两边分子的系数,得58122122,242( )13121213(12 )2 1312(12 )ccA xxxxxxccxxx 所以所以1200011200(3 )(2 )2(1)(2 )32(1)2nnnnnnnnnnnnnncxcxnxccnxa x 11212 32(1)2,nnnnaccnc c 故递推关系的通解为故递推关系的通解为其中为任意常数.其中为任意常数.部分分式之和591212 1 nnnFFFFF 求定解问题 求定解问题例2例200 ( ) (0)nnnnFG xF xF 解 的母函数为解 的母函数为这里这里 1220()n

38、nnnxFFx 1221222nnnnnnxxFxxFx60210nnnnnnG xxxF xxF x（ ）（ ）即 即 2( )( )xxG xx G x21xG xxx ， （ ）， （ ）所以所以( )15151122xG xxx 115515151122xx611515, ,22111( )115G xxx 令于是令于是00011()()()55nnnnnnnnxxx1()511515 225nnnnnF故故621201(1)(2)20, 2 0, 1 nnnnanaanaa 解定解问题 解定解问题例3例321123( )nnA xaa xa xa x 解 令解 令2223423134

39、0, ( )23(1)( )23(1)nnnnaAxa xa xna xxAxa xa xna x 由原问题知于是由原问题知于是234321(1)( )2(32) (1)(2)nnnx Axa xaaxnanax 两式相减, 得两式相减, 得63312321232,(1)( )2222 2( )nnaax A xa xa xa xaxxA x 由原问题知于是由原问题知于是( )22,2( )11A xxA xxx 所以所以0( )22ln(1)( )xA xdxxxA x 积分积分2ln( )ln(0)2ln(1)A xAxx 即即1ln(0)lnln1Aa 又= 0又= 06400( 1)

40、2(1)!kknnnknkxk 10(1)2,( 1)!knknknkak 所以所以22( )(1)xeA xx 故故00( 2 )(1)!nnnnxnxn 6511( 1) , 2 0 nnnDnDnD 用指母函数解递推关系,求 用指母函数解递推关系,求例例解解4 4001, ( )!nnnxDD xDn 解 令设解 令设!nxnn用乘以递推关系的两端,然后对 从1到求和,得用乘以递推关系的两端,然后对 从1到求和,得1111( 1)!nnnnnnnnnxxxDnDnnn 0( )( )1xD xDxD xe 即即66( )1xeD xx 亦即 亦即 0( 1) !knnkDnk 由母函数的

41、性质知由母函数的性质知0( 1)!111 !(1( 1)1!2!knnknDnknn 故故67111, 2 1 nnkn kkhh hnh 求解 求解5 5 递推关系递推关系例例1( )nnnH xh x 解 令 解 令 21111( )klk lklklklklHxh xh xh h x 平方 平方 234121221132231112211()()() ()nnnnh hxh hh h xh hh hh h xh hh hhh x6812121()( )( )nnnkn knnknh hxh xH xh xH xx 2, ( )( )0HxH xx所以所以12114114,( ), ( )

42、22xxHxHx解得解得112(0)0,( )11411( )(14 )222HHxxH xx 因所以舍去,得因所以舍去,得690211111( 4 )( 4 )22222nnnnxxxnn21 111(1)(2)(1)12 222( 4 )2!nnnxxn 211(12)(14)(122)( 4 )22!nnnnxxn 211 3 5(23)422!nnnnnxxn 70221,1nnhnn 所以所以12211nnnxnn 21(22)!22!(22)(24)4 2nnnnxxnnn 21(22)!1(22)!(1)!(1)!(1)!nnnnnnxxxn nn nn713.4 3.4 三种典

43、型数列三种典型数列3.4.1 Fibonacci数列数列1, 1, 2, 3, 5, 8, 13, 21, 34, Fibonacci，。 形如的数列， 形如的数列，从第三项起，每个数都是它前两项之称从第三项起，每个数都是它前两项之称为为数列数列和和1212, 3 1, 1 nnnnFibonacciFFFFnFF 数列的定解问题为:数列的定解问题为:721151511522255115, 25 115, 25nnnnnnFnn 其解为:其解为:为偶数为偶数为奇数为奇数73FibonacciFibonacci数列最初来源于意大利数学家数列最初来源于意大利数学家在1202年提出的有趣的兔子问题.

44、在1202年提出的有趣的兔子问题.1212121213 11 nnnnnnnnFnF = F =nFFFFFFFnFF ， ， ，解 用表示在第 个月的兔子数，显然，解 用表示在第 个月的兔子数，显然，3时于是得的定解问题3时于是得的定解问题n（）有雌雄一对小兔, 一月后长大, （）有雌雄一对小兔, 一月后长大, 两月起往后每月生(雌雄)一对小兔，小兔亦同两月起往后每月生(雌雄)一对小兔，小兔亦同例1例1样样如此，问第 月后共有多少如此，问第 月后共有多少兔子问题兔子问题对小兔？对小兔？74nn() 某人欲登上 级楼梯,若每次() 某人欲登上 级楼梯,若每次只能跨一级或两级, 问他从地面上到第

45、 级楼梯,只能跨一级或两级, 问他从地面上到第 级楼梯,共有多少种共有多少种上楼梯上楼梯不同不同问问例例题题2 2的方法?的方法?Fibonacci数列的其它模型数列的其它模型12.1,2, 3naaan 解 设上到第n级楼梯的方法数为显然解 设上到第n级楼梯的方法数为显然时, 将上楼梯的方案分类:时, 将上楼梯的方案分类:1nna (1) 第一步跨一级,则余下的 -1级楼梯有(1) 第一步跨一级,则余下的 -1级楼梯有 种上法; 种上法;2nna (2) 第一步跨两级,则余下的 - 2级楼梯有(2) 第一步跨两级,则余下的 - 2级楼梯有 种上法. 种上法.751212, 3 1, 2 nn

46、naaanaa 故上楼梯的方案数为:故上楼梯的方案数为:01111,11515225nnnnaaF 由递推关系和初始条件可推得显然由递推关系和初始条件可推得显然76.nnaa ()用红、蓝二色给一个1n棋 ()用红、蓝二色给一个1n棋盘涂色，要求相邻两格不能都涂成红色，设不同盘涂色，要求相邻两格不能都涂成红色，设不同的涂色法共有种，的涂色法共有种，棋盘涂色问棋盘涂色问求求例例题题3 3122, 3, 3, aan解 显然设对涂色法分类:解 显然设对涂色法分类:21 (2)nna (1)第一格涂红色, 则第二格只能涂蓝色, 余下部(1)第一格涂红色, 则第二格只能涂蓝色, 余下部 分为棋盘,有种

47、涂色方法; 分为棋盘,有种涂色方法;1 (2)n棋盘棋盘21 (1)nna (2)第一格涂蓝色, 则余下部分为棋盘,有(2)第一格涂蓝色, 则余下部分为棋盘,有 种涂色方法. 种涂色方法.771(1)n 棋棋盘盘1212, 3 2, 3 nnnnaaaanaa 于是涂色方案数满足递推关系:于是涂色方案数满足递推关系:02221,11515225nnnnaaF 由递推关系和初始条件可得显然由递推关系和初始条件可得显然78()用规格为12的骨牌完全覆()用规格为12的骨牌完全覆盖2n的棋盘, 问有多少种不同盖2n的棋盘, 问有多少种不同棋盘覆盖棋盘覆盖的完全覆的完全覆问题问题例4 例4 盖方案?盖

48、方案?12, 1, 2,nggg解 设所求覆盖方案数为显然解 设所求覆盖方案数为显然3, :n 设对覆盖方式分类设对覆盖方式分类1n- 2 (n-1)g2 (n-1)g(1)最左边两格用同一块骨牌竖着覆盖, 则剩余(1)最左边两格用同一块骨牌竖着覆盖, 则剩余部分为棋盘, 有种方案;部分为棋盘, 有种方案;2(1)n 棋棋盘盘792n- 2 (n-2)g2 (n-2)g(2)用一块骨牌横着覆盖第一行的前两格, 则第(2)用一块骨牌横着覆盖第一行的前两格, 则第二行前两格一定被同一骨牌覆盖, 剩余部分为二行前两格一定被同一骨牌覆盖, 剩余部分为棋盘, 有种方案.棋盘, 有种方案.2(2)n 棋棋

49、盘盘1212, 3 1, 2 nnnngggngg 于是覆盖方案数g 满足递推关系:于是覆盖方案数g 满足递推关系:8011111515225nnnngF 显然显然0 (1)(2)(1), 1.nxx xxxnx(又称为递降阶乘函数)定义为(又称为递降阶乘函数)定义为下函数下函数: :阶乘阶乘1(1)nnnxxxxn 易知有递推性质:易知有递推性质: 3.4.2 Stirling数列数列81120012 ( , ), ( , ) ( , ), ( , )nnknnkkkStirlxS n k xxSn kingStirxS n kSni gkl n定义3.4.1定义3.4.1第第设设则称为则称

50、为一类数第二一类数第二类类 为为数.数.111111(1) ( ,0)0;(2) ( ,1)( 1)(1)!;(3) ( , )1;(4) ( ,1)( ,2);(5) sgn( , )( 1);nn kStirlingS nS nnS n nS n nC nS n k 第一类数有如下 第一类数有如下定定性质:性质:理3.4.1 理3.4.1 821111(6) ( , ) ( , )(1,1)(1)(1, )S n kS n kS nknS nk满足递推关系满足递推关系kx比较两端的系数,即知结论成立.比较两端的系数,即知结论成立.111 (1) (1) , nnnnxxnxx xnx证 由