四线性常系数递推关系第四周课件版

1、4 线性常系数递推4-1 Fibonacci的兔子定义组合数学Combinatorics第n相比n-1多出的兔子数是n-2第一有一对刚诞生的兔子；的兔子生出来的，即Fn=Fn-1+Fn-2如果一对兔子每月能生一对小兔（一雄一雌）；而每对小兔在它出生后的第三个月里，又能开始生一对小兔， 兔子永不死去；由一对出生的小兔开始，50后会有多少对兔子？2Fibonacci number1 1 2 3 5 8 13 21 34 55OEIS: A000045n³2: F(n)=F(n-1)+F(n-2)递推初始值: F(0)=0, F(1)=1Leonardo of Pisa Fibonacci

2、，Bonacci之子Bonacci: 好、自然或简单1150年数学家研究箱子包裝物件长宽刚好为1和2的可行方法数目时，首先描述这个数列。在西方，1202年，的算盘全书(Liber abbaci)：那契中提出了一个关于兔子繁殖的那契，L(Fibonacci，Leonardo) 1175-1250年波那契(Bonacci)的成员;22岁时随父亲亚非等，在那里学会了用数码计算；在西方的数学复兴中起到了先锋作用，在东西方的数学发展中起到了桥梁作用G(Cardano) ：“我们可以假定，所有我们掌握的希腊之外的数学知识都是由于”那契的而得到的。Fibonacci number1 1 2 3 5 8 13

3、 21 34 55Fibonacci数 1963年创刊的那契季刊(TheFibonacciQuarterly)专门登载有关这个数列的最新发现其中： 最后一位数字，每60个数一循环；最后两位数字，每300个数一循环；最后三位数字，每1500个数一循环；最后四位数字，每15000个数一循环；最后五位数字，每150000个数一循环，等等 每第三个数可被2整除，每第四个数可被3整除， 每第五个数可被5整除，每第六个数可被8整除，等等这些除数本身也那契数列Fibonacci prime (Sequence A005478 in OEIS) 在那契数列中，有素数： 2, 3, 5, 13, 89, 233

4、,1597, 28657, 514229, 433494437, 2971215073,99194853094755497, 除了n = 4之外，所有的Fibonacci primes的序号都是素数 但是并不是所有素数序号的那契数都是素数。 相关猜想：那契数列中是否无穷多个素数？那契数，一共有 目前已知最大素数是第81839个17103位数。F 22+ F 22+L+ F= F Fnn+11n长方形面积=若干正方形面积之和无字证明 vs逻辑演绎F0 = 0，F1 = 1 ， 递推Fn = Fn - 1 + Fn - 2证明恒等式：F 2 + F 22 +L+ F2= F Fnn+11n证明：F

5、 2 = F F121F0 = 0，F1 = 1 ， 递推Fn = Fn - 1 + Fn - 2𝐹1 + 𝐹2 + + 𝐹𝑛 = 𝐹𝑛 + 2 1= F3 - F2= F4 - F3LLF1F2证明：= Fn+1- FnFn-1Fn+)= Fn+2 - Fn+1𝐹1 + 𝐹2 + + 𝐹𝑛 = 𝐹𝑛 + 2 19F0 = 0，F1 = 1 ， 递推Fn = Fn - 1 + Fn - 2F1 + F3证

6、明：+ F5+L+ F2n-1= F2n= FF12= F4 - F2= F6 - F4LLF3F5具体的表达式？+)= F2n- F2n-2F2n-1F1 + F3 + F5 +L+ F2n-1= F2n104 线性常系数递推4-2 Fibonacci数的表达式组合数学Combinatorics魔术有一块80厘米的正方形桌布，如何把它改造成长1.3米，宽50厘米的长方形？ ”0, 1, 1, 2, 3, 5, 8, 13, 21,.58F(n)*F(n) F(n-1)F(n+1) = (-1)nn=0,1,2更大的桌布？F(100)=?直接表达式？38135baF0 = 0，F1 = 1 ，

