当前课程知识点:组合数学 > 线性常系数递推关系 > Fibonacci数列的应用 > Fibonacci的直接表达式
那么我们下面呢就来分析一下
怎么去计算斐波那契的直接表达式
当然对于斐波那契来说
有很多种方法可以去计算它的直接表达式
这里面我们想给大家介绍一下母函数的方法
既然我们想用母函数的方法来算斐波那契表达式
首先我们需要有一个母函数
这里面我们用gx来表示斐波那契的母函数
说起母函数实际上就是把序列作为xk次方的系数
这里面因为我们知道
f0是等于0的
所以我们从f1x一直加到f2x平方
一直累加过去
这个式子实际上就是斐波那契的母函数
如果我们能够把母函数的表达式计算出来
自然就可以推广出来对应于序列它是长什么样子了
那么我们来分析一下
我们前面介绍过汉诺塔问题
我们是通过把它每一项每一项累加起来
来分析出gx的表达式是什么
我们同样采用同样的方法
对应于我们从x3次方开始加起
x3次方它的系数是f3
而f3根据递推关系等于f2加f1
x4次方它的系数是f4
也等于f3加f2
这样依次的累加出来
我们得到了一个序列
左边对应于就和gx是一样的
只是缺了前两项
所以左边等于gx减去x平方减去x
注意
这里面因为f1和f2系数都为1
因此我在这里面就省略了
而右边呢
右边实际上有两个项
我们分别来看
比如说这里对应的f2实际上它应该也是累乘x的3次方
f1也要累乘x的3次方
对于f3乘的x4次方
但是在原来的母函数中间
f2对应的是x平方
f3对应的是x的3次方
因此在这个式子累加过程中
它实际上多了一个x
那么把x提出来之后
后面还剩什么呢
后面的式子变成了f2乘以x的平方
加上f3乘以x3次方
和原来母函数相比
缺了仅仅是第一项
因此右端的第一项实际上累加起来就是等于x乘以gx减x
而第二项呢
第二项变成了f1乘以x的3次方
f2乘以x4次方
依次累加出来
对应于和原来的gx相比
它实际上多乘了x平方项
因此右端的累加和
就应该等于x平方乘以gx
这时候我们已经列出了有关gx的一个等式
那么gx应该长什么样子呢
我们直接就把它整理出来
变成1减x减x平方乘以gx
等于x
所以我们就能推出gx等于x除以1减x减x平方
而这里面我们因为想要把它进行展开分式之和
因此对于分母我们要进行一系列的变换
变成1减αx的样子
这里正好1减x减x平方
正好等于1减1减根号5
除以2x乘以1减1/2加根号5x
而这时候我们根据原来求汉诺塔的形式
我们就可以把它转化成了
变成两个分式之和
而其中一个分式
正好是这个因子构成了分母
比如说这里分母就是1减1/2加根号5x
当然它上面的系数应该得多少呢
我们并不知道
我们用a来代替
这作为一个待定系数
后续我们再通过解方程求解
另外一项变成了1减1/2 1减根号5x分之b
当然b作为一个待定系数也在这里面
作为a和b两个待定系数
通过下面的分式呢
来进一步的求解
这个式子就应该等于x除以1减x减x平方
那么至于a和b等于多少
我们就可以进一步的求解
其中a加b根据刚才的对应于分子是x
因此它的常系数应该得0
而它的一次项系数呢
正好是二分之根号五
a减b应该等于1
那么下面应该求解之后
我们就知道对应的a加b等于0
a减b等于根号五分之二
求出来a等于根号五分之一
b等于负的根号五分之一
这时候a和b都有了
自然我们就知道gx长什么样子了
把a和b代入
gx就正好等于根号五分之一乘以1减1/2加根号5x分之一
减去1减1/2 1减根号5x分之一
那这个时候我们知道
这个式子就可以利用泰勒展开变成α的k次方
乘以xk次方
这个系数呢
可以变成β乘以x的n次方
乘以x的n次方
因此我们为了简便起见
用α代替1/2加根号5
β变成了1/2减根号5
左边这个式子就可以变成了一个多项的累加和
变成了根号5分之一乘以α减去βx加α平方
减去β平方x平方
依次累加
这个时候我们引入了α和β之后
发现gx表达式就更加的容易
而对应的系数就应该是我们原来说的斐波那契数的序列
这里fn作为gx每一项xn次方前面的系数
就等于根号5分之一αn次方减去βn次方
代入α等于1/2加上根号5
β等于1/2加根号5
这时候我们可以列出斐波那契数第n项
它的表达式就等于根号5分之一乘以1/2加根号5的n次方
减去二分之一减根号5的n次方
走到这里
我们发现
我们已经得到了对应的斐波那契数的展开式了
而一个很神奇的地方在于
如果我们拿第n项的斐波那契数
除以第n减1项的斐波那契数
也就是刚才这样的式子
我们分别代入n和n减1之后
经过化解
刚好等于1/2加根号5
而1/2加根号5是什么呢
它正好就是我们的黄金分割1.618
刚才我给大家用母函数的方法求解出了斐波那契序列的直接表达式
大家可以看
斐波那契的递推关系非常的简单
fn等于fn减1加上fn减2
但是求出来的直接表达式
却是代了这么多根号一个事情
明明这个fn是一个整数
但是我们的直接表达式却用了一些无理数来表示
可以看到斐波那契实际上建立了从自然数和无理数之间的一种对应关系
而更多神奇的是两个相邻的fn和fn减1进行相除
它的比例正好是黄金分割点
而黄金分割实际上也可以用这样一个累加的方式进行表达
可以看到数学形式虽然多种多样
从中总有千丝万缕的联系
如果我们还是按照斐波那契这样的排列把它排出来之后
会得到一个这样一个黄金分割的曲线
而现实生活中
大家可以看到自然界也是应用了很多很多这样的黄金分割
所以说呢斐波那契实际上具有神奇的魔力
而且它在我们现实生活中很有巨大的应用
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(1)
--采访武永卫老师
-第一周作业
--作业说明
--H
--U
--G
--作业讨论区说明
-第一周演示程序
--程序讨论区说明
--幻方生成器
--换方计数
--屏幕解锁方案数
--欧拉路计数
--共享程序
-加减乘除来计数
--计数的基本法则
-排列还是组合
--排列还是组合
--小乒乓球的组合之旅--排列还是组合
-各种各样的排列
--圆排列和项链排列
--圆排列和项链排列--习题
--多重排列
--多重排列--练习
-多样的组合
--可重组合
--不相邻组合
--小乒乓球的组合之旅--多样的组合
-钟声里的全排列
--钟声里的全排列
--钟声里的全排列
--字典序法
--SJT算法
-第二周作业
--H
--U
--G
--思考题
--公式测试
--作业讨论区说明
-第二周演示程序
--程序讨论区说明
--全排列生成
--组合生成器
--共享程序
-参考资料:Stirling估计式
-母函数是函数的母亲吗
--母函数的定义(1)--练习
--母函数的定义(2)--练习
-母函数的简单应用
--初识母函数--母函数的简单应用
-整数拆分
--整数拆分(1)
--整数拆分(2)
-Ferrers图像
--Ferrers图像--作业
-母函数与递推关系
--母函数能做什么
--偶数个5怎样算
--母函数小结
-大家谈组合数学(2)
-第三周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第三周演示程序
--程序讨论区说明
--整数拆分
--汉诺塔
--共享程序说明
-Fibonacci数列
--线性常系数递推关系--Fibonacci数列
-Fibonacci数列的应用
--桌布魔术
--桌布魔术--练习
--艾略特波浪曲线
-线性常系数齐次递推关系
--定义
--特征多项式
--线性常系数递推关系--线性常系数齐次递推关系
-说“数”解题
-第四周作业
--H
--U
--G
--GT思考题
--作业讨论区说明
-第四周演示程序
--程序讨论区说明
--程序共享说明
-爆笑花絮
--爆笑花絮
-参考资料:K线分析中的Fibonacci 相关理论
-Catalan数
--计算机界的精灵
--神奇的序列--Catalan数
-指数型母函数
--指数型母函数
--神奇的序列--指数型母函数
-错排
--错排1
--错排2
--神奇的序列--错排
-Stirling数
--神奇的序列--Stirling数
-母函数小结
--母函数小结
-大家谈组合数学(3)
-第五周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第五周演示程序
--讨论区说明
--Catalan数
--程序共享
-且容且斥
--容斥原理
--容斥原理的证明
--容斥原理和鸽巢原理--且容且斥
-容斥原理的精妙
-回忆过去,容斥新解
--容斥原理和鸽巢原理--回忆过去,容斥新解
-鸽子抢巢
--鸽巢原理
--鸽巢原理--练习
--鸽巢原理的应用(1)--练习
-看得见摸得着的鸽巢
--韩信点兵
--中国剩余定理
--容斥原理和鸽巢原理--看得见摸得着的鸽巢
-6人行和Ramsey数
--6人行
--Ramsey数
--小结
-第六周作业
--H
--U
--G
--GT
--作业讨论区说明
-第六周演示程序
--讨论区说明
--程序共享说明
-可以转的世界
--可以转的世界
--可以转的世界--练习
--伽罗华与群
--群的定义
--群的定义--练习
--群的一些概念
-置换群
--置换群
--群--置换群
--共轭类
--对换
--对换--练习
--置换群的应用
-Burnside引理
--着色问题的等价类
--Burnside引理--作业
-闲话群
-第七周作业
--H
--U
--G
--作业讨论区说明
-Burnside引理的困境
-从Burnside到Polya
--Polya定理
-立方体旋转
--立方体旋转(1)
--立方体旋转(2)
--立方体旋转--作业
--立方体旋转(3)
--立方体旋转--作业
--立方体旋转(4)
-母函数型Polya定理
--Polya定理--母函数型Polya定理
-图的计数
--图的计数
-总结
--本章小结
-第八周作业
--H
--U
--G
--GT
--作业讨论区说明
-大家谈组合数学(4)
--采访黄连生老师
-组合之美
--组合之美之计数
-组合之美之线性常系数递推关系
-组合之美之多样的序列
-组合之美之鸽巢原理
-组合之美之转动群与染色
-采访邹欣
--采访邹欣1
--采访邹欣2
-知识点串串烧
--知识点串串烧
-期末测验--期末测验