数论-斐波那契数列

定义

斐波那契数,

又称黄金分割数列。
递推公式是:$F(n)=F(n-1)+F(n-2)$.

推导通项公式

设常数$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$显然成立。

练习题

斐波那契中的gcd
斐波那契变式1
斐波那契数列的最小公倍数问题
题解

文章目录
  1. 1. 定义
  2. 2. 推导通项公式
  3. 3. 性质
    1. 3.1. 相邻互质
    2. 3.2. 任意两项的gcd
  4. 4. 练习题