当前课程知识点:组合数学 >  线性常系数递推关系 >  Fibonacci数列 >  Fibonacci恒等式

返回《组合数学》慕课在线视频课程列表

Fibonacci恒等式在线视频

Fibonacci恒等式

下一节:桌布魔术

返回《组合数学》慕课在线视频列表

Fibonacci恒等式课程教案、知识点、字幕

我们有了这样一串的斐波那契数

我们可以

把每一个数字都平方一下

所以我们可以得到

1的平方是1 1的平方是1 2的平方是4

3的平方是9

依此类推

如果我们把

前若干项的

平方和加到一起呢

我们会发现

1加1加4等于6

1加1加4加9等于15

接着往下

我们依次加下去会发现

比如说1加1加4加9加25

加64 等于104

这样的累加和

和斐波那契有什么关系呢

可能大家现在看不见

但是如果我们把

右端项变成两个数的乘积的话

大家就会发现

6等于2乘以3

接下来我们看

下面的104

等于8乘以13

所以其实每一项右端

都等于两个相邻的

斐波那契数的乘积

这时候我们是不是

就可以推出一个式子呢

也就是说

对应于

f1的平方

加上f2平方

一直累加到

fn的平方

所有的

一串斐波那契数平方之和

它们就等于

相邻的两个斐波那契数乘积

也就是fn乘以fn加1

这个式子对吗

我们看了这四个式子

似乎是对的

那我们给它一个证明

我们先看

对应于1的平方可以怎么表示呢

我们可以用一个

长宽都是1的

小正方形来表示

所以我们可以这样想

比如说1加1加4

可以变成两个

1、1的小方块摆在一起

然后再加一个

2乘以2的稍微大一点的方块

这时候我们构成了一个

3乘以2的

接着呢我们在旁边

再累一个3乘以3的方块

接着我们在下面又可以

累一个5乘以5的

之后旁边又可以出来一个8乘以8的

这时候我们看到了什么

这就是刚才

我们列举的最后一个式子

1加1加2加3加5加8

所有的平方和累加起来

就应该等于大的长方形面积

长方形面积是什么呢

正好它的高是斐波那契数8

而它的长是斐波那契5加8 是13

所以我们可以看到

利用这样拼小的正方形和长方形

我们最终得到长方形的面积

是等于所有的小正方形面积之和

而长方形的面积

正好是两个斐波那契数的乘积

所有的小正方形面积

正好是对应的斐波那契数的平方

这时候

我们没有写任何一个数学的符号

而证明了这样一个斐波那契等式

实际上最近

大家如果关心网上的话

会发现

很多消息有关的是无字证明

确实我们对于斐波那契

也用了一下无字证明的方法

那么大家会想

有没有有字的证明呢

我们能不能

做逻辑的演绎呢

下面我们来仔细分析一下

那么我们就来证明

这样一个恒等式

f1平方加f2平方

一直累加到fn平方

等于两个相邻的

斐波那契数fn乘以fn加1

这时候我们会想

每一个fn

都满足它的递推关系

也就是fn等于fn减1加上n减2

那在这个平方数目里面

我们是不是可以拿一个数出来

将它进行变换呢

比如说我们看一下

给这样一个证明

对应于f1的平方

因为f1和f2都等于1

所以f1平方可以写为

f2乘以f1

对应于f2的平方

我们保留其中一个f2

我们保留其中一个f2

利用递推关系它等于f3减去f1

这时候我们乘起来

就得到了f2乘以f3减去f2乘以f1

那么这时候我们就看到

它似乎有一个序号的变化

接着f3的平方

也可以把f3打开乘f4减f2

变成了f3减去f4

减去f2乘以f3

这我们如果把它

累加的话

就会发现

这里有一个f2 f3

这里也有一个f2、f3

如果累加

就会消掉

所以依次向下

我们会发现

如果到最后一项

fn的平方等于

fn乘以fn加1

减去fn减1打开之后

变成fn乘以fn加1

减去fn减1乘以fn

之后呢

我们把它进行累加

左边累加

就得到的是恒等式的左边

而右边累加

我们会发现

这里面f2、f1,f2、f1消掉

f2、f3,

f2、f3,f3、f4依次消掉

最后的一项

只保留了fn乘以fn减1

因此左右两端进行相加以后

我们会得到的等式

就是左边f1平方

加上f2f平方

加上一直累加到fn平方

就会等于fn乘以fn减1。

