組合數(shù)學第四版盧開澄標準答案第二章母函數(shù)與遞推關系

【第53頁共53頁】第二章 母函數(shù)與遞推關系2.1求序列.兩邊求導：同乘以x：兩邊求導： 兩邊同乘以x：兩邊求導： 兩邊同乘以x： 即方法二：令則有 ① 1= ② 8= ③ 27= ④于是②－①有 1=3A+2B+C ⑤ ③－①有 8=9A+5B+2C ⑥ 27=19A+9B+3C ⑦于是⑥－2*⑤有 6=3A+B⑧ ⑦－3*⑤有 24=10A+3B ⑨于是有⑨－3*⑧有 6=A ⑩將⑩代入⑧有 B=6-3A=6-3*6=-12=11\*GB2⑾將⑩，=11\*GB2⑾代入⑤有 C=1-3A-2B=1-3*6-2*(-12)=7將⑩，⑾，⑿代入⑨有D=-A-B-C=-6-(-12)-7=-1故解為：于是有故此母函數(shù)2.2已知序列{求母函數(shù)[解]設其母函數(shù)為 2.3已知母函數(shù)［解］由于則有于是有由②－6*①有 -15A=60③ 故此 A=-4 ④將④代入①有 B=3-A=3-(-4)=7從而有故此故此：2.4已知母函數(shù)［解］由于則有于是有,故此故 2.5設 解其根為 故有于是有 即 2.6求序列{1,0,2,0,3,0,4,0,……}的母函數(shù)[解] 令 而 故此2.7設 求.[解]根據(jù)題2.6可知 從而 并且2.8求下列序列的母函數(shù)：(a)1,0,1,0,1,0,……(b)0,-1,0,-1,0,-1,……(c)1,-1,1,-1,1,-1[解](a) (b) (c) 2.9設證明：（a） (b) (c)[證]2.10證明：[證] 2.11 [證]2.12已知。[解]利用母函數(shù)的性質(zhì)3，可知母函數(shù) 2.13已知[解]2.14已知 (a)求 (b)[解]2.15已知的母函數(shù)為求序列的遞推關系。[解]2.17[證] 用母函數(shù)法求下列遞推函數(shù)關系的解.[解]2.19用特征法求習題2.18的解[解]： [解] [解]2.23[解] 2.24[解] 2.25設序列的母函數(shù)為但[解] 2.26[證]2.27求下列遞推關系的一般解[解] （m）特征方程：特征根：齊次通解：非齊次通解：代入非齊次方程：故此非齊次方程的特解為：于是非齊次方程的通解為：（n）特征方程：特征根：齊次通解：非齊次通解：（因為，是現(xiàn)齊次的一重特征根）代入非齊次方程：故有C＝1，D＝3，E＝2故此非齊次方程的特解為：于是非齊次方程的通解為：令新的A為A＋B，有：2.28，利用置換求解。【解】：由，兩邊取對數(shù)：令：，則有從而特征方程：特征根：齊次通解：將代入上式，有2.29，求這個遞推關系的解?！窘狻浚河蓛蛇吶?shù)：令：，則有從而特征方程：特征根：齊次通解：將代入上式，有2.30，，，解個遞推關系。【解】：由，兩邊取對數(shù)：令：，則有，從而特征方程：特征根：齊次通解：由初值，由，解之于是有將代入上式，有2.31，，，解個遞推關系?！窘狻浚河?，兩邊取對數(shù)：令：，則有，從而特征方程：特征根：齊次通解：由初值，由，解之于是有將代入上式，有2.32解下列遞推關系（a），，（b），（c）【解】：（a）由，，得：（b）特征方程：特征根：齊次通解：非齊次特解：代入非齊次方程：從而非齊次特解：于是非齊次特解：所以（c）特征方程：特征根：齊次通解：非齊次特解：代入非齊次方程：從而非齊次特解：于是非齊次特解：2.33，，是Fibonacci序列，求解。（提示：）【解】：特征方程：特征根：齊次通解：由于故此非齊次得一個特解：因此，非齊次得通解為：2.34，，求?！窘狻浚禾卣鞣匠蹋禾卣鞲糊R次通解：非齊次特解：于是令，有；令，有，于是；令，有，于是；令，有，于是；則非齊次特解：從而，非齊次的通解：將代入，有，于是非齊次的解為：2.35，，求?！窘狻浚禾卣鞣匠蹋禾卣鞲糊R次通解：非齊次特解：于是令，有；令，有，于是；令，有，于是；令，有，于是；令，有，于是；則非齊次特解：從而，非齊次的通解：將代入，有，于是非齊次的解為：2.36利用迭代法解：（a），；（b），?！窘狻浚海╝）(迭代法)設于是，（b）(迭代法)設于是， 2.37利用置換解，，?！窘狻浚海ㄖ脫Q法）將代入，有(1)若>0,特征方程：特征根：通解：初值：，解得故此，于是，（2）若<0,則有：從而初值：，解得故此，于是，利用置換解，。【解】：（置換法）將置換代入遞推方程，有整理，得：特征方程：特征根：齊次通解：非齊次特解：代入非齊次方程，有：即從而非齊次得特解為：故非齊次的通解為：由初值得，，故，從而，即于是有，從而利用置換解，。【解】：（置換法）將置換代入遞推方程，有整理，得：特征方程：特征根：齊次通解：非齊次特解：（因為，1是一重特征根）代入非齊次方程，有：從而非齊次特解為：故非齊次的通解為：于是將代回，有由初值得，從而因此，有2.40解下列遞推關系：（a）,,；（b），,；（c）,；【解】：（a）（置換法）令代入遞推方程，有整理，得：特征方程：特征根：，齊次通解：非齊次特解：代入非齊次方程，有：，整理，有，故從而非齊次的特解為：故非齊次的通解為：由初值得，，故得，，故代入有，故，即因此，于是，（b）（置換法）令代入遞推方程，有整理，得：特征方程：特征根：，齊次通解：非齊次特解：代入非齊次方程，有：，整理，有，故從而非齊次的特解為：故非齊次的通解為：由初值得，，故得，，故代入有，故，即因此，于是，（c）特征方程：特征根：齊次通解：非齊次特解：代入非齊次方程，有：故,從而，從而非齊次的特解為：故非齊次的通解為：令A為A＋B后，有利用，有，知，從而2.41設滿足：，其中：，和都是常數(shù)，試證該序列滿足三階奇次線性常系數(shù)奇次遞推關系，且有特征多項式。【解】：滿足特征多項式為的遞推關系為=1\*GB3①整理為=2\*GB3②將關于序列的遞推關系：=3\*GB3③代入=2\*GB3②，有這說明序列滿足三階奇次線性常系數(shù)奇次遞推關系=1\*GB3①，且有特征多項式。2.42設滿足，滿足，，，試證序列滿足四階奇次線性常系數(shù)奇次遞推關系。【解】：方法一（特征系數(shù)法）由于序列滿足遞推關系：=1\*GB3①故顯然也滿足遞推關系：這里，為任意常數(shù)整理為：=2\*GB3②由于序列滿足遞推關系：=3\*GB3③故顯然也滿足遞推關系這里，為任意常數(shù)整理為：=4\*GB3④令，解之得，將此代入=2\*GB3②，=4\*GB3④有=5\*GB3⑤=6\*GB3⑥將=5\*GB3⑤＋=6\*GB3⑥，并注意到，我們有=7\*GB3⑦這就是序列滿足的四階線性常系數(shù)奇次遞推關系。方法二（特征根法）遞推關系特征方程：特征根：故其通解：遞推關系特征方程：特征根：故其通解：于是因此序列滿足的四階線性常系數(shù)奇次遞推關系。其特征多項式為整理為再整理為因此，對應的四階線性常系數(shù)奇次遞推關系為2.43在習題2.42中，若，試證之?！窘狻浚海ㄌ卣鞲ǎ┻f推關系特征方程：特征根：故其通解：遞推關系特征方程：特征根：故其通解：于是因此序列滿足的四階線性常系數(shù)奇次遞推關系。其特征多項式為整理為再整理為因此，對應的四階線性常系數(shù)奇次遞推關系為2.44設和均滿足遞推關系，試證：(a)滿足一個三階奇次線性常系數(shù)奇次遞推關系；(b)二階線性常系數(shù)奇次遞推關系?！咀C】：(a)（特征根法）二階奇次線性常系數(shù)奇次遞推關系的特征方程為=1\*GB3①甲.設其特征根為，，，則有：于是這說明滿足一個三階奇次線性常系數(shù)奇次遞推關系，其特征方程為：或者由于，，故因此有故此滿足如下的三階奇次線性常系數(shù)奇次遞推關系設其特征根為是一個二重根，則：于是這說明滿足一個三階奇次線性常系數(shù)奇次遞推關系，其特征方程為：由于，，因此有故此滿足如下的三階奇次線性常系數(shù)奇次遞推關系(b)甲.因此，這說明滿足一個二階奇次線性常系數(shù)奇次遞推關系其特征方程為整理為：由于，，有于是故此序列滿足一個二階奇次線性常系數(shù)奇次遞推關系為：乙.因此，這說明滿足一個二階奇次線性常系數(shù)奇次遞推關系其特征方程為整理為：由于，，于是故此序列滿足一個二階奇次線性常系數(shù)奇次遞推關系為：2.45設是Fibonacci序列，是找出常數(shù)a，b，c，d，使。【解】：（1）先求常數(shù)a,b,c,d：令，有；，有；，有；，有注意到，，，，，，，，，