当前课程知识点:组合数学 > 线性常系数递推关系 > 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算法
-第二周作业
--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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验