所以我们发现

利用这样的递推关系

可以帮助我们

证明出来

有关斐波那契的恒等式

那么我们可以接着往下看

下面呢

我们来看这样一个恒等式

f1加f2

一直累加到fn

等于fn加2减1

可以看到

前n项的斐波那契数列之和

就等于fn加2减1

那么我们有了刚才的经验

就知道了其实可以

把任意一个斐波那契数

变成两个斐波那契数之差

所以有了这样的思想以后

我们来看一下

比如说f1

它可以写成f3减去f2

f2写成f4减去f3

依此类推

fn等于fn加2减去fn加1。

有了这样一个式子以后

我们发现

它们累加就会有一定的关系

比如说这里面

f3和f3就可以消掉

f4也会和它消掉

最终的fn加1

和fn加1也全部都消掉

那么我们剩下的

只有fn加2这一项

以及f2这一项

因此左边累加起来

就正好是f1

一直累加到fn

而右边呢

正好等于fn加2减1

由这个思想

我们接着还可以

去证明其他的式子

比如说f1加f3加f5

一直累加到f2n减1

这实际上是

奇数序列中的

斐波那契数

对应的它们的和

正好等于

一个偶数项的斐波那契数

也就是f2n

怎么证明

跟刚才的思路

是完全一致的

比如说f1就等于f2

而f3等于f4减f2

f5等于f6减f4

依此类推

直到最后一项f2n减1

等于f2n减去f2n减2

这个的累加和我们同样可以计算出来

我们可以发现

这样累加之后

左边就是若干个奇数项之和

而右边呢f2和f2消掉了

f4和f4消掉了

依此类推只类下了最后一项

也就是f2n

左边正好等于

若干项奇数之和

而右边呢正好等于f2n

这时我们就会想

对于斐波那契数来说

有很多的这样的恒等式

它具有很好的性质

那么它具体能不能

单独计算出

一个fn等于多少呢

有没有直接的表达式呢

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

-漫谈组合数学--最精巧的排列——幻方

-苦难的羊皮纸卷

--羊皮纸卷

-苦难的羊皮纸卷--作业

-你的手机密码安全吗

--你的手机密码安全吗

-漫谈组合数学--你的手机密码安全吗

-暴力枚举和抽象转换

--世界杯引出的问题

--世界杯引出的问题--练习

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(1)

--采访武永卫老师

-第一周作业

--作业说明

--H

--U

--G

--作业讨论区说明

-第一周演示程序

--程序讨论区说明

--幻方生成器

--换方计数

--屏幕解锁方案数

--欧拉路计数

--共享程序

小乒乓球的组合之旅

-加减乘除来计数

--计数的基本法则

-排列还是组合

--排列还是组合

--小乒乓球的组合之旅--排列还是组合

--格路模型与组合恒等式

-各种各样的排列

--圆排列和项链排列

--圆排列和项链排列--习题

--多重排列

--多重排列--练习

-多样的组合

--可重组合

--不相邻组合

--小乒乓球的组合之旅--多样的组合

-钟声里的全排列

--钟声里的全排列

--钟声里的全排列

--字典序法

--SJT算法

--程序支持与Stirling公式

-第二周作业

--H

--U

--G

--思考题

--公式测试

--作业讨论区说明

-第二周演示程序

--程序讨论区说明

--排列数和组合数的计算

--全排列生成

--组合生成器

--共享程序

-参考资料:Stirling估计式

--Stirling估计式

初识母函数

-母函数是函数的母亲吗

--母函数的定义(1)

--母函数的定义(1)--练习

--母函数的定义(2)

--母函数的定义(2)--练习

-母函数的简单应用

--母函数的简单应用(1)

--母函数的简单应用(2)

--初识母函数--母函数的简单应用

-整数拆分

--整数拆分(1)

--整数拆分(2)

-Ferrers图像

--Ferrers图像

--Ferrers图像--作业

-母函数与递推关系

--母函数能做什么

--Hanoi问题(1)

--Hanoi问题(2)

--偶数个5怎样算

--偶数个5怎样算(2)

--母函数小结

-大家谈组合数学(2)

--科研,找工作与组合数学

-第三周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第三周演示程序

--程序讨论区说明

--整数拆分

--汉诺塔

--共享程序说明

线性常系数递推关系

-Fibonacci数列

--Fibonacci兔子

--Fibonacci恒等式

