斐波那契数列 学习笔记

模板及讲解

通项公式

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

技巧

1、斐波那契数列增长快
2、与斐波那契数列相关的大数据递推,可以用矩阵优化

恒等式

1、$f(1)+f(2)+f(3)+ \dots +f(n)=f(n+2)-1$
2、$f(1)^2+f(2)^2+f(3)^2+ \dots +f(n)^2=f(n)f(n+1)$
3、$f(1)+f(3)+f(5)+ \dots +f(2n-1)=f(2n)$
4、$f(2)+f(4)+f(6)+ \dots +f(2n)=f(2n+1)-1$
5、$f(m)f(n-m+1)+f(m-1)f(n-m)=f(n), n \leq m$
6、$f(n-1)f(n+1)=f(n)^2+(-1)^n$

性质

1、$\gcd(f(n), f(m))=f(\gcd(n, m))$
2、$n | m \Leftrightarrow f(n) | f(m)$

------ 本文结束 ------