RainAir
My OI Blog
RainAir
斐波那契数列学习笔记

定义

$$
F_n = \begin{cases}
0 & n = 0 \\
1 & n = 1 \\
F_{n-1}+F_{n-2} & otherwise
\end{cases}
$$

一些小性质

一些 simple 的运算

运算 1

$$F_n = F_{n+2} – F_{n+1}$$
证明:拆开算就可以了
$$F_{n+2}-F_{n+1} = F_{n+1}+F_n – F_{n+1} = F_n$$

运算2

$$F_{n+1}F_{n-1}-F_n^2 = (-1)^n$$
证明:数学归纳法一下就可以了。
咕咕咕~

运算3

我们如果把斐波那契数列扩展到负数,那么有公式
$$F_{-n} = (-1)^{n-1}F_n$$

运算4

$$F_{n+k} = F_{n+1}F_k + F_nF_{k-1}$$
证明:
首先验证小范围的 k 发现是正确的。
那么我们设 $\forall k \in [1,i-1]$ 是正确的,现在尝试证明 $k=i$ 是正确的。
\begin{align}
F_{n+k} &= F_{n+k-1}+F_{n+k-2} \\
&=F_{n+1}F_{k-1}+F_{n}F_{k-2}+F_{n+1}F_{k-2}+F_{n}F_{k-3} \\
&=F_{n+1}F_{k}+F_{n}F_{k-1}
\end{align}

一些正常的小性质

性质 1

$$gcd(F_i,F_{i-1}) = 1(i>1)$$
证明:考虑辗转相减法:
$$gcd(F_i,F_{i-1}) = gcd(F_{i-1},F_i-F_{i-1}) = \cdots = gcd(1,0) = 1$$

性质 2

$$n | m \Leftrightarrow F_n | F_m$$
我们首先证明从左到右:
我们将 $m$ 表示为 $kn$,现在需要证明 $F_n | F_{kn}$
考虑 $k=2$ 的情形:
$$F_{2n} = F_{n+n} = F_{n+1}F_n + F_{n}F_{n-1} \Rightarrow F_{n} | F_{2n}$$
同理:当 $k=3$ 的时候,借助上面的结论,显然也有
$$F_{3n} = F_{n+2n} = F_{n+1}F_{2n}+F_{n}F_{2n-1} \Rightarrow F_{n} | F_{3n}$$
归纳证明命题正确。
现在我们证明从右到左,首先我们来观察一个引理:
引理 1:$$gcd(F_m,F_n) = F_{gcd(m,n)}$$
证明:我们不妨设 $m>n$,则 $m = n+(m-n)$。
所以有 $$F_m = F_{n+(m-n)} = F_{n+1}F_{m-n}+F_{n}F_{m-n-1}$$

$$gcd(F_m,F_n) = gcd(F_{n+1}F_{m-n}+F_{n}F_{m-n-1},F_n)$$
显然经过数次辗转相减后会变成:
$$gcd(F_{n+1}F_{m-n},F_n) $$
注意到 $gcd(F_{n+1},F_n) = 1$,所以可以得
$$gcd(F_{n},F_{m-n})$$
观察下标由 $(m,n) \to (n,m-n)$,实质是在对下标辗转相减,也就是求下标的 gcd。
现在我们来考虑证明命题
$$F_n | F_m \Rightarrow n|m$$
因为整除所以可以得到
$$F_n | gcd(F_n,F_m) \Rightarrow F_n | F_{gcd(n,m)}$$
注意到满足条件的 $gcd(n,m)$ 的最小值是 $n$,所以我们就证明了上述命题。

性质三(马蒂亚舍维奇引理)

$$F_n^2 | F_m \Leftrightarrow nF_n | m$$
证明:
我们考虑 $\forall k \in N^* $,观察什么时候有 $F_{kn} \mod F_n^2 = 0$。
首先可以知道的是 $F_n \mod F_{n}^2 = F_n$,这并不是零。
注意到有 $F_{n+1} \equiv F_{n-1} (\mod F_i)$,所以
$$F_{2n} = F_nF_{n+1}+F_nF_{n-1}\equiv 2F_nF_{n+1}(\mod F_n^2)$$
类似地,我们对于 $2n+1$ 还有
$$F_{2n+1} = F_{n+1}^2 + F_{n}^2 \equiv F_{n+1}^2 (\mod F_n^2)$$
通过对于 $2n$ 和 $2n+1$ 的计算使我们可以计算 $3n$ 和 $3n+1$:
\begin{align}
F_{3n} &= F_{2n+1}F_n + F_{2n}F_{n-1}\\
&\equiv F_{n+1}^2F_n+(2F_nF_{n+1})F_{n-1} = 3F^2_{n+1}F_n (\mod F_n^2) \\
F_{3n+1} &= F_{2n+1}F_{n+1}+F_{2n}F_n \\
&\equiv F_{n+1}^3(\mod F_n^2)
\end{align}
仿照上面的过程,对 $k$ 用数学归纳法,可以得到规律:
$$F_{kn} \equiv kF_nF_{n+1}^{k-1} \text{和} F_{kn+1} \equiv F_{n+1}^k (\mod F_n^2)$$
因为 $gcd(F_n,F_{n+1}) = 1$,所以
\begin{align}
F_{kn} \equiv 0 (\mod F_n^2) &\Leftrightarrow kF_n \equiv 0(\mod F_n^2)\\
&\Leftrightarrow k \equiv 0(\mod F_n^2)
\end{align}
说明存在这样的 $k$,证毕。

