浅析斐波那契数列
呵呵侠
·
·
个人记录
注：本文偏向于数学，涉及的编程知识较少
斐波那契（Fibonacci）数列：
1.定义：
由递归方程：
f_{n+2} = f_{n+1} + f_n (n \ge 1)
且
f_1 = f_2 = 1
定义的数列称为Fibonacci数列（以下简称F-数列）
简单地说，就是：F-数列的前两项均为1，从第三项开始，每一项都等于前面两项的和
所以，我们不难写出F-数列前面的一些项：
------------
## 2.来源：
公元1202年，意大利数学家列昂纳多出版了他的著作《算盘全书》，提出了著名的“兔子问题”，从而衍生出了F-数列，这个“兔子问题”是这样的：
_某人有一对初生的兔子，养殖在四堵围墙封闭的庭院之中，成熟的兔子每月可生产小兔子一对，而初生的小兔要一个月才能成熟，如此经一年（12个月）时间，问：庭院中的兔子能繁殖到多少对？（假设兔子不会死亡）_
经过分析，我们知道：
```plain
1月末时，庭院中有1对初生小兔；
2月末时，1月末新生的小兔成熟，庭院中仍只有1对成熟的兔子；
3月末时，2月末的兔子产下1对小兔，故兔子增加1对，共2对兔子；
4月末时，3月末新生的小兔成熟，而2月末的那1对兔子又产下1对小兔，故兔子增加1对，共3对兔子；
5月末时，4月末新生的小兔成熟，而3月末的那2对兔子又产下2对小兔，故兔子增加2对，共5对兔子；
……
12月末时，11月末新生的小兔成熟，而11月末的那55对兔子又产下55对小兔，故兔子增加55对，共144对兔子。
```
因此，经过一年时间，庭院中的兔子能繁殖到144对
我们发现，每次增加的兔子的数量都等于上一次的兔子数量（想一想为什么）
而每过一个月兔子的数量，就等于前两个月兔子数量的和（即开头提到的递归方程1）
------------
## 3.应用：
经过本人总结，F-数列主要有这些应用：
### （1）与黄金分割比的关系：
所谓黄金分割比，就是$\mathtt{a:b=a+b:a \ (a>b)}$，这个比值是一个无理数，约等于$0.618
而当我们用F-数列的前一项去除后一项的时候，你会发现商越来越接近黄金分割比
可以用Python写程序来仔细观察商的变化，我为了节省空间，就不写了
（2）与杨辉三角的关系：
把杨辉三角左对齐，如图：
F \qquad 1 \qquad 1 \qquad 2 \qquad 3 \qquad 5 \qquad 8
1 \qquad / \qquad / \qquad / \qquad / \qquad / \qquad /
1 \qquad 1 \qquad / \qquad / \qquad / \qquad / \qquad /
1 \qquad 2 \qquad 1 \qquad / \qquad / \qquad / \qquad /
1 \qquad 3 \qquad 3 \qquad 1 \qquad / \qquad /\qquad/
1 \qquad 4 \qquad 6 \qquad 4 \qquad 1 \qquad / \qquad /
1 \qquad 5 \qquad 10 \quad \ \ 10 \quad \ \ 5 \qquad 1 \qquad /
把从右上到左下斜线上的数加起来，恰好等于最上行的数：
1 = 1
1 = 1
1 + 1 = 2
1 + 2 = 3
1 + 3 + 1 = 5
1 + 4 + 3 = 8
……
而最上面的数，又恰好是F-数列里的数！
4.F-数列的代数性质（重头戏）
（1）F-数列的部分和
F-数列有下面的求和公式：
f_1 +f_2 + f_3 + … + f_n = f_{n+2} - 1
作为递归数列，F-数列的求和公式有两个证明方法，在此，我贴出较为浅显的一种
证明：
由F-数列的递推式可得：
f_1 = f_3 - f_2
f_2 = f_4 - f_3
f_3 = f_5 - f_4
……
f_{n - 1} = f_{n + 1} - f_n
f_n = f_{n + 2} - f_{n + 1}
各项相加，可得：
f_1 +f_2 + f_3 + … + f_n = f_{n-2} - f_2
即：
f_1 +f_2 + f_3 + … + f_n = f_{n-2} - 1
（2）涉及求和的一些恒等式
由F-数列的部分和公式可以导出下面的一些恒等式：
-
f_1 + f_3 + f_5 + … + f_{2n - 1} = f_{2n}
证明：
f_1 = f_2
f_3 = f_4 - f_2
f_5 = f_6 - f_4
……
f_{2n - 1} = f_{2n} - f_{2n-2}
各项相加，可得
f_1 + f_3 + f_5 + … + f_{2n - 1} = f_{2n}
-
f_2 + f_4 + f_6 + … + f_{2n} = f_{2n + 1} - 1
证明：
由求和公式得：
f_1 + f_2 + … + f_{2n} = f_{2n + 2} - 1
用这个式子减去刚才得到的第一个恒等式，即得：
f_2 + f_4 + f_6 + … + f_{2n} = f_{2n + 1} - 1
-
f_3 + f_6 + … + f_{3n} = \dfrac{1}{2}(f_{3n + 2}-1)
证明：
f_1 + f_2 = f_3
f_4 + f_5 = f_6
……
f_{3n - 2} + f_{3n - 1} = f_{3n}
由求和公式得：
f_3 + f_6 + … +f_{3n} = \dfrac{1}{2}(f_1 + f_2 + … + f_{3n}) = \dfrac{1}{2}(f_{3n + 2} - 1)
（3）Lucas数列
由递归方程：
l(x)=\begin{cases}l_{n + 2} = l_{n + 1} + l_n&n\geqslant1\\l_1 = 1, \ \ l_2 = 3\end{cases}
定义的数列称为Lucas数列（简称L-数列）
L-数列与F-数列有着相同的递归方程（但两者的始值不同），因而有着相同的特征方程和特征根\alpha,\beta，且不难证明L-数列的通项公式为：
l_n = \alpha ^ n + \beta ^ n
至于L-数列的其他性质，我并没有写，读者们可以去自行查找
5.F-数列与数论
整除性
定理1 若m| n，则f_m| f_n
定理2 (f_m, f_n) = f_{(m, n)}
定理3 m| n当且仅当f_m| f_n
读者读到这里，可以自行思考为什么（证明过长，略去）
6.编程的经典题目（推荐做）
月落乌啼算钱
数楼梯
ps:因为和F-数列相关的题大都需要高精，所以建议不会高精的小伙伴们暂时不刷这几道题
参考书目：《数林外传系列·Fibonacci数列》 肖果能编著 中国科学技术大学出版社
在最后，我打个广告（光速逃
My Blog