7、 Fibonacci递推Fn = Fn - 1 + Fn - 2设: F = F + Fx3x4321: F = F + F432+)G(x) -LLLLL(G(2G(x)(1 - x - x2 )G(x) = xxxABG(x) =+1- x - x21-51+51+1-55(1-x)(1-1-x1-x)x2222G(x) = F x + F x2 +L12Fibonacci递推A + B = 0A + B = 05 ( A - B) = 1 A - B =11A =B = -,2555=2G( x) = 1 1-11(a- b)x + (a2 - b2 )x2+L5 1- 1+5 x1-

8、1-5 x52- 22= 1 += 1 -5 ,25ab =1 -1 +5252= 1 +Fn5» 1.61814F2n-1F =1 (an - bn ) =1 (1 +5 )n - (1 -5 )n )n5522Fibonacci数列1 (1 +5 )n - (1 -15 )n )F =(an - bn ) =F= F+ Fnn - 1n - 2n2255= 1 +Fn5» 1.618Fn-1215在选优法上的应用x = x 点取得极大值。要求f (x) 在设函数用若干次试验找到x 点准确到一定的程度。最，把(a, b) 三等分，令：简单的x = a + 1 (b - a

9、),x= a + 2 (b - a)1233y如下图：y =f (x)f (x1 )f ( x2 )x0ax1x2b16§2.4在选优法上的应用依据f (x1 ), f (x2 )的大小分别讨论如下：f (x2 )，则极大点x 必在(a, x2 ) 区间当 f (x1 ) >上，区间 (x2 , b) 可以。yyy =f (x)f (x1 )f ( x2 )x0ax1x1x2axx20bf (x1 ) >f (x2 )17§2.4在选优法上的应用f (x2 )，则极大点x当f (x1 ) <必在(x1 , b) 区间上，区间(a, x1) 可以。y =f

10、(x)yyf (x1 ) f (x )2x0ax1x2x0x1x2bbf (x1 ) <f (x2 )18§2.4在选优法上的应用f (x2 )，则极大点x当f (x1 ) =必在(x1 , x2 )区间。上，区间(a, x1 ) 和(x2 , b) 均可以yyy =f (x)f (x1 ) f (x )2x0ax1x1x2x0x2bf (x1 ) =f (x2 )19y = f (x)f (x1 )f ( x2 )x0可见做两次试验，至少可把区间缩至原来区间的2/3，比如 f (x1 ) > f (x2 ) ，进一步在(a, x2 )区间上找极值点。若继续用三等分法，将

11、面对着这一实事，即其中 x1 点的试验没发挥其作用。为此设想在(0,1)区间的两个对称点x, l - x 分别做试验。1- xx01201- xx01设保留(0, x)区间，继续在(0, x) 区间的下面两个点x2,(1-x)x处做试验，若= (1- x)x2则前一次1 - x 的点的试验，这一次可继续使用可节省一次试验。由上式有+ x -1 = 0x2-1 +0.382，0.6180.236，0.3820.146，0.2365x = 0.61820.382 = (0.618)200.618121在选优法上的应用(0,1) 区这就是所谓的0.618优选法。即若在间上找单峰极大值时，可在x1 =

12、 0.618,x2 = 1 - 0,618 = 0.3832点做试验。比如保留区间(0,0.618)，由于(0.618)2 = 0.328 ，故只要在0.618 ´ 0.328 = 0.236点作一次试验。22在选优法上的应用优选法中可利用Fibonacci数列，和0.618法不同之点在于它预先确定试验次数，分两种情况介绍其方法。(a) 所有可能试验数正好是某个Fn。Fn-2Fn-1123l 这时两个试验点放在Fn-1和Fn-2两个分点上，l 如果Fn-1分点比较好，则舍去小于Fn-2的部分；l 留下的部分共Fn-Fn-2 = Fn-1个分点，l 其中第Fn-2和第Fn-3二试验点，

13、对应的原标号是Fn-2+Fn-2=2Fn-2以及Fn-3+Fn-2=Fn-1,恰好Fn-1点是刚才留下来的试验可以利用。Fn-2+Fn-2=2Fn-2Fn-3+Fn-2=Fn-1Fn-2Fn-1l 如果Fn-2点更好，则舍去大于Fn-1的部分。l 在留下的部分共Fn-1个分点，下一步Fn-2和Fn-3二试验点中，恰好Fn-2是刚才留下来的试验可以利用。可见在Fn个可能试验中，最多用n-1次试验便可得到所求的极值点。Fn-2利用Fibonacci数列进行优选不同于Fn-10.618法之点,还在于它适合于参数只能取整数数值的情况.如若可能试验的数目比小,但比大时,可以虚加几个点凑成个点，但新增加的

