令 $a=\dfrac{1+\sqrt5}{2},b=\dfrac{1-\sqrt5}{2}$。

我们有结论：对于 $n\ge 2$，$F_{n+1}=F_{n-1}+F_{n}$。

证明：

注意到：

$$\begin{aligned}F_n=F_n(a+b)&=\dfrac{a^{n+1}-b^{n+1}+a^nb-ab^n}{\sqrt 5}\\&=F_{n+1}+abF_{n-1}\\&=F_{n+1}-F_{n-1}\end{aligned} $$

因此 $F_{n+1}=F_{n-1}+F_n$。

$\mathcal{Q.E.D.}$

前 $\mathcal{O}(1)$ 项的值容易求出，然后使用 http://192.168.121.12/p/P387/solution/67caa97a11ce04ce230e63f5 中提到的做法即可 $\mathcal{O}(\log n)$。