--线性常系数递推关系--Fibonacci数列

-Fibonacci数列的应用

--桌布魔术

--桌布魔术--练习

--Fibonacci的直接表达式

--Fibonacci优选法

--艾略特波浪曲线

-线性常系数齐次递推关系

--定义

--特征多项式

--母函数与特征多项式

--根据特征多项式求解递推关系通解(1)

--根据特征多项式求解递推关系通解(2)

--线性常系数递推关系--线性常系数齐次递推关系

-说“数”解题

--说“数”解题(1)

--说“数”解题(2)

-第四周作业

--H

--U

--G

--GT思考题

--作业讨论区说明

-第四周演示程序

--程序讨论区说明

--Fibonacci优选法

--Fibonacci数值计算

--程序共享说明

-爆笑花絮

--爆笑花絮

-参考资料:K线分析中的Fibonacci 相关理论

--Fibonacci retracement资料

神奇的序列

-Catalan数

--计算机界的精灵

--Catalan数的直接表达式

--Catalan数的各种实例

--神奇的序列--Catalan数

-指数型母函数

--指数型母函数

--指数型母函数的应用

--神奇的序列--指数型母函数

-错排

--错排1

--错排2

--神奇的序列--错排

-Stirling数

--第一类Stirling数

--神奇的序列--Stirling数

--第二类Stirling数

-母函数小结

--母函数小结

-大家谈组合数学(3)

--采访郭家宝(BYVoid)

-第五周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第五周演示程序

--讨论区说明

--Catalan数

--第二类Stirling数

--程序共享

容斥原理和鸽巢原理

-且容且斥

--容斥原理

--容斥原理的证明

--容斥原理和鸽巢原理--且容且斥

-容斥原理的精妙

--容斥原理的应用(1)

--容斥原理的应用(2)

--容斥原理的应用(3)

-回忆过去,容斥新解

--容斥原理的应用(4)

--容斥原理的应用(5)

--容斥原理的应用(6)

--容斥原理和鸽巢原理--回忆过去,容斥新解

-鸽子抢巢

--鸽巢原理

--鸽巢原理--练习

--鸽巢原理的应用(1)

--鸽巢原理的应用(1)--练习

-看得见摸得着的鸽巢

--鸽巢原理的应用(2)

--韩信点兵

--中国剩余定理

--容斥原理和鸽巢原理--看得见摸得着的鸽巢

-6人行和Ramsey数

--6人行

--Ramsey数

--小结

-第六周作业

--H

--U

--G

--GT

--作业讨论区说明

-第六周演示程序

--讨论区说明

--Find a multiple

--程序共享说明

-可以转的世界

--可以转的世界

--可以转的世界--练习

--伽罗华与群

--群的定义

--群的定义--练习

--群的一些概念

-置换群

--置换群

--群--置换群

--共轭类

--对换

--对换--练习

--置换群的应用

-Burnside引理

--着色问题的等价类

--Burnside引理--作业

--Burnside引理

--Burnside引理的应用

-闲话群

--无处不在的群(1)

--无处不在的群(2)

-第七周作业

--H

--U

--G

--作业讨论区说明

Polya定理

-Burnside引理的困境

--Burnside引理的困境(1)

--Burnside引理的困境(2)

-从Burnside到Polya

--Polya定理

--Polya定理的应用(1)

--Polya定理的应用(2)

-立方体旋转

--立方体旋转(1)

--立方体旋转(2)

--立方体旋转--作业

--立方体旋转(3)

--立方体旋转--作业

--立方体旋转(4)

-母函数型Polya定理

--母函数型Polya定理(1)

--母函数型Polya定理(2)

--母函数型Polya定理(3)

--母函数型Polya定理(4)

--Polya定理--母函数型Polya定理

-图的计数

--图的计数

-总结

--本章小结

-第八周作业

--H

--U

--G

--GT

--作业讨论区说明

-大家谈组合数学(4)

--采访黄连生老师

组合之美

-组合之美

--组合之美之计数

--组合之美之排列组合

--组合之美之多样组合和全排列

-组合之美之线性常系数递推关系

--组合之美之线性常系数递推关系

-组合之美之多样的序列

--组合之美之多样的序列

-组合之美之鸽巢原理

--组合之美之鸽巢原理

-组合之美之转动群与染色

--组合之美之转动群与染色

-采访邹欣

--采访邹欣1

--采访邹欣2

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

Fibonacci恒等式笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。