斐波那契数

定义

$$\begin{matrix} F(n)= \left\{ \begin{matrix} f_1 &n=1\\ f_2 &n=2\\ a*F(n-1)+b*F(n-2) &otherwise \end{matrix} \right. &n\in N^* \\ a,b\in \left\{ \begin{matrix} a^2+ab>0\\ |a-\sqrt{a^2+4b}|\leq2 \end{matrix} \right. \end{matrix}$$

性质

1.通项公式：

$$F(n)=\frac{k^n(f_2-mf_1)-m^n(f_2-kf_1)}{k-m}\\ 其中: m,k=\frac{a\pm \sqrt{a^2+4b}}{2}$$

2.通用性质

1.卡西尼恒等式

$$F_{n+1}∗F_{n−1}−F_n^2=(−1)^n，n>0$$

3.斐波那契数列

定义

$$\begin{matrix} F(n)= \left\{ \begin{matrix} 0 &n=0\\ 1 &n=1\\ F(n-1)+F(n-2) &otherwise \end{matrix} \right. &n\in N^* \\ \end{matrix}$$

通项公式

$$F(n)=\frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}}$$

当然你可能发现，这个公式分子的第二项总是小于 ，并且它以指数级的速度减小。因此我们可以把这个公式写成

$$F(n)= \begin{bmatrix} \frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}} \end{bmatrix}$$

[] 表示取最近整数

性质

1.黄金分割比

$$\frac{F_n}{F_{n+1}}=\frac{\sqrt{5}-1}{2}+\frac{\sqrt{5}}{(-\frac{3+\sqrt{5}}{2})^{n+1}-1}$$ $$\displaystyle\lim_{x\to+\infty}\frac{F_n}{F_{n+1}}=\frac{\sqrt{5}-1}{2}$$

2.奇数项求和

$$F_1+F_3+F_5+F_7+\cdots+F_{2n-1}=F_{2n}$$

3.偶数项求和

$$F_2+F_4+F_6+F_8+\cdots+F_{2n}=F_{2n+1}-1$$

4.平方求和

$$F_1^2+F_2^2+F_3^2+\cdots+F_n^2=F_n*F_{n+1}$$

正方形的边长由小到大，分别对于斐波那契数列

面积之和则对于平方和

计算方法

递推 $O(N)$

递归 $O(2^N)$

此做法过于垃圾，不进行说明。。。

矩阵快速幂 $O(log\ N)$

快速算法 $O(log\ N)$

证明

公式

$$F_{2k+1}=4F_k^2-F_{k-1}^2+(-1)^k\\ F_{2k-1}=F_k^2+F_{k-1}^2\\ F_{2k}=F_{2k+1}-F_{2k-1}\\$$

3.卢卡斯数列

参考资料

斐波那契数列

神奇的斐波那契数

斐波那契数 整理