14、点的试验不必真做，可认定比其他点都差的点来处理。波浪(Elliott wave)理论一个完整的循环八个波浪，五上三落一个完整的周期包含8浪，其中5Fn-1Fn浪上升，3浪下降-这些都是Fibonacci数。再往以下两个层次细分，分别得到34浪和144浪-它们也是Fibonacci数字经常遇见的回撤比率为0.382、0.5及0.618。波段理论主要反映群众心理Fibonacci retracement1波浪上升段Fn, 下降段Fn-1y= 亏损：y2/2亏损: (x+y)x/2x+y=1x=0.382y0始终均匀的出手的话从0到1，再下降x 保本支撑点x=?yxxFibonacci retrac

15、ement4 线性常系数递推4-3 线性常系数递推组合数学CombinatoricsFn-Fn-1-Fn-2=0h(n) 3h(n-1)+2h(n-2)=0如果序列an 满足定义an总结特点 线性累加和+ C1an-1 + C2an-2+L+ Ck an-k= 0,a= d , a = d ,L, a= d,k -1k -10011 右端 系数是0C , C,LC¹ 0，则上式，Ckd, d ,Ld及 01 是k -112k称为 a的k阶常系数线性递推，n(Linear Homogeneous Recurrence Relations)h ( n ) = 2 h ( n - 1) +

16、 1,h (1) = 1an = an - 1 + an 2 an 3an - 1 = an 2 =an 3 = 1Fn=Fn-1+Fn-2F0=0, F1=1Fibonacci递推(1 - x - x2 )G(x) = x设xxABG(x) =+1- x - x21+1-551-1-xx22因式分解？(1- ax)-1 = 1+ ax + a2 x2 + .(1- x -)22(1- 1-5 x)(1- 1+5 x)22G(x) = F x + F x2 +L12(因式定理) 若a是一元多项式f(x)的根，即f(a)=0成立，则多项式f(x)有一个因式x-a 需要（1-ax）的因式，若a是一

