《组合数学3.2常系数线性齐次递推关系》由会员分享，可在线阅读，更多相关《组合数学3.2常系数线性齐次递推关系（20页珍藏版）》请在金锄头文库上搜索。
1、3.2常系数线性齐次递推关系 n3.2.1 递推关系(3.2.1)n3.2.2 递推(3.2.1)的特征方程n3.2.3 递推(3.2.1)的解n3.2.4 递推(3.2.1)特征根互不同n3.3.5 递推(3.2.1)特征根有重根足饮赏炳嗅锦纸吴易败泛馋薄靖昏至火焙谜挑砰继霓咙暑绍则板塌在措苔组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系3.2.1 递推关系(3.2.1)n常系数常系数k阶阶线性线性齐次齐次递推关系递推关系 anc1an-1c2an-2ckan-k (3.2.1) 其中c1,c2,ck是实数常数， ck0威泉晃讣耀城众科婆撬纯辽鸭窃瑟捂补鸵崩税攘
2、坞钨惜埔辨腹涨票糊愚疏组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系3.2.2 递推(3.2.1)的特征方程n把anxn (x0)代入递推关系(3.2.1)得 xnc1xn-1c2xn-2ckxn-k 用xn-k除上式两边得 xkc1xk-1c2xk-2ck-1xck xkc1xk-1c2xk-2ck-1xck0 (3.2.2) (3.2.2)即为递推关系(3.2.1)的特征方程特征方程 递推关系(3.2.1)的特征根特征根 铰踞玉椒巳验妻矢挠撰菠烹伎煮蹭稽恕燎供枫缝彪涟阴蘑侣试叹姓驹油饵组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系
3、3.2.3 递推(3.2.1)的解n定理3.2.1 非零复数q是特征方程(3.2.2)的根，当且仅当anqn是递推关系(3.2.1)的解nxkc1xk-1c2xk-2ck-1xck0 (3.2.2) xq anqnnanc1an-1c2an-2ckan-k (3.2.1) 其中c1,c2,ck是实数常数， ck0雕吃父吧胶展卒警莽睛棍划辑柔梯秀骚芍辰斯挨捌仁鸡反岔传偷迄恭删题组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系3.2.3 递推(3.2.1)的解n定理3.2.2 若h1(n),h2(n),hk(n)是递推关系(3.2.1)的解，则它们的线性组合A1h1(n
4、)A2h2(n)Akhk(n)也是递推关系(3.2.1)的解，其中A1, A2, Ak为常数。 露慎措脖开贝怎膨杏醚啤妊缴爱槽肉骄漳衅智吊窿惭歼滥邯殉邓全青削寸组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系3.2.4 递推(3.2.1)特征根互不同n定理3.2.3 如果特征方程(3.2.2)有k个不同的根x1,x2,xk (可有共轭虚根)，则 anA1x1nA2x2nAkxkn 是递推关系(3.2.1)的通解，其中A1,A2,Ak为任意的常数。 昧迂织鼻迁距期令戳外狙耶废毋鸦傻厢腻慑坦金溺兴英淑剖啡魁面浪坷墙组合数学 3.2常系数线性齐次递推关系组合数学 3.2常
5、系数线性齐次递推关系3.2.4 递推(3.2.1)特征根互不同n例3.2.1 解递归n解解 递推推关系fnfn-1fn-2 () ()的特征方程为x2x10 ()的特征根x1 , x2 ()的通解怜郁翠放任狙撰煎孺抱坛蹦灰乎焦隐旱歼掐赠票锈搀琢肋艳恍歉囱亲录裁组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系3.2.4 递推(3.2.1)特征根互不同n把f00, f11代入通解得n因此所求递归的解为 饶归修钝血脑坷既鹏棉来髓丧钮坷煤此赤傻畦玫殉驻与繁弊衅杖宋佃船瓜组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系3.2.4 递推(3.2.1)
6、特征根互不同n定理3.2.3中，若特征方程(3.2.2)有共轭复根x1pei，x2pe-i 此时x1npnein，x2npne-in都是递推关系(3.2.1)的解。再由定理3.2.2知： x1n x2npncosn, x1n x2npnsinn 也都是递推关系(3.2.1)的解。确柳狠峡藉洞拘钨风业减落霓篆搽赡卓歧腮旁裤龚瑰北驮敲孩蜂武蕾奢涸组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系3.2.4 递推(3.2.1)特征根互不同n特征方程(3.2.2)有k个不同的根x1,x2,xk n递推关系(3.2.1)的通解 anA1x1nA2x2nAkxkn 共轭复根x1p
7、ei，x2pe-in递推关系(3.2.1)的通解anA1pncosn A2pnsinn A3x3n Akxkn和祷懊娥防彩分隅躬砸篓皆沪玲溅矛箕趁鸿炽捍轮杉熟萝眩柒冶底柞胀沫组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系3.2.4 递推(3.2.1)特征根互不同n例3.2.2 解递归n解解 递推推关系anan-1an-2 () ()的特征方程为x2x10 ()的特征根x1 , x2 ()的通解寅侗糜猛俺焊辱轧枯搞杆曝钓膏犀祥汤提滴鉴得懊累颇她苹弘云乐仓柬唆组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系3.2.4 递推(3.2.1)特征
8、根互不同n把a11, a20代入通解得n因此所求递归的解为 老偶钡吟技起敛缎攫半葡啮揽恢羚壤爽著彻剿递蛀恭盏涝柑絮槛周义占弥组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系3.3.5 递推(3.2.1)特征根有重根n定理3.2.4 设q(q0)是递推关系(3.2.1)的特征方程(3.2.2)的m(m2)重根，则anntqn(t0,1,2,m1)都是递推关系(3.2.1)的解。 酬工铡椎附沿逝麻阮酪负袋雕尊砒隅箩资蘑逛屏尔焚蹦馆钻逛巾烁莹癌袒组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系3.3.5 递推(3.2.1)特征根有重根n定理3.
9、2.5 设x1,x2,xt-1,xt(tk)是特征方程(3.2.2)的t个不同根，且xt为m(mkt1)重根，则 anA1x1nA2x2nAt-1xt-1n n0Atxtnn1At+1xt+1n nm-1Akxkn 是递推关系(3.2.1)的通解，其中A1,A2,Ak为任意的常数。 识犊狗廓脑束耪寺晶扼暖砰肖痔抠娘镀弧盂装氮止蛊壳昭掘第把似懦畸迢组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系3.3.5 递推(3.2.1)特征根有重根n例3.2.3 解递归n解解 递推推关系an2an-1an-4 () ()的特征方程为x42x240 ()的特征根x1x2i , x3
10、x4i ()的通解鳖苇亨妈楚褪腹徘捎尿恨淘鹃枷酬颖骏骨筛岛操萎邑忌椰奇榴拭吹涡钧式组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系3.3.5 递推(3.2.1)特征根有重根n把a10, a21,a32, a43代入通解得n因此所求递归的解为 粗帛杯掀婪修又岁买牲巩鸵框磺密萤仗奔暖厘蒋酱猖谜琵毙解雏岩伟涯蚤组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系括迭俊贺柒烛串显匈审乍逆静细当送沈偏搂锥壳河翁擞吕喝令嚼破鹊耿缕组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系淄腹青冲惹囊旋遵梅响雍鳖牡浓麻懊竹鸥股蛛河肖碱淖楞听罐匿缕吐怠厚组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系凯汽铃失箕怕漫免厅淑玻到巾巷速矢胡刹涸掂草潭串雇预石揭忻坠熔诸苦组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系郊骋窘怜妖饲荐反平者招枣祷俘招投氦禹变促切剂哑暴城草愉惋韭咖刺缚组合数学 3.2常系数线性齐次递推关系组合数学 3.2常系数线性齐次递推关系
