斐波那契数列的性质
Shellchen
·
·
算法·理论
数学课提到的斐波那契数列有一堆性质，于是我整合了一波。
注：本文之后若无特别说明，均有：
F_i = \begin{cases}
1 & i \le 2\\
F_{i-1}+F_{i-2} & i>2
\end{cases}
首先，一个非常显然的性质。
\begin{aligned}
F_n&=F_{n-1}+F_{n-2}\\
&=2F_{n-2}+F_{n-3}\\
&=F_{n-2}+2F_{n-3}+F_{n-4}\\
&=F_{n-2}+F_{n-3}+2F_{n-4}+F_{n-5}\\
&=\cdots\\
&=F_{n-2}+F_{n-3}+F_{n-4}+\cdots+F_3+2F_2+F_1\\
&=\sum^{n-2}_{i=1} F_i+F_2
\end{aligned}
于是，我们得到了不用特别构造矩阵就能 O(\log n) 求出 \displaystyle\sum^n_{i=1} F_i 的方法，只需求出 F_{n+2}-F_2 即可！
接下来，还有：
\begin{aligned}
F_n&=F_{n-1}+F_{n-2}\\
&=F_{n-1}+F_{n-3}+F_{n-4}\\
&=F_{n-1}+F_{n-3}+F_{n-5}+F_{n-6}\\
&=\cdots\\
&=F_{n-1}+F_{n-3}+F_{n-5}+\cdots+F_{n \bmod 2+4}+F_{n \bmod 2+2}+F_{n \bmod 2+1}
\end{aligned}
于是，你学会了求斐波那契数列的奇数项之和与偶数项之和。
我们还注意到：
\begin{aligned}
F_n&=F_{n-2}+F_{n-3}+F_{n-4}+\cdots+F_2+F_1+F_2\\
&=2F_{n-2}+2F_{n-5}+2F_{n-8}+\cdots+2F_{n \bmod 3+4}+2F_{n \bmod 3+1}+\sum^{n \bmod 3}_{i=1} F_i+F_2
\end{aligned}
于是，模 3 同余项之和的我们也会求解了。
此外还有一种奇偶项求和的方法。（下面默认 n 是奇数）
\begin{aligned}
F_{n}+F_{n-2}+F_{n-4}+\cdots+F_3+F_1&=F_{n+1}-F_{n-1}+F_{n-1}-F_{n-3}+\cdots+F_4-F_2+F_2-F_1\\
&=F_{n+1}-F_1
\end{aligned}
接下来，一个较为重要的性质。
设 F_n=a，F_{n+1}=b。则：
F_{n+2}=a+b\\
F_{n+3}=a+2b\\
F_{n+4}=2a+3b\\
F_{n+5}=3a+5b\\
\cdots\\
F_m=F_{m-n-1}\cdot a+F_{m-n}\cdot b\\
F_m=F_{m-n-1}\cdot F_n+F_{m-n}\cdot F_{n+1}
并且注意到，只要知道 m 的值，n 可以任意取。
通过这个还可以证明一个性质：(F_n,F_m)=F_{(n,m)}。（(a,b) 表示 a 与 b 的最大公约数）
证明：不妨 n \le m，由上，
\begin{aligned}
(F_n,F_m)&=(F_n,F_{m-n-1}\cdot F_n+F_{m-n}\cdot F_{n+1})\\
&=(F_n,F_{m-n}+F_{n+1})
\end{aligned}
引理：(F_{n},F_{n+1})=1。
证：
\begin{aligned}
(F_n,F_{n+1})&=(F_n,F_n+F_{n-1})\\
&=(F_n,F_{n-1})\\
&=(F_{n-1},F_{n-2})\\
&=\cdots\\
&=(F_2,F_1)\\
&=1
\end{aligned}
于是，有
(F_n,F_m)=(F_n,F_{m-n})
容易发现这是在辗转相减。于是命题得证。
恭喜你，AC 了 P1306。
那么由此有推论：F_n \mid F_{kn}，其中 k,n 为任意正整数。证明：(F_n,F_{kn})=F_{(n,kn)}=F_n。
没了。还有的话欢迎私信投稿。