17、元多项式f(x-1)的根，即f(a)=0成立，则多项式f(x-1)有一个因式x-1-a=(1-ax)/x(1- ax)-1 = 1+ ax + a2 x2 + .(1-x-x2)= x2(x-1)2-x-1-1)=x2(m)2-m-1)令m=x-1C(m) = m2-m-1=(m-a)(m-b)(1- x -)22- 21 +5a=1 -=,25Fn= Fn - 1 + Fn 2m=x-1代回来，得到= 1 -25F(x) = x2(x-1- a)(x-1- b)=(1- a x)(1- b x)b=1 +25 线性常系数递推 Fibonacci数列的递归表达式x=(1 - ax)(1 - b

18、x)GF0 = 0，F1 = 1 ，分母变成F(x) = x2(x-1)2-x-1-1)=x2(m)2-m-1) 令m=x-1(m-a)(m-b)C(m) =a = 1 +5 ,b = 1 -5m=x-1代回来，得到22F(x) = x2(x-1- a)(x-1- b)=(1- a x)(1- b x)x5 x)(1- 1+- 1(2Hanoi的递归表达式h(n) - 2h(n - 1) = 1H)h(n - 1) - 2h(n - 2) = 1相减得2C(x)=0的1和2C(x) = x -3x+2h(n) - 3h(n - 1) + 2h(nm2-m-1=Fn = Fn - 1 + Fn

19、22+ C1an-1 + C2an-2+L+ Ck an-k= 0,an线性常系数递推设G(x)为an的母函数G(x) = a+ a x +L+ a+Lxn01nxk (a+ C a+ C a+L+ C a ) = 01k -12k -2kk0xk +1 (aLL+ C a+ C a+L+ C a ) = 0k +12k -11kk1xn (a+ C a+ C a+L+ C a) = 01n-12n-2kn-knLL将这些式子两边分别相加，得到k -1G(x)- åæk -2)- åö(a xi +C1 xç G xa xi ÷ii&

20、#232;øi =0i =0+L+ C xkG(x) = 0k线性常系数递推k -1- j(1+ C x + C)G(x) = åCk -1å i+L+ Cx2xkx jia x12kjj =0i=0k -1- jk -1令P(x) = åCj=0G(x) =åi=0x ji,多项式P(x)的次数k-1。a xjiP(x)()1+ C1x +L+ Ck xk+ C1an-1 + C2an-2+L+ Ck an-k= 0,anC(m) = (m - a)k1(m - a)k2L(m - a)ki12ik1 + k2 +L+ ki= k=P(x)(

21、1- a x) (1- a x) L(1- a x)kkk12i12iC(m) = mk + C mk-1 +L+ Cm + C1k -1k(1- ax)-1 = 1+ ax + a2 x2 + .线性常系数递推Fn-Fn-1-Fn-2=0x2-x-1=0h(n) 3h(n-1)+2h(n-2)=0x2-3x+2=0如果序列an 满足定义an+ C1an-1 + C2an-2+L+ Ck an-k= 0,a0 = d0 , a1 = d1,L, ak -1 = dk -1,C1, C2 ,LCk及d0 , d1 ,Ldk -1¹ 0，则上式，Ck是称为an 的k阶常系数线性递推，(L

22、inear Homogeneous Recurrence Relations)特征多项式C(x) = xk + C xk-1 +L+ Cx + C1k -1kFn-Fn-1-Fn-2=0定义anh(n) 3h(n-1)+2h(n-2)=0如果序列an 满足+ C1an-1 + C2an-2+L+ Ck an-k= 0,a0 = d0 , a1 = d1,L, ak -1 = dk -1,C1, C2 ,LCk及d0 , d1 ,Ldk -1¹ 0，则上式，Ck是称为an 的k阶常系数线性递推，(Linear Homogeneous Recurrence Relations)特征多项式

23、C(x) = xk + C xk-1 +L+ Cx + C1k -1k线性常系数齐次递推以下分别各种情况讨论具体计算的（1）特征多项式C (x)无重根。C(x) = (G(x)可简化为-ak )设l1 , l2 ,L, lk可由线性方程组l1 + l2 +L+ lk = d0l1l2lkìG(x) =+L+ï1-a1x1-a2 x1-ak xl1a1 + l2a2 +L+ lkak = d0.ïíïkliå=i=1 1-ai xïk -k -k -la+ l a+L+ la= d111î 1k -1122kk其中d

24、0,d1dk是an的初始值(1- ax)-1 = 1+ ax + a2 x2 + .ka = ålanniii=1线性常系数齐次递推Fibonacci数列Linear Homogeneous Recurrence RelationF0 = 0，F1 = 1 ，定义 如果序列a 满足na+ C a+ C a+ L + C a= 0,1n-12n-2kn-kna0 = d0 , a1 = d1 ,L, ak -1 = dk -1 ,特征多项式C(x) = x2-x-1=(x-a)(x-b)C , C,LC及d, d ,L d是。k -112k01a = 1+5 ; b = 1-5特征多项

25、式22C ( x) = xk+ C xk -1+ L + Cx + CF = Aa n + Bb nk -11knF0 = 0，1）特征多项式无重根，k个不同的实数解C (x ) = (x - a1 )(x - a2 )L (x - ak)F1 = 1= l an + l an+ L + lanaA + B = 0n1122kk51 +1 -1155( A - B) = 1F =(an - bn ) =- ()n)n )(2n2255Fn = Fn - 1 + Fn 2母函数定义2-1对于序列a0, a1, a2, 构造一函数G(x)= a0+a1x+a2x2+,拉斯称G(x)为序列a , a

26、 , a 的母函数。0121812年lll1705年前递推1764年前整数拆分a+ C a+ C a+ L + C a= 0,1n-12n-2kn-kn母函数G(x)为桥梁a= l an+ l+ L + lanann1122kk似函数,非函数,是C ( x) = xk + C xk-1 + L + Cx + C1k -1k线性常系数齐次递推定义如果序列an满足(2 - 5 - 1)(2 - 5 - 2)。+ C1an-1 + C2 an-2+ L + Ck an-k= 0,ana0 = d0 , a1 = d1 ,L, ak -1 = dk -1 ,C1 , C2 ,LCk 及d0 , d1,

27、L dk-1 是+ C xk -1特征多项式 C ( x) = xk+ L + Cx + Ck -11k1）特征多项式无重根，k个不同的实数解C (x ) = (x - a1 )(x - a2 )L (x - ak )a= l an + l an + L + lann1122kk其中 l1 , l2 ,L, lk ,是待定系数¥1¥a (a -1).(a - n +1)åk =0(1+ x)= å(k +1)xk =ana Î Rx(1- x)2n!n=0特征多项式有多重根an - 4an-1 + 4an-2= 0，a0 = 1,a1 = 4特

28、征根法特征方程：x2-4x+4=(x-2)2例母函数法: a(2) = 4a(1) - 4a(0): a(3) = 4a(2) - 4a(1)L L L L2x2x3ax + b母函数形式：A( x) =部分分式：AA(x) = A(1+ 2x + 22 x2 + .) + B(1+ 2+ )A(1 - 2 x)22)2 + .)A)2= A(1+ 2x + 22 x2 + .) + B(1+ 2´ (2x) + 3´ (2x)2 + .)¥= (1 - 2x)-2 = åC (k + 1, k )2kxka= A ´ 2n + B(n + 1

29、)2n = ( A '+ Bn)2nna0 = A ' = 1,a1 = (1 + B)2 = 4k =0¥= å(k +1)2kk =0xkA ' = 1,B = 1a= (n + 1)2n na= (n + 1)2n nAijkiåt= åG( x)(1 - ai x)j¥a (a -1).(a - n +1) n!i=1j=1(1+ x)a = åxna Î Rn=0（2）特征多项式C(x)有重根Ak设是C(x)的k重根，则G(x)可简化为åj(1 - bx) jj=1æ j

30、 + n -1ökan = å Aj ç÷bnxn的系数。 其中nèøj=1j + n -1ö = æ j + n -1öæçè÷ç÷j -1nøèø是n的j-1次多项式。因此，an是与n的k-1次多项式的乘积。则递推的解对应于的nk -1)b n( A + A n +L+ Ak -101其中A0 , A1,L, Ak -1 是k个待定。an - 4an-1 + 4an-2 = 0，a0 = 1,a1 = 4例- 2

31、）2特征方程为：a= ( A + A n)2nn12a0= A1= 1a1=（1+ A2）2 = 4,an=（1+ n）2n= 1A2共轭复根？重根无重根- x +1 = 0x2共轭复根一元二次方程求根公式当b2-4ac<0，方程无实根，在复数范围有两个复根。a1 = r (cosq + i sin q ),a 2 = a1 = r (cos q - i sin q )复数z = a + bi化为三角形式： z = (cos+ i sin)r =a2+ b2 §2.5线性常系数递推（3）特征多项式 C(x) 有共轭复根是C(x) 的一对共轭复根。a1,a 2设a= r (cos

32、 q + i s in q ),a= a= r (cos q - i s in q )121A11 - a1 xA21 - a 2 x中 xn 的系数是+A a n + A a n1 12 2 线性常系数递推 A a n + A a n1122= ( A + A )r n cos nq + i( A - A )r n sin nq1212= Ar n cos nq + Br n sin nqA = A1 + A2 ,B = i( A1 - A2 )其中在具体计算时，可先求出各对共轭复根，再求待定系数A，B，避免中间过程的复数运算。A a+ A a= Arcos nq + Brsin nqnn2

33、nn112= an-1 - an-2,a1= 1,a2 = 0an例- x +1 = 0x2特征方程为：p3p1±- 3±p ix = cos± i sin= e323a= A cos npsin np+ An123= 13a= 1 A3 A+112223A1 = 1;A2 =31 32a2 = - 2 A1 += 0A2a= cos np+ 3 sin npn333总结线性常系数递推根据特征多项式C(x)的非零解的情况C(x) = (x - a1 )(x - a2 )L(x - ak )1)有k个不同非零实数解a= l an + l an +L+ l ann11

