斐波那契数列的重要性质

对于斐波那契数列 $f$，有如下定义：

$f_n= \begin{cases} 0 & n=0 \\ 1 & n=1 \\ f_{n-1}+f_{n-2} &n>1 \end{cases}$

其有如下重要性质。

性质一 对于 $\forall n\ge 1$，有

$\boxed{f_{n-1}f_{n+1}-f_n^2=(-1)^n}$

证明根据定义，有

$\begin{aligned} f_{n-1}f_{n+1}-f_n^2&=f_{n-1}(f_{n-1}f_n)-f_n^2 \\ &= f_{n-1}^2-f_n(f_{n-1}-f_n) \\ &=f_{n-1}^2-f_nf_{n-2} \\ &=f_{n-1}f_{n-3}-f_{n-2}^2 \\ &=\cdots \\ &=(-1)^{n-1}(f_0f_2-f_1^2) \\ &=(-1)^n \end{aligned}$

证毕。

性质二 对于 $\forall n\ge 0,k\ge 1$，有

$\boxed{f_{n+k}=f_{k-1}f_n+f_kf_{n+1}}$

证明设 $f_n=a,f_{n+1}=b$，则有

$\begin{aligned} f_{n+1}&=a+b \\ f_{n+2}&=a+2b \\ f_{n+3}&=2a+3b \\ \cdots \\ f_{n+k}&=f_{k-1}a+f_kb \\ &= f_{k-1}f_n+f_kf_{n+1} \end{aligned}$

上述规律可以表述为 $a,b$ 的系数均为相邻两项斐波那契数列且与 $k$ 相关。

证毕。

上述结论也可表示为 $f_m=f_{m-n-1}f_n+f_{m-n}f_{n+1}$，其中 $m>n\ge 0$。

性质二推论一 若取 $k=n$，则有

$f_{2n}=f_n(f_{n-1}+f_{n+1})$

性质二推论二 由推论一可以归纳证明

$\forall k\in \mathbb N\,,\,f_n\mid f_{nk}$

性质二推论三 推论二可逆，即

$f_a\mid f_b\Leftrightarrow a\mid b$

性质三 对于 $\forall n\ge 0$，有

$\boxed{(f_n,f_{n+1})=1}$

其中，$(x,y)$ 表示 $x$ 与 $y$ 的最大公约数。

证明施更相减损术，有

$\begin{aligned} (f_n,f_n+1)&=(f_n,f_{n+1}-f_n) \\ &=(f_n,f_{n-1}) \\ &=\cdots \\ &=(f_1,f_2) \\ &=1 \end{aligned}$

证毕。

性质四 对于 $\forall n,m\ge 0$，有

$\boxed{(f_n,f_m)=f_{(n,m)}}$

其中，$(x,y)$ 表示 $x$ 与 $y$ 的最大公约数。

证明根据性质二，有

$\begin{aligned} (f_n,f_m)=(f_n,f_{m-n-1}f_n+f_{m-n}f_{n+1}) \end{aligned}$

因为 $f_n\mid f_{m-n-1}f_n$，$(f_n,f_{n+1})=1$，所以

$(f_n,f_m)=(f_n,f_{m-n})$

发现上述等式等价于对下标进行更相减损术，故有

$(f_n,f_m)=(f_0,f_{(n,m)})=f_{(n,m)}$

证毕。

应用此性质，可以完成例题：洛谷 P1306 斐波那契公约数。

这个性质对于广义斐波那契数列也同样成立。