组合数学第四版卢开澄标准答案第二章母函数与递推关系

【第53页共53页】第二章 母函数与递推关系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故解为：于是有故此母函数2.2已知序列{求母函数[解]设其母函数为 2.3已知母函数［解］由于则有于是有由②－6*①有 -15A=60③ 故此 A=-4 ④将④代入①有 B=3-A=3-(-4)=7从而有故此故此：2.4已知母函数［解］由于则有于是有,故此故 2.5设 解其根为 故有于是有 即 2.6求序列{1,0,2,0,3,0,4,0,……}的母函数[解] 令 而 故此2.7设 求.[解]根据题2.6可知 从而 并且2.8求下列序列的母函数：(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已知。[解]利用母函数的性质3，可知母函数 2.13已知[解]2.14已知 (a)求 (b)[解]2.15已知的母函数为求序列的递推关系。[解]2.17[证] 用母函数法求下列递推函数关系的解.[解]2.19用特征法求习题2.18的解[解]： [解] [解]2.23[解] 2.24[解] 2.25设序列的母函数为但[解] 2.26[证]2.27求下列递推关系的一般解[解] （m）特征方程：特征根：齐次通解：非齐次通解：代入非齐次方程：故此非齐次方程的特解为：于是非齐次方程的通解为：（n）特征方程：特征根：齐次通解：非齐次通解：（因为，是现齐次的一重特征根）代入非齐次方程：故有C＝1，D＝3，E＝2故此非齐次方程的特解为：于是非齐次方程的通解为：令新的A为A＋B，有：2.28，利用置换求解。【解】：由，两边取对数：令：，则有从而特征方程：特征根：齐次通解：将代入上式，有2.29，求这个递推关系的解。【解】：由两边取对数：令：，则有从而特征方程：特征根：齐次通解：将代入上式，有2.30，，，解个递推关系。【解】：由，两边取对数：令：，则有，从而特征方程：特征根：齐次通解：由初值，由，解之于是有将代入上式，有2.31，，，解个递推关系。【解】：由，两边取对数：令：，则有，从而特征方程：特征根：齐次通解：由初值，由，解之于是有将代入上式，有2.32解下列递推关系（a），，（b），（c）【解】：（a）由，，得：（b）特征方程：特征根：齐次通解：非齐次特解：代入非齐次方程：从而非齐次特解：于是非齐次特解：所以（c）特征方程：特征根：齐次通解：非齐次特解：代入非齐次方程：从而非齐次特解：于是非齐次特解：2.33，，是Fibonacci序列，求解。（提示：）【解】：特征方程：特征根：齐次通解：由于故此非齐次得一个特解：因此，非齐次得通解为：2.34，，求。【解】：特征方程：特征根：齐次通解：非齐次特解：于是令，有；令，有，于是；令，有，于是；令，有，于是；则非齐次特解：从而，非齐次的通解：将代入，有，于是非齐次的解为：2.35，，求。【解】：特征方程：特征根：齐次通解：非齐次特解：于是令，有；令，有，于是；令，有，于是；令，有，于是；令，有，于是；则非齐次特解：从而，非齐次的通解：将代入，有，于是非齐次的解为：2.36利用迭代法解：（a），；（b），。【解】：（a）(迭代法)设于是，（b）(迭代法)设于是， 2.37利用置换解，，。【解】：（置换法）将代入，有(1)若>0,特征方程：特征根：通解：初值：，解得故此，于是，（2）若<0,则有：从而初值：，解得故此，于是，利用置换解，。【解】：（置换法）将置换代入递推方程，有整理，得：特征方程：特征根：齐次通解：非齐次特解：代入非齐次方程，有：即从而非齐次得特解为：故非齐次的通解为：由初值得，，故，从而，即于是有，从而利用置换解，。【解】：（置换法）将置换代入递推方程，有整理，得：特征方程：特征根：齐次通解：非齐次特解：（因为，1是一重特征根）代入非齐次方程，有：从而非齐次特解为：故非齐次的通解为：于是将代回，有由初值得，从而因此，有2.40解下列递推关系：（a）,,；（b），,；（c）,；【解】：（a）（置换法）令代入递推方程，有整理，得：特征方程：特征根：，齐次通解：非齐次特解：代入非齐次方程，有：，整理，有，故从而非齐次的特解为：故非齐次的通解为：由初值得，，故得，，故代入有，故，即因此，于是，（b）（置换法）令代入递推方程，有整理，得：特征方程：特征根：，齐次通解：非齐次特解：代入非齐次方程，有：，整理，有，故从而非齐次的特解为：故非齐次的通解为：由初值得，，故得，，故代入有，故，即因此，于是，（c）特征方程：特征根：齐次通解：非齐次特解：代入非齐次方程，有：故,从而，从而非齐次的特解为：故非齐次的通解为：令A为A＋B后，有利用，有，知，从而2.41设满足：，其中：，和都是常数，试证该序列满足三阶奇次线性常系数奇次递推关系，且有特征多项式。【解】：满足特征多项式为的递推关系为=1\*GB3①整理为=2\*GB3②将关于序列的递推关系：=3\*GB3③代入=2\*GB3②，有这说明序列满足三阶奇次线性常系数奇次递推关系=1\*GB3①，且有特征多项式。2.42设满足，满足，，，试证序列满足四阶奇次线性常系数奇次递推关系。【解】：方法一（特征系数法）由于序列满足递推关系：=1\*GB3①故显然也满足递推关系：这里，为任意常数整理为：=2\*GB3②由于序列满足递推关系：=3\*GB3③故显然也满足递推关系这里，为任意常数整理为：=4\*GB3④令，解之得，将此代入=2\*GB3②，=4\*GB3④有=5\*GB3⑤=6\*GB3⑥将=5\*GB3⑤＋=6\*GB3⑥，并注意到，我们有=7\*GB3⑦这就是序列满足的四阶线性常系数奇次递推关系。方法二（特征根法）递推关系特征方程：特征根：故其通解：递推关系特征方程：特征根：故其通解：于是因此序列满足的四阶线性常系数奇次递推关系。其特征多项式为整理为再整理为因此，对应的四阶线性常系数奇次递推关系为2.43在习题2.42中，若，试证之。【解】：（特征根法）递推关系特征方程：特征根：故其通解：递推关系特征方程：特征根：故其通解：于是因此序列满足的四阶线性常系数奇次递推关系。其特征多项式为整理为再整理为因此，对应的四阶线性常系数奇次递推关系为2.44设和均满足递推关系，试证：(a)满足一个三阶奇次线性常系数奇次递推关系；(b)二阶线性常系数奇次递推关系。【证】：(a)（特征根法）二阶奇次线性常系数奇次递推关系的特征方程为=1\*GB3①甲.设其特征根为，，，则有：于是这说明满足一个三阶奇次线性常系数奇次递推关系，其特征方程为：或者由于，，故因此有故此满足如下的三阶奇次线性常系数奇次递推关系设其特征根为是一个二重根，则：于是这说明满足一个三阶奇次线性常系数奇次递推关系，其特征方程为：由于，，因此有故此满足如下的三阶奇次线性常系数奇次递推关系(b)甲.因此，这说明满足一个二阶奇次线性常系数奇次递推关系其特征方程为整理为：由于，，有于是故此序列满足一个二阶奇次线性常系数奇次递推关系为：乙.因此，这说明满足一个二阶奇次线性常系数奇次递推关系其特征方程为整理为：由于，，于是故此序列满足一个二阶奇次线性常系数奇次递推关系为：2.45设是Fibonacci序列，是找出常数a，b，c，d，使。【解】：（1）先求常数a,b,c,d：令，有；，有；，有；，有注意到，，，，，，，，，