📄 2_5.htm
字号:
<head><title>组合数学</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"></head><h1>§2.5 线性常系数递推关系 </h1><p> 定义 如果序列{a<sub>n</sub>}满足</p> <p> <img border="0" src="2_5.pic/image004.gif" width="304" height="48"></p><p>C<sub>1</sub>,C<sub>2</sub>,<sup>...</sup>,C<sub>k</sub>及d<sub>0</sub>,d<sub>1</sub>,<sup>...</sup>,d<sub>k-1</sub>是常数，C<sub>k</sub><>0，则(2-5-1)称为{a<sub>n</sub>}的k阶常系数线性递推关系，(2-5-2)称为{a<sub>n</sub>}的初始条件， 称C(x)=x<sup>k</sup>+C<sub>1</sub>x<sup>k-1</sup>+<sup>...</sup>+C<sub>k-1</sub>x+C<sub>k</sub>为{a<sub>n</sub>}的特征多项式 </p> <p> 设G(x)为{a<sub>n</sub>}的母函数 根据(2-5-1)，有 </p> <p> <img border="0" src="2_5.pic/image019.gif" width="200" height="25"></p><p>将这些式子两边分别相加，得到 </p><p> <img border="0" src="2_5.pic/image021.gif" width="263" height="119"></p><p>即 </p><p> <img border="0" src="2_5.pic/image023.gif" width="232" height="75"></p><p> <img border="0" src="2_5.pic/image025.gif" width="319" height="48"></p><p>其中C<sub>0</sub>=1</p><p> 令 </p> <p> <img border="0" src="2_5.pic/image029.gif" width="148" height="48">，</p><p>多项式P(x)的次 数不大于k-1。 特征多项式C(x)=x<sup>k</sup>+C<sub>1</sub>x<sup>k-1</sup>+<sup>...</sup>+C<sub>k-1</sub>x+C<sub>k</sub>因此， </p> <p> <img border="0" src="2_5.pic/image033.gif" width="187" height="45"></p><p>是k次多项式，我们知道C(x)=0在复数域中有k个根。设 </p><p> <img border="0" src="2_5.pic/image035.gif" width="233" height="51"></p><p>则 </p><p> <img border="0" src="2_5.pic/image037.gif" width="268" height="75"></p><p>于是 (1+C<sub>1</sub>x+<sup>...</sup>+C<sub>k-1</sub>x<sup>k</sup>)G(x)=P(x)</p><p> <img border="0" src="2_5.pic/image041.gif" width="315" height="93"></p><p>(2-5-3)式是有理式，且分子的次数低于分母的次数，有分项表示，即： </p><p> <img border="0" src="2_5.pic/image043.gif" width="293" height="171"></p><p> <img border="0" src="2_5.pic/image045.gif" width="253" height="48"></p><p>x<sup>n</sup> 的系数是 </p> <p> <img border="0" src="2_5.pic/image049.gif" width="173" height="48">。 </p><p>A<sub>ij</sub>是常数。 </p><p> 定理：设P(x)/Q(x)是有理分式，多项式的P(x)次数低于Q(x)的次数。则P(x)/Q(x)有分项表示，且表示唯一 </p> <p> 证明：设Q(x)的次数为n，对n用数学归纳法。 </p> <p> n=1时，P(x)是常数，命题成立。 </p> <p> 假设对小于n的正整数，命题成立。 </p> <p> 下面证明对正整数n命题成立。设a 是Q(x)的k重根， </p> <p> <img border="0" src="2_5.pic/image056.gif" width="216" height="24"></p><p>不妨设P(x)与Q(x)互素，设 </p><p> <img border="0" src="2_5.pic/image058.gif" width="219" height="168"></p><p>P(x)的次数低于Q(x)。根据归纳假设， </p><p> <img border="0" src="2_5.pic/image060.gif" width="93" height="45"></p><p>可分项表示。因此，P(x)/Q(x)可分项表示。由(2-5-6)式及(2-5-7)式可知表示是唯一的。 </p><p> 以下分别各种情况讨论具体计算的问题。 </p> <p> （1）特征多项式C(x)无重根 </p> <p> 设 C(x)=(x-a<sub>1</sub>)(x-a<sub>1</sub>)<sup>...</sup>(x-a<sub>1</sub>)，(2-5-4)可见化为 </p><p> <img border="0" src="2_5.pic/image065.gif" width="241" height="93"></p><p> x<sup>n</sup>的系数是 </p><p> <img border="0" src="2_5.pic/image068.gif" width="203" height="45"></p><p> A<sub>1</sub>,A<sub>2</sub>,<sup>...</sup>,A<sub>k</sub>可由线性方程组 </p><p> <img border="0" src="2_5.pic/image072.gif" width="281" height="101"></p><p>解出。 </p><p> (2-5-10)的系数矩阵的行列式是Vander mond 行列式 </p> <p> <img border="0" src="2_5.pic/image074.gif" width="211" height="139"></p><p>不难看出(2-5-10)有唯一解。 </p><p> （2）特征多项式C(x)有共轭复根，设 是C(x)的一对共轭复根。 </p> <p> <img border="0" src="2_5.pic/image078.gif" width="308" height="25"></p><p> <img border="0" src="2_5.pic/image080.gif" width="104" height="45"></p><p>中x<sup>n</sup> 的系数是 </p><p> <img border="0" src="2_5.pic/image083.gif" width="324" height="131"></p><p>其中 A=A<sub>1</sub>+A<sub>2</sub>, B=i(A<sub>1</sub>-A<sub>2</sub>)</p><p> 在具体计算时，可先求出各对共轭复根，再求待定系数A，B，避免中间过程的复数运算。 </p><p> （3）特征多项式C(x)有重根 </p> <p> 设a是C(x)的k重根，则(2-5-4)可简化为 </p> <p> <img border="0" src="2_5.pic/image087.gif" width="77" height="45"></p><p>的系数 </p><p> <img border="0" src="2_5.pic/image090.gif" width="149" height="48">。</p><p>其中 </p><p> <img border="0" src="2_5.pic/image092.gif" width="149" height="48"></p><p>是n的j-1次多项式。因此，a<sub>n</sub>是à<sup>n</sup>与n的k-1次多项式的乘积。 </p><p> 为了简化计算，下面引入一些记号，介绍几个命题。 </p> <p> 设x是任意变量，n是非负整数，令 </p> <p> <img border="0" src="2_5.pic/image098.gif" width="269" height="69"></p><p>不难证明，多项式f(x)=a<sub>n</sub>x<sup>n</sup>+a<sub>n-1</sub>x<sup>n-1</sup>+<sup>...</sup>+a<sub>1</sub>x+a<sub>0</sub> 可用 </p><p> <img border="0" src="2_5.pic/image102.gif" width="101" height="48"></p><p>唯一线性表示。其中a<sub>k</sub> (k=0..n)是常数 </p><p> 设{a<sub>n</sub>}是给定序列，令 </p><p> <img border="0" src="2_5.pic/image108.gif" width="227" height="25"></p><p><img border="0" src="2_5.pic/image110.gif" width="33" height="25">， 称为a<sub>n</sub>的k阶差分。 </p><p> 不难证明，如果对任意的n有 </p><p> <img border="0" src="2_5.pic/image113.gif" width="57" height="25">，</p><p>则有 </p><p> <img border="0" src="2_5.pic/image115.gif" width="135" height="48"></p><p>因而序列{a<sub>n</sub>}的特征多项式为C(x)=(1-x)<sup>þ</sup></p><p> 不难证明，如果<img border="0" src="2_5.pic/image110.gif" width="33" height="25">是n的r次多项式，则a<sub>n</sub> 是n的r+1次多项式。 </p><p> 以上几个命题作为习题，请读者自己证明。 </p> <p> 总之： </p> <p> (1)若特征多项式C(x)有n个不同零点a<sub>0</sub>,a<sub>1</sub>,<sup>...</sup>,a<sub>n</sub> 则递推关系(2-5-1)的解a<sub>k</sub>=l<sub>1</sub>a<sub>1</sub><sup>k</sup>+l<sub>2</sub>a<sub>2</sub><sup>k</sup>+<sup>...</sup>+l<sub>n</sub>a<sub>n</sub><sup>k</sup> 其中l<sub>1</sub>l<sub>2</sub><sup>...</sup>l<sub>n</sub> 是待定系数，有初始条件(2-5-2)来确定。 </p><p> (2)若特征多项式C(x)有不同的复根，可依照(1)的办法处理。不过任意复数a+bi可写为<img border="0" src="2_5.pic/image129.gif" width="31" height="24">形式，设</p><p> <img border="0" src="2_5.pic/image131.gif" width="184" height="24"></p><p> 是C(x)的一个零点，其共轭复根为 </p><blockquote><p> <img border="0" src="2_5.pic/image133.gif" width="192" height="24"></p><p> <img border="0" src="2_5.pic/image135.gif" width="257" height="77"></p></blockquote><p>l<sub>1</sub>+l<sub>2</sub> 和i(l<sub>1</sub>+l<sub>2</sub>) 仍然是待定常数。即C(x)=0有一对共轭复根</p> <p> <img border="0" src="2_5.pic/image141.gif" width="61" height="24"> </p><p>和</p><p> <img border="0" src="2_5.pic/image143.gif" width="69" height="24"></p><p>时，递推关系(2-5-1)的解有对应的项 </p><p> <img border="0" src="2_5.pic/image145.gif" width="160" height="24"></p><p>其中A，B是待定常数。 </p><p> (3)若C(x) k重根。不妨设a<sub>1</sub>是k的重根。则递推关系(2-5-1)的解对应于的项为 </p><p> <img border="0" src="2_5.pic/image149.gif" width="176" height="25"></p><p>其中A<sub>0</sub>,A<sub>1</sub>,<sup>...</sup>,A<sub>k</sub> 是k个待定常数。 </p>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -