浅谈斐波那契数列的一个性质及推广
SoyTony
·
·
个人记录
浅谈斐波那契数列的一个性质及推广
前置知识
导引
斐波那契数列有一个大家所熟知的性质：
\gcd(f_{n},f_{m})=f_{\gcd(n,m)}
以下部分的内容将证明这一性质。
先来看一个引理：
\text{Lemma}\ 1
f_{n+m}=f_{n}\times f_{m-1}+f_{n+1}\times f_{m}
使用归纳法证明，m\le 2 时，显然有：
f_{n+1}=f_{n}\times f_{0}+f_{n+1}\times f_{1}
f_{n+2}=f_{n}\times f_{1}+f_{n+1}\times f_{2}
假设 m\le k 时均成立，现证明 m=k+1 时成立。
根据假设，可以得到：
f_{n+k}=f_{n}\times f_{k-1}+f_{n+1}\times f_{k}
f_{n+k-1}=f_{n}\times f_{k-2}+f_{n+1}\times f_{k-1}
两式相加：
f_{n+k+1}
&=f_{n+k}+f_{n+k-1}\\
&=f_{n}\times (f_{k-1}+f_{k-2})+f_{n+1}\times (f_{k}+f_{k-1})\\
&=f_{n}\times f_{k}+f_{n+1}\times f_{k+1}
\end{aligned}
即证 m=k+1 时成立。
同时，换元可以得到：
f_{m}=f_{n}\times f_{m-n-1}+f_{n+1}\times f_{m-n}
接下来是斐波那契数列另一性质：
\text{Lemma}\ 2
\gcd(f_{n},f_{n+1})=1
简单推导一下：
\gcd(f_{n},f_{n+1})
&=\gcd(f_{n},f_{n+1}-f_{n})\\
&=\gcd(f_{n},f_{n-1})\\
&\cdots\\
&=\gcd(f_{1},f_{2})\\
&=1
\end{aligned}
回到最初的证明，类比更相减损推广至辗转相除，如果我们能证明：
\gcd(f_{n},f_{m})=\gcd(f_{n},f_{m-n})
就可以证明该性质。
只需要大力展开：
\gcd(f_{n},f_{m})=\gcd(f_{n},f_{n}\times f_{m-n-1}+f_{n+1}\times f_{m-n})
容易发现前一项可以直接消去，而后一项中 f_{n} 与 f_{n+1} 互质，因此：
\gcd(f_{n},f_{m})=\gcd(f_{n},f_{m-n})
拓展
那么对于任意的 x,y\in \mathbf{N^*}，递推式：
\begin{cases}
[n=1]&n\le 1\\
xf_{n-1}+yf_{n-2}&n>1
\end{cases}
是否同样有：
\gcd(f_{n},f_{m})=f_{\gcd(n,m)}
成立？
尝试证明拓展结论时，我们仍然要从两个引理的拓展下手。
引理 1 的归纳部分可效仿之处很多，事实上，对于任意的系数：
f_{n+m}=a\times f_{n}\times f_{m-1}+b\times f_{n+1}\times f_{m}
归纳 m=k+1 成立的部分都可以写成：
f_{n+k+1}
&=xf_{n+k}+yf_{n+k-1}\\
&=a\times f_{n}\times (xf_{k-1}+yf_{k-2})+b\times f_{n+1}\times (xf_{k}+yf_{k-1})\\
&=a\times f_{n}\times f_{k}+b\times f_{n+1}\times f_{k+1}
\end{aligned}
因此我们只需要找到使得边界成立 a,b，容易列出：
f_{n+1}=a\times f_{n}\times f_{0}+b\times f_{n+1}\times f_{1}\\
f_{n+2}=a\times f_{n}\times f_{1}+b\times f_{n+1}\times f_{2}
\end{cases}
得：
a=y\\
b=1
\end{cases}
于是我们得到本文中 最为强力 的结论：
\text{Theorem}\ 1
$$f_{n}=
\begin{cases}
[n=1]&n\le 1\\
xf_{n-1}+yf_{n-2}&n>1
\end{cases}$$
满足：
$$f_{n+m}=y\times f_{n}\times f_{m-1}+f_{n+1}\times f_{m}$$
---
而引理 $2$ 的拓展同样值得思考，当 $y=1$ 时：
$$\gcd(f_{n},f_{n+1})=\gcd(f_{n},f_{n+1}-xf_{n})=\gcd(f_{n},f_{n-1})$$
是流畅而愉悦的，但对于更普遍的情况则不甚适用。
于是我们调转思考方向，尝试寻找一个关于 $x,y$ 的条件以得到：
$$\gcd(f_{n},f_{n+1})=1$$
将式子拆开：
$$\gcd(f_{n},f_{n+1})=\gcd(f_{n},f_{n+1}-xf_{n})=\gcd(f_{n},yf_{n-1})$$
尝试使用归纳法，假设对于 $n\le k$，有 $\gcd(f_{n},f_{n+1})=1$ 成立，试探究 $n=k+1$ 时成立的条件。
在假设的前提下，就可以将上式再整理：
$$\begin{aligned}
\gcd(f_{k},f_{k+1})
&=\gcd(f_{k},yf_{k-1})\\
&=\gcd(f_{k},y)\\
&=\gcd(f_{k}\bmod y,y)
\end{aligned}$$
显然 $f_k$ 可以表示成 $f_k=ax+by$ 的形式，即要求 $\gcd(ax,y)=1$ 成立。
于是我们得到一个必要条件：$\gcd(x,y)=1$，似乎很有意义。
---
下面来证明其充分性。
再看刚刚归纳得到的式子：
$$\gcd(f_n,f_{n+1})=\gcd(f_n,yf_{n-1})$$
假设中 $\gcd(f_{n},f_{n-1})=1$，此时满足条件 $\gcd(f_{n},y)=1$ 则原式成立，我们不妨对此同样进行归纳。
假设 $n\le k$ 时，$\gcd(f_{n},f_{n+1})=1,\gcd(f_{n},y)=1$，现证明满足 $\gcd(x,y)=1$ 的情况下，$n=k+1$ 时仍然成立。
$$\begin{aligned}
\gcd(f_{k+1},y)
&=\gcd(xf_{k}+yf_{k-1},y)\\
&=\gcd(xf_{k},y)
\end{aligned}$$
而 $\gcd(x,y)=1,\gcd(f_k,y)=1$ 均成立，即证。
综上，我们得到：
$\text{Theorem}\ 2
$$f_{n}=
\begin{cases}
[n=1]&n\le 1\\
xf_{n-1}+yf_{n-2}&n>1
\end{cases}$$
满足：
$$\gcd(x,y)=1\Leftrightarrow\gcd(f_{n},f_{m})=f_{\gcd(n,m)}$$
## 题
### rafrsq
感谢题目提供者：[Jijidawang](https://www.luogu.com.cn/user/227514)
给定一个序列 $b$ 以及正整数 $x,y$ 要求维护一个初始值为 $0$ 序列 $a$，支持以下操作：
`1 l r k`，对于所有 $i\in [l,r]$，令 $a_i\leftarrow a_i+f(b_i+k)
2 l r，查询 \sum_{i=l}^r a_i
其中 f 为数列，满足：
\begin{cases}
[n=1]&n\le 1\\
xf_{n-1}+yf_{n-2}&n>1
\end{cases}
答案对 998244353 取模。
只需将 f(b_i+k) 拆开成 y\times f(b_i)\times f(k-1)+f(b_i+1)\times f(k)，由于 b 固定，只需要维护系数。
后记