斐波那契数系

我们考虑用斐波那契数来表示任意的数,记
$$j >> k \Leftrightarrow j\geq k+2$$
那么每个正整数有唯一的表示形式
$$n = \sum_{0 \leq i \leq r} F_{k_i},\text{满足} k_1 >> k_2 >> \cdots >> k_r >> 0$$
显然我们可以用贪心构造这样的一组解,并且这组解是唯一的。证明留给读者自己思考。
这样斐波那契数系的定义就出来了:
$$n = (b_m, b_{m-1} \cdots b_2 )_ F \Leftrightarrow \sum_{k=2}^m b_k F_k$$

求斐波那契数列的通项式

当然是直接生成函数啦(逃
我们考虑无穷级数
$$ F(z) = \sum_{n\geq0} f_nz^n$$
观察如下级数的系数特点:
\begin{align}
F(z) = 1 + 1z + 2z^2 + 3z^3 + 5z^4 + 8z^5 \cdots \\
zF(z) = z +1z^2 + 2z^3 + 3z^4 + 5z^5 \cdots \\
z^2F(z) = 1z^2+1z^3+2z^4+3z^5 \cdots
\end{align}
于是我们可以发现
$$F(z) – zF(z) – z^2F(z) = 1$$。
用一些小学数学可以解出来一个关于 $F(z)$ 的更紧凑的公式
$$F(z) = \frac{1}{1-z-z^2}$$
显然大家都知道生成函数为 $\frac{1}{1-x}$ 表示的序列是 $\sum_{i \geq 0} x^i$,考虑尽量表示成类似于这样的形式,这样就能求出一个关于系数的通项公式了。
我们可以将分母的式子 $1-z-z^2$ 因式分解,变成 $(1-\phi z)(1- \hat{\phi} z)$。
运用初中知识容易解得:
\begin{cases}
\phi = \frac{1+\sqrt{5}}{2}\\
\hat{\phi} = \frac{1-\sqrt{5}}{2}
\end{cases}
(给小学神仙选手的提示:把式子拆开系数对应联立方程组即可。)
哎是不是十分像 $\frac{1}{1-kx}$ 的形式了?我们考虑把这玩意拆开(裂项)
$$\frac{a}{(1-\phi z)} + \frac{b}{(1-\hat{\phi} z)}$$,为了确定 $a,b$ 的值,我们需要解方程
$$a(1-\hat{\phi}z) + b(1-\phi z) = 1$$
考虑首先将其看成关于 $z$ 的方程,小学变形可得:
$$(a+b-1)-z(a\hat{\phi} + b \phi ) = 0$$
这样就列个方程组?
\begin{cases}
a+b-1 = 0 \\
a\hat{\phi} + b\phi = 0
\end{cases}
我们写个高斯消元跑一下用计算器算了一下,发现解为
\begin{cases}
a = \frac{1}{\sqrt{5}} \phi \\
b = -\frac{1}{\sqrt{5}} \hat{\phi}
\end{cases}
代入 $F$ 可以得到
$$F = \frac{\phi}{\sqrt{5}}\frac{1}{(1-\phi z)} – \frac{\hat{\phi}}{\sqrt{5}}\frac{1}{(1-\hat{\phi}z)}$$
那么运用小学知识略作整理就可以达到通项公式啦:
$$F_n = \frac{1}{\sqrt{5}} ((\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n})$$

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/547
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

斐波那契数列学习笔记
定义 $$ F_n = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F_{n-1}+F_{n-2} & otherwise \end{cases} $$ 一些小性质 一些 simple 的运算 运算 1 $$F_n = F_{n+2}…
扫描二维码继续阅读
2019-03-14
标签
近期评论