第四周-线性常系数递推关系

1组合数学Combinatorics4线性常系数递推关系4-1Fibonacci的兔子定义2第一个月有一对刚诞生的兔子；如果一对兔子每月能生一对小兔（一雄一雌）；而每对小兔在它出生后的第三个月里，又能开始生一对小兔，兔子永不死去；由一对出生的小兔开始，50个月后会有多少对兔子？Month1Month2Month3Month4Month5第n个月相比n-1个月多出的兔子数是n-2个月的兔子生出来的，即Fn=Fn-1+Fn-2•1150年印度数学家研究箱子包裝物件长宽刚好为1和2的可行方法数目时，首先描述这个数列。•在西方，1202年，斐波那契出版的《算盘全书》(Liberabbaci)中提出了一个关于兔子繁殖的问题：•斐波那契，L．(Fibonacci，Leonardo)1175-1250年–波那契(Bonacci)家族的成员;–22岁时随父亲亚非等国家，在那里学会了用印度数码计算；–在西方的数学复兴中起到了先锋作用，在东西方的数学发展中起到了桥梁作用．–G．卡尔达诺(Cardano)：“我们可以假定，所有我们掌握的希腊之外的数学知识都是由于斐波那契的存在而得到的。”LeonardoofPisaFibonacci，Bonacci之子Bonacci:好、自然或简单Fibonaccinumber11235813213455……递推关系:F(n)=F(n-1)+F(n-2)n2初始值:F(0)=0,F(1)=1OEIS:A000045……Fibonacci数•1963年创刊的《斐波那契季刊》(TheFibonacciQuarterly)专门登载有关这个数列的最新发现．其中包括：–最后一位数字，每60个数一循环；最后两位数字，每300个数一循环；最后三位数字，每1500个数一循环；最后四位数字，每15000个数一循环；最后五位数字，每150000个数一循环，等等．–每第三个数可被2整除，每第四个数可被3整除，每第五个数可被5整除，每第六个数可被8整除，等等．这些除数本身也构成斐波那契数列．Fibonacciprime(SequenceA005478inOEIS)–在斐波那契数列中，有素数：2,3,5,13,89,233,1597,28657,514229,433494437,2971215073,99194853094755497,–除了n=4之外，所有的Fibonacciprimes的序号都是素数–但是并不是所有素数序号的斐波那契数都是素数。–相关猜想：斐波那契数列中是否存在无穷多个素数？–目前已知最大素数是第81839个斐波那契数，一共有17103位数。122221nnnFFFFF长方形面积=若干正方形面积之和无字证明vs逻辑演绎证明：)())()(111123243243231232132221221nnnnnnnnFFFFFFFFFFFFFFFFFFFFFFFFFFF________________________122221nnnFFFFF122221nnnFFFFF证明恒等式：F0=0，F1=1，……Fn=Fn-1+Fn-2递推关系证明：1211342231)nnnnnnFFFFFFFFFFFF________________________递推关系9𝐹1+𝐹2+⋯+𝐹𝑛=𝐹𝑛+2−1𝐹1+𝐹2+⋯+𝐹𝑛=𝐹𝑛+2−1F0=0，F1=1，……Fn=Fn-1+Fn-2证明：2221246524321)nnnFFFFFFFFFFF________________________nnFFFFF212531递推关系10nnFFFFF212531具体的表达式？F0=0，F1=1，……Fn=Fn-1+Fn-211组合数学Combinatorics4线性常系数递推关系4-2Fibonacci数的表达式•有一块80厘米的正方形桌布，如何把它改造成长1.3米，宽50厘米的长方形？”魔术881350,1,1,2,3,5,8,13,21,……….35F(n)*F(n)–F(n-1)F(n+1)=(-1)nn=0,1,2更大的桌布？F(100)=?直接表达式？221)(xFxFxG)::23441233FFFxFFFx___________________)())(()(22xGxxxGxxxxGxxGxx)()1(2设Fibonacci递推关系xBxAxxxxxxxG25112511)2511)(2511(1)(2F0=0，F1=1，……Fn=Fn-1+Fn-21)(250BABA{{520BABA51,51BA111515151122()[]Gxxx251512,251512])()[(51222xxnnnnn111515F()(()())(2)225561812511.nnFF14Fibonacci递推关系Fibonacci数列15nnnnn111515F()(()())(2)2255Fn=Fn-1+Fn-261812511.nnFF在选优法上的应用设函数在点取得极大值。要求用若干次试验找到点准确到一定的程度。最简单的方法，把三等分，令：)(xfx),(ba)(32),(3121abaxabax如下图：yx0ab1x2x)(1xf)(2xf)(xfy16§2.4在选优法上的应用依据的大小分别讨论如下：)(),(21xfxf当，则极大点必在区间上，区间可以舍去。)()(21xfxf),(2xa),(2bxyx0)(xfyab1x2x)()(21xfxfyx0)(1xf)(2xfa2x1x17§2.4在选优法上的应用当，则极大点必在区间上，区间可以舍去。)()(21xfxf),(1bx),(1xayx0)(xfyab1x2x)()(21xfxfyx0)(1xf)(2xf2x1xb18§2.4在选优法上的应用当，则极大点必在区间上，区间和均可以舍去。)()(21xfxf),(21xx),(1xa),(2bxyx0)(xfyab1x2x)()(21xfxfyx02x1x)(1xf)(2xf19可见做两次试验，至少可把区间缩至原来区间的2/3，比如，进一步在区间上找极值点。若继续用三等分法，将面对着这一实事，即其中点的试验没发挥其作用。为此设想在区间的两个对称点分别做试验。)()(21xfxf),(2xa1x)1,0(xlx,yx0)(xfy)(1xf)(2xf0x1x120设保留区间，继续在区间的下面两个点x2,(1-x)x处做试验，若),0(x),0(x)1(2xx则前一次的点的试验，这一次可继续使用可节省一次试验。由上式有x1012xx618.0251x02)618.0(382.0618.010x1x10.382，0.6180.236，0.3820.146，0.23621在选优法上的应用这就是所谓的0.618优选法。即若在区间上找单峰极大值时，可在)1,0(3832.0618,01,618.021xx点做试验。比如保留区间，由于，故只要在)618.0,0(328.0)618.0(2236.0328.0618.0点作一次试验。22在选优法上的应用优选法中可利用Fibonacci数列，和0.618法不同之点在于它预先确定试验次数，分两种情况介绍其方法。(a)所有可能试验数正好是某个Fn。102nFnF1nF23这时两个试验点放在Fn-1和Fn-2两个分点上，如果Fn-1分点比较好，则舍去小于Fn-2的部分；留下的部分共Fn-Fn-2=Fn-1个分点，其中第Fn-2和第Fn-3二试验点，对应的原标号是Fn-2+Fn-2=2Fn-2以及Fn-3+Fn-2=Fn-1,恰好Fn-1点是刚才留下来的试验可以利用。102nFnF1nFFn-2+Fn-2=2Fn-2Fn-3+Fn-2=Fn-1如果Fn-2点更好，则舍去大于Fn-1的部分。在留下的部分共Fn-1个分点，下一步Fn-2和Fn-3二试验点中，恰好Fn-2是刚才留下来的试验可以利用。可见在Fn个可能试验中，最多用n-1次试验便可得到所求的极值点。02nFnF1nF利用Fibonacci数列进行优选不同于0.618法之点,还在于它适合于参数只能取整数数值的情况.如若可能试验的数目比小,但比大时,可以虚加几个点凑成个点，但新增加的点的试验不必真做，可认定比其他点都差的点来处理。艾略特波浪(Elliottwave)理论一个完整的循环包括八个波浪，五上三落艾略特波段理论主要反映群众心理经常遇见的回撤比率为0.382、0.5及0.618。一个完整的周期包含8浪，其中5浪上升，3浪下降--这些都是Fibonacci数。再往以下两个层次细分，分别得到34浪和144浪--它们也是Fibonacci数字FnFn-101始终均匀的出手的话从0到1，再下降x保本支撑点x=?y盈利=亏损Fibonacciretracementxy艾略特波浪上升段Fn,下降段Fn-1y盈利：y2/2亏损:(x+y)x/2x+y=1x=0.382xFibonacciretracement30组合数学Combinatorics4线性常系数递推关系4-3线性常系数递推关系•总结特点–线性累加和–右端项为0–系数是常数Fn-Fn-1-Fn-2=0h(n)–3h(n-1)+2h(n-2)=0定义如果序列满足na,02211knknnnaCaCaCa,,,,111100kkdadada及是常数，，则上式称为的k阶常系数线性递推关系，kCCC,,21110,,kddd0kCna21111()(),()hnhnhan=an-1+an–2an–3an-1=an–2=an–3=1(LinearHomogeneousRecurrenceRelations)221)(xFxFxGxxGxx)()1(2设Fibonacci递推关系xBxAxxxxxxxG25112511)2511)(2511(1)(2Fn=Fn-1+Fn-2F0=0,F1=1)2511)(25-1-1)1(2xxxx（因式分解？122(1)1.....axaxax(因式定理)若a是一元多项式f(x)的根，即f(a)=0成立，则多项式f(x)有一个因式x-a．需要（1-ax）的因式，若a是一元多项式f(x-1)的根，即f(a)=0成立，则多项式f(x-1)有一个因式x-1-a=(1-ax)/x．)2511)(25-1-1)1(2xxxx（122(1)1.....axaxax(1-x-x2)=x2((x-1)2-x-1-1)=x2((m)2-m-1)令m=x-1C(m)=m2-m-1=(m-)(m-)m=x-1代回来，得到F(x)=x2(x-1-)(x-1-)=(1-x)(1-x)251512,251512Fn=Fn-1+Fn–2•Fibonacci数列的递归表达式F0=0，F1=1，Fn=Fn-1+Fn–2•Hanoi的递归表达式21()xGxxx1515151511112222()()()xABGxxxxx112)()(nhnhC(x)=x2-3x+2C(x)=0的解为1和21221)()(nhnh02213)()()(nhnhnh相减得到2112132()