Fibonacci's Magic

$\rm Fibonacci$ 数列的性质很多，有的常考，有的不常考。
这些性质都有可能是解题关键。这里稍作总结。
$\rm Fibonacci$ 的定义很多，本文采取如下的递归定义：

$f_i=\begin{cases} 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=0\\ 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=1\\ f_{i-1}+f_{i-2}\ \ \ \ \ \ \ \ \ \ i \geq 2 \end{cases}$

广义 $\rm Fibonacci$ 对于 $f_0$ 和 $f_1$ 的定义不变，剩下的项为：

$f_n=pf_{n-1}+qf_{n-2}\ \ \ \ \ \ \ \ \ \ n\geq 2$

从 $f_n$ 到 $f_k$

$\rm Fibonacci$ 数最好的性质就是定义（出自《$\rm Imakf$ 本纪》）：

$f_i=f_{i-1}+f_{i-2}$

直接暴力展开上面的定义式可以得到 $\rm Fibonacci$ 数的另一个重要性质

$f_n=f_{k}f_{n-k+1}+f_{k-1}f_{n-k}$

这个性质提供了从 $f_n$ 凑 $f_k$ 的一条直接途径。
广义 $\rm Fibonacci$ 数列是类似的。

二次 $f_n,f_{n-1}$ 的关系

$\rm Fibonacci$ 相邻项之间的关系除了定义式外还有一条有趣的性质：

$f^2_{n-1}-f^2_{n}+f_{n-1}f_{n}=f_{n-1}f_{n+1}-f^2_n=(-1)^n$

归纳证明。$n=1$ 时原式成立。假设当 $n<m$ 时原式成立。
对于 $f_m$，我们把上左式的 $f_m$ 展开，可以得到：

$\begin{aligned} f^2_{m-1}-(f_{m-1}+f_{m-2})^2+f_{m-1}(f_{m-1}+f_{m-2})&=f^2_{m-1}-f ^2_{m-2}-f_{m-1}f_{m-2}\\ &=(-1)\times (-1)^{m-1}\\ &=(-1)^{m} \end{aligned}$

我们可以把上面的式子写成另一个形式：

$f^2_{n-1}\equiv c^{n}\pmod{f_{n}}$

其中 $c$ 是一个常数。
对于广义 $\rm Fibonacci$ 数列，上式仍然成立，只是 $c$ 有所变化。
当 $n=1$ 时， $f_{n-1}f_{n+1}-f^2_{n}=-1$。
当 $n=2$ 时，

$\begin{aligned} f_{n-1}f_{n+1}-f^2_{n}&=f_{n-1}(pf_n+qf_{n-1})-f^2_n\\ &=qf^2_{n-1}+pf_nf_{n-1}-f_n(pf_{n-1}+qf_{n-2})\\ &=qf^2_{n-1}-qf_nf_{n-2}\\ &=-q(f_{n-2}f_{n}-f^2_{n-1}) \end{aligned}$

所以对于 广义 $\rm Fibonacci$ 数列而言， $c$ 应该为 $-q$ 。

向负下标的扩展

通过 $f_{n}=f_{n+2}-f_{n+1}$ ，即使下标为负数，我们也可以求出对应的 $\rm Fibonacci$ 数。在本文的 $\rm Fibonacci$ 定义下，正负 $\rm Fibonacci$ 的转化可以写成：

$f_{-n}=(-1)^{n-1}f_{n}$

$\rm gcd$ 相关

首先有个小性质：

$\gcd(f_{n},f_{n+1})=1$
直接归纳就可以证明了...?

关于 $\gcd$ 有一个更加广为流传的式子：

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

证明可以从辗转相除法入手。我们现在是 $f_n$ ，我们怎么凑出 $f_m$ 呢...?
$\rm Bingo$！不要忘记了第一个小标题的性质。以下假设 $n>m$ 。

$f_n=f_mf_{n-m+1}+ f_{m-1}f_{n-m}$

然后有 $\gcd(a,b)=\gcd(a,a\text{ mod } b)$ 。所以 $\gcd(f_n,f_m)=\gcd(f_{n-m},f_m)=f_{\gcd(n,m)}$

下标和值上面的 $\gcd$ 可以实现互换。

$\rm Fibonacci$ 进制数

$\rm Fibonacci$ 进制数，就是把一个数用若干个 $\rm Fibonacci$ 数来表示，要求每个 $\rm Fibonacci$ 数只能用一次。构造的话可以从高到低枚举 $\rm Fibonacci$ 数一个一个删。

$\rm Fibonacci$ 进制下有很好的性质。

• 不会有连续两个 $1$ 。
• 可以通过将一个 $1$ 平推得到该数新的斐波那契表示。平推后会得到两个 $1$ ，下标大的 $1$ 必然不能再平推。所以，在 $\rm Fibonacci$ 进制下，每两个 $1$ 的段是相对独立的。考虑时可以一段一段考虑。

经典的例题有 $\rm BJOI2012 最多的方案$ 。