34、22kk其中 l1, l2 ,L, lk ,是待定系数2)有一对共轭复根a= reiq 和a= re-iq 时，12a= Ar n cos nq + Br n sinnqn其中A，B是待定。3)有k重根。不妨设a1是k重根。a( A + A n +L+ Ak -1nn)k -1011其中A0 , A1,L, Ak-1是k个待定。4 线性常系数递推4-4 应用举例组合数学Combinatorics 线性常系数递推 nSn = å kSn = 1 + 2 + 3 + L + (n - 1) + n例：求k =0= 1 + 2 + 3 + L + (n - 1)Sn-1 Sn同理相减得同理

35、- Sn-1= nSn-1 - Sn-2= n - 1Sn - 2Sn-1Sn-1+ Sn-2= 1- 2Sn-2+ Sn-3= 1Sn - 3Sn-1 + 3Sn-2- Sn-3= 0S0 = 0,S1 = 1,S2 = 3Sn - 3Sn-1 + 3Sn-2- Sn-3= 0S0= 0,S1 = 1,S2= 3对应的特征方程为- 3m2 + 3m - 1 = (m - 1)3 = 0m3m = 1是三重根Sn = ( A + Bn + Cn )(1)= A + Bn + Cn2n2S0 = 0,S1 = 1,A = 0B + C = 1 B = C = 1S = 3,2B + 4C = 3,22n(n + 1)111S=n +=n2即n2221这就证明了 1 + 2 + 3 +L + n = 2 n(n + 1) 线性常系数n递推= å k 2例2：求Snk =0Sn = 1同理Sn - S- SSn-1