数论——斐波那契数列

大家好，欢迎来到IT知识分享网。

定义

推导通项公式

设常数$r$和$s$，使得$F(n)-r\times F(n-1)=s\times [F(n-1)-r\times F(n-2 )]$
所以$r+s=1,-r\times s=1$
在$3\leq n$的时候，有

$$\begin{align} F(n)-rF(n-1)&=s\times [F(n-1)-r\times F(n-2)]\\ F(n-1)-rF(n-2)&=s\times [F(n-2)-r\times F(n-3)]\\ F(n-2)-rF(n-3)&=s\times [F(n-3)-r\times F(n-4)]\\ ……&\ ……\\ F(3)-rF(2)&=s\times [F(2)-r\times F(1)]\\ \end{align}$$

联立解方程组得到：

$$F(n)-r\times F(n-1)=s^{n-2}\times [F(2)-r\times F(1)]$$
因为

$$s=1-r,F(1)=F(2)=1$$
上式可化简得：

$$F(n)=s^{n-1}+r\times F(n-1)$$
那么：

$$\begin{align} F(n)&=s^{n-1}+r\times F(n-1)\\ &=s^{n-1}+r\times s^{n-2}+r^2\times F(n-2)\\ &……\\ &=s^{n-1}+r\times s^{n-2}+r^2\times s^{n-3}+…+r^{n-2}\times r^{n-1}\\ \end{align}$$
所以这是个等比数列的和。
也就是

$$=\frac{s^n-r^n}{s-r}$$
因为 $r+s=1,-rs=1$，所以一组解是

$$s=\frac {1+\sqrt 5}{2}$$

$$r=\frac {1-\sqrt 5}{2}$$
则

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

性质

相邻互质

$gcd(F_n,F_{n-1})=1$
证明：
由于$gcd(F_n,F_{n-1})=gcd(F_{n-1},F_{n-2})=…=F1=1$
（利用欧几里得算法可以证明）

任意两项的gcd

$gcd(F_m,F_n)=F_{gcd(n,m)}$
证明：
当$m=n$显然成立。

练习题