<h2>定义</h2>
$$ F_n = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F_{n-1}+F_{n-2} & otherwise \end{cases} $$
<h2>一些小性质</h2>
<h3>一些 simple 的运算</h3>
<h4>运算 1</h4>
$$F_n = F_{n+2} - F_{n+1}$$
证明：拆开算就可以了
$$F_{n+2}-F_{n+1} = F_{n+1}+F_n - F_{n+1} = F_n$$
<h4>运算2</h4>
$$F_{n+1}F_{n-1}-F_n^2 = (-1)^n$$
证明：数学归纳法一下就可以了。
咕咕咕~
<h4>运算3</h4>
我们如果把斐波那契数列扩展到负数，那么有公式
$$F_{-n} = (-1)^{n-1}F_n$$
<h4>运算4</h4>
$$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}
<h3>一些正常的小性质</h3>
<h4>性质 1</h4>
$$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$$
<h4>性质 2</h4>
$$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$,所以我们就证明了上述命题。
<h4>性质三（马蒂亚舍维奇引理）</h4>
$$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$，证毕。
<h2>斐波那契数系</h2>
我们考虑用斐波那契数来表示任意的数，记
$$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$$
<h2>求斐波那契数列的通项式</h2>
当然是直接生成函数啦（逃
我们考虑无穷级数
$$ 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 \\
ahat{phi} + bphi = 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})$$
