斐波那契数列的重要性质

对于斐波那契数列 \(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 斐波那契公约数。

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