企业官网建设流程全解析

做竞赛题和写数值代码的人，多少都遇到过这样的时刻：明明只想算个数列，结果题面里同时冒出 Fibonacci 数列和 Lucas 数列，还要求你证明一串看起来毫不相干的性质与推论。我早年在整理一份手写笔记时也卡在这个地方——单独看 Fibonacci 数列的性质，每条都能背下来，可一旦把 Lucas 数列摆在旁边，很多结论就有了更短、更统一的证明路径。这篇内容想做的事情很具体：把这两个数列的定义、互推关系、Binet 公式、恒等式、整除结构、模周期和组合解释串成一条完整的线，把每条性质的证明过程写透，把"为什么这么证"讲清楚。它既适合正在准备数学竞赛、需要把证明写严谨的读者，也适合写高性能计算代码、需要把公式落成实现的工程读者。文中所有推导我都配了可直接运行的校验代码，你抄下去跑一遍，就能验证每一步没有虚构。

1. 两条数列为什么必须成对出现：定义、初值与互推关系

1.1 递推定义与前若干项的对照表

先把地基打平。Fibonacci 数列的递推是 $F_0=0,\ F_1=1,\ F_n=F_{n-1}+F_{n-2}$；Lucas 数列的递推结构完全相同，只是初值换成 $L_0=2,\ L_1=1$。初学者最容易犯的错，是把"递推关系相同"误当成"这两个数列是同一回事的两种写法"。实际上，递推关系只是一个二阶线性变换，"初值"才决定了你最终落在哪条轨道上。

二阶线性递推的状态空间是二维的，任何一个满足 $x_n=x_{n-1}+x_{n-2}$ 的数列，都可以唯一地写成 $x_n=aF_n+bL_n$ 的形式。换个说法：Fibonacci 数列和 Lucas 数列构成了这个递推关系的一组基。这就是它们必须成对出现的第一层原因——不是数学家喜欢凑对，而是二维空间需要两个基向量。

最后一行很关键：$L_n-2F_n=F_{n-2}$（$n\ge 2$）。这不是巧合，而是基变换的显式写法。你可以马上写出 $F_n=\frac{L_n-L_{n-1}}{2}$ 或者 $L_n=F_{n-1}+F_{n+1}$，这些换算在证明里能省掉大量代数运算。

1.2 $L_n=F_{n-1}+F_{n+1}$ 的两种证明路径

这条恒等式是我用得最多的一条，必须证到位。归纳法的写法是这样的：$n=1$ 时 $F_0+F_2=0+1=1=L_1$，$n=2$ 时 $F_1+F_3=1+2=3=L_2$。设 $n-1,n$ 时成立，则

$$F_n+F_{n+2}=(F_{n-1}+F_{n-2})+(F_{n+1}+F_n)=(F_{n-1}+F_{n+1})+(F_{n-2}+F_n)=L_n+L_{n-1}=L_{n+1}$$

归纳成立。这条路稳妥但不够"透明"，看不出为什么会这样。

代数法更直观。设 $\alpha=\frac{1+\sqrt5}{2},\ \beta=\frac{1-\sqrt5}{2}$，则 $F_n=\frac{\alpha^n-\beta^n}{\sqrt5}$。于是

$$F_{n-1}+F_{n+1}=\frac{\alpha^{n-1}(1+\alpha^2)-\beta^{n-1}(1+\beta^2)}{\sqrt5}$$

注意到 $\alpha^2=\alpha+1$，所以 $1+\alpha^2=\alpha+2$；同理 $1+\beta^2=\beta+2$。又因为 $\alpha^2=\alpha+1$ 两边乘 $\alpha$ 得 $\alpha^3=\alpha^2+\alpha=2\alpha+1$，即 $\alpha(\alpha+2)=2\alpha^2+\alpha$……这里绕了一圈，换个更干净的做法：直接验证 $\alpha(1+\alpha^2)=\alpha(\alpha+2)=2\alpha+1$；同理 $\beta(\beta+2)=2\beta+1$。于是

$$F_{n-1}+F_{n+1}=\frac{(2\alpha+1)\alpha^{n-1}-(2\beta+1)\beta^{n-1}}{\sqrt5}=\frac{\alpha^n+\alpha^{n-1}-\beta^n-\beta^{n-1}}{\sqrt5}$$

而 $\alpha^n+\alpha^{n-1}=\alpha^{n-1}(\alpha+1)=\alpha^{n+1}$（因为 $\alpha+1=\alpha^2$），所以上式变成 $\frac{\alpha^{n+1}-\beta^{n+1}}{\sqrt5}=F_{n+1}$。诶，这算出的是 $F_{n+1}$ 而不是 $L_{n+1}$，说明我中间跳了步骤。正确的收尾应该是：$F_{n-1}+F_{n+1}=\frac{\alpha^n+\alpha^{n-1}-\beta^n-\beta^{n-1}}{\sqrt5}$，而 $\alpha^n+\alpha^{n-1}=\alpha^n(1+\alpha^{-1})$，用 $\alpha\beta=-1$ 得 $\alpha^{-1}=-\beta$，所以 $1+\alpha^{-1}=1-\beta=\alpha$（因为 $\alpha+\beta=1$），于是 $\alpha^n+\alpha^{n-1}=\alpha^{n+1}$……这样又回到同一个地方。

提示：这条路我实测容易绕，真正干净的做法是先证明 $L_n=\alpha^n+\beta^n$ 作为定义，再用 $\alpha^n+\beta^n=(\alpha^{n-1}+\beta^{n-1})+(\alpha^{n-2}+\beta^{n-2})$ 验证它满足 Lucas 递推和初值，从而 $L_n=F_{n-1}+F_{n+1}$ 由 $\frac{\alpha^n-\beta^n}{\sqrt5}$ 的移位相减直接得出。绕路说明一件事：不要把"Lucas 数的闭式"当成需要从 $F$ 推出来的结论，它本身就是定义的一部分。

1.3 负下标延拓与一般 Lucas 序列的统一视角

把递推式改写成 $x_{n-2}=x_n-x_{n-1}$，就能把两条数列延拓到全整数下标。$F_0=0,F_1=1$ 给出 $F_{-1}=1,F_{-2}=-1,F_{-3}=2,F_{-4}=-3$，规律是

$$F_{-n}=(-1)^{n+1}F_n$$

同理 $L_{-n}=(-1)^nL_n$。这两条式子在处理下标差为负的恒等式时特别有用，比如 d'Ocagne 恒等式里 $m<n$ 的情形，直接套用就能避免分类讨论。

更值得推广的是Lucas 序列$U_n(P,Q)$ 与 $V_n(P,Q)$：设 $\alpha+\beta=P,\ \alpha\beta=Q$，定义

$$U_n=\frac{\alpha^n-\beta^n}{\alpha-\beta},\qquad V_n=\alpha^n+\beta^n$$

取 $P=1,Q=-1$ 时 $U_n=F_n,\ V_n=L_n$；取 $P=2,Q=-1$ 得到 Pell 序列；取 $P=1,Q=-2$ 得到 Jacobsthal 序列，其闭式里出现 $2^n$。这个统一视角的价值在于：你在 Fibonacci 上证的每一条恒等式，几乎都能原封不动搬到 $U_n,V_n$ 上，只是 $\Delta=P^2-4Q$ 和 $Q^n$ 需要替换。

我把这张表贴在显示器边上用了很久，它比任何单条恒等式都好记，因为右边只是左边的一个特例。要注意 $Q=-1$ 带来的符号翻转，这是最容易写错的地方。

2. Binet 公式的完整推导与它作为证明工具的使用边界

2.1 特征方程法：从递推到闭式的标准流程

常系数线性递推的通项求解有一套固定流程，值得完整走一遍。设 $x_n=rx^{n}$ 形式的解，代入 $x_n=x_{n-1}+x_{n-2}$ 得 $r^n=r^{n-1}+r^{n-2}$，约掉 $r^{n-2}$ 得特征方程

$$r^2=r+1\quad\Longrightarrow\quad r=\frac{1\pm\sqrt5}{2}$$

两根互异，因此通解是 $x_n=A\alpha^n+B\beta^n$。用初值定系数：$F_0=0$ 给出 $A+B=0$；$F_1=1$ 给出 $A\alpha+B\beta=1$。联立得 $A=\frac{1}{\alpha-\beta}=\frac{1}{\sqrt5}$，$B=-\frac{1}{\sqrt5}$，于是

$$F_n=\frac{\alpha^n-\beta^n}{\sqrt5},\qquad L_n=\alpha^n+\beta^n$$

有两个数值事实必须记住：$\alpha\approx1.618034$，$|\beta|\approx0.618034<1$。后者意味着 $\beta^n\to0$，所以 $F_n$ 就是 $\frac{\alpha^n}{\sqrt5}$ 四舍五入到最近整数。这个"四舍五入"性质在算大数下标、判断某数是否 Fibonacci 数时非常实用——只要检查 $5x^2\pm4$ 是否完全平方即可，这是判别法的完整依据。

2.2 $\alpha$、$\beta$ 的代数关系表

Binet 公式的证明力，全部来自 $\alpha,\beta$ 之间那几条几乎不证自明的关系。我整理成表，做恒等式证明时逐条对照使用：

最后一条值得单独立出来，它把"$\alpha$ 的幂"翻译成"Fibonacci 数的线性组合"，很多竞赛题的突破口就在这里。证明只需归纳：$k=1$ 时 $\alpha=\alpha\cdot1+0$ 成立；设 $k$ 成立，则 $\alpha^{k+1}=\alpha(\alpha F_k+F_{k-1})=\alpha^2F_k+\alpha F_{k-1}=\alpha(F_k+F_{k-1})+F_k=\alpha F_{k+1}+F_k$。同理有 $\beta^k=\beta F_k+F_{k-1}$。

2.3 用 Binet 公式一次性推平三条经典恒等式

Cassini 恒等式：$F_{n+1}F_{n-1}-F_n^2=(-1)^n$。代入 Binet 公式，分子是

$$(\alpha^{n+1}-\beta^{n+1})(\alpha^{n-1}-\beta^{n-1})-(\alpha^n-\beta^n)^2$$

展开：第一项为 $\alpha^{2n}-\alpha^{n+1}\beta^{n-1}-\alpha^{n-1}\beta^{n+1}+\beta^{2n}$，第二项为 $\alpha^{2n}-2\alpha^n\beta^n+\beta^{2n}$。相减得

$$-\alpha^{n+1}\beta^{n-1}-\alpha^{n-1}\beta^{n+1}+2\alpha^n\beta^n=-\alpha^{n-1}\beta^{n-1}(\alpha^2-2\alpha\beta+\beta^2)=-(\alpha\beta)^{n-1}(\alpha-\beta)^2$$

由 $\alpha\beta=-1$、$(\alpha-\beta)^2=5$，分子为 $-(-1)^{n-1}\cdot5=5(-1)^n$。除以 $(\sqrt5)^2=5$，得 $(-1)^n$。证毕。

Lucas 数的范数恒等式：$L_n^2-5F_n^2=4(-1)^n$。这个更简单，因为 $L_n^2-5F_n^2=(\alpha^n+\beta^n)^2-(\alpha^n-\beta^n)^2=4(\alpha\beta)^n=4(-1)^n$。一行出结果。

乘法公式：$F_nL_n=F_{2n}$。左边等于 $\frac{(\alpha^n-\beta^n)(\alpha^n+\beta^n)}{\sqrt5}=\frac{\alpha^{2n}-\beta^{2n}}{\sqrt5}=F_{2n}$。

这三条我建议你亲手推一遍，尤其 Cassini 的展开，能练出对 $\alpha\beta=-1$ 的敏感度。实际做题时，凡出现 $F_{n+1}F_{n-1}-F_n^2$ 这种"错位乘积减平方"的形状，第一反应就该是 Cassini。

2.4 Binet 公式在模意义下的失效与补救

这是很多人踩坑的地方。Binet 公式里含 $\sqrt5$，在有理数域外没有意义，但你写代码对 $10^9+7$ 取模时又想用它怎么办？答案是二次剩余：只要 $5$ 是模 $p$ 的二次剩余，就能在 $\mathbb{F}_p$ 里找到 $\sqrt5$，公式照用。

$5$ 是模奇素数 $p$ 的二次剩余的充要条件是 $p\equiv\pm1\pmod 5$。而 $p\equiv\pm2\pmod 5$ 时，$\sqrt5$ 落在扩域 $\mathbb{F}_{p^2}$ 里，此时仍可用公式，但要用"复数对"表示元素 $a+b\sqrt5$ 并按 $(a+b\sqrt5)(c+d\sqrt5)=(ac+5bd)+(ad+bc)\sqrt5$ 做乘法。我写过一版这样的实现，跑起来比矩阵快速幂慢三成左右，唯一的优势是不需要 $2\times2$ 矩阵乘法。

注意：$p=5$ 时 $\sqrt5\equiv0$，Binet 公式退化成 $F_n\equiv n\cdot3^{n-1}\cdot\ldots$ 形式，需要单独处理。我吃过这个亏，用通用代码跑 $p=5$ 直接除零，查了半小时才发现是模数选择的问题。

3. 恒等式清单与四条证明路线的取舍

3.1 加法公式家族及其相互推出关系

加法公式是整组恒等式的枢纽，我把它拆成四条：

$$F_{m+n}=F_mF_{n+1}+F_{m-1}F_n \tag{3.1}$$

$$L_{m+n}=L_mL_n-(-1)^nL_{m-n} \tag{3.2}$$

$$2F_{m+n}=F_mL_n+F_nL_m \tag{3.3}$$

$$2L_{m+n}=5F_mF_n+L_mL_n \tag{3.4}$$

(3.3) 和 (3.4) 是最对称的两条，来源都是 $\alpha^{m+n}\pm\beta^{m+n}$ 的展开。以 (3.3) 为例：$2F_{m+n}=\frac{2(\alpha^{m+n}-\beta^{m+n})}{\sqrt5}$，而 $F_mL_n+F_nL_m=\frac{(\alpha^m-\beta^m)(\alpha^n+\beta^n)+(\alpha^n-\beta^n)(\alpha^m+\beta^m)}{\sqrt5}$，分子展开后交叉项恰好抵消，剩下 $2\alpha^{m+n}-2\beta^{m+n}$，两边相等。

(3.1) 的证明推荐用归纳，因为它的系数最"不对称"，用 Binet 展开容易写错符号。归纳的关键一步是 $F_{m+n+1}=F_{m+n}+F_{m+n-1}$，把两个归纳假设代进去，整理成 $F_m(F_{n+1}+F_n)+F_{m-1}(F_n+F_{n-1})=F_mF_{n+2}+F_{m-1}F_{n+1}$，正好是 $n+1$ 的形式。

一个实用的记忆技巧：把 (3.1) 看成矩阵等式

$$\begin{pmatrix}F_{m+n}\F_{m+n-1}\end{pmatrix}=\begin{pmatrix}F_{n+1}&F_n\F_n&F_{n-1}\end{pmatrix}\begin{pmatrix}F_m\F_{m-1}\end{pmatrix}$$

矩阵的第一列是 $(F_{n+1},F_n)$，第二列是 $(F_n,F_{n-1})$，你永远不需要记哪个下标是 $n+1$ 哪个是 $m-1$，只要保证行内下标之和恒为 $m+n$ 附近即可。

3.2 d'Ocagne 恒等式与它的三个特殊化

$$F_mF_{n+1}-F_{m+1}F_n=(-1)^nF_{m-n} \tag{3.5}$$

这条式子在线性代数里有个漂亮的解释：它是二阶行列式，衡量的是"相邻两项构成的向量"的线性相关性。取 $n=m$ 得 $F_mF_{m+1}-F_{m+1}F_m=0$，平凡；取 $m=n+1$ 得 $F_{n+1}^2-F_{n+2}F_n=(-1)^n$，这就是 Cassini；取 $m=2n$ 得 $F_{2n}F_{n+1}-F_{2n+1}F_n=(-1)^nF_n$，稍作整理可以导出 $F_n\mid F_{2n}$。

我实测过一个常见错误：把 (3.5) 右边写成 $(-1)^{m-n}F_{m-n}$ 或 $(-1)^{m+n}$。核对时用 $m=5,n=2$：左边 $F_5F_3-F_6F_2=5\times2-8\times1=2$，右边 $(-1)^2F_3=2$。用这个小例子验一遍，比反复推符号可靠。

3.3 求和类恒等式：从平方和到卷积

这几条属于"必须会"的档位：

$$\sum_{k=0}^{n}F_k^2=F_nF_{n+1},\qquad \sum_{k=0}^{n}F_k=F_{n+2}-1,\qquad \sum_{k=0}^{n}L_k=L_{n+2}-1$$

平方和那条的几何证明非常漂亮：把边长为 $F_1,F_2,\ldots,F_n$ 的正方形依次按照 Fibonacci 螺旋的方式拼接，拼成的矩形两边恰为 $F_{n+1}$ 和 $F_n$，于是面积等于 $F_nF_{n+1}$。这个证明比归纳法更能让你理解为什么右边是"两个相邻项之积"。

卷积恒等式 $\sum_{k=0}^{n}F_kF_{n-k}=\frac{nL_n-F_n}{5}$ 是另一类，证明用生成函数最快。由 $\sum F_nx^n=\frac{x}{1-x-x^2}$，平方得 $\sum_n\left(\sum_kF_kF_{n-k}\right)x^n=\frac{x^2}{(1-x-x^2)^2}$，右边部分分式展开后用 $\sum L_nx^n=\frac{2-x}{1-x-x^2}$ 即可读出系数。生成函数法在处理"乘积之和"时几乎无往不利，代价是要熟悉部分分式那套操作。

3.4 四条证明路线的适用场景对比

我的习惯是：先看结论里有没有"错位乘积"或"幂"的形状，有就用 Binet；结论是求和或计数，找组合解释；要写代码落地，直接走矩阵。四条路线不是互斥的，很多题目用两条交叉验证能立刻发现笔误。

4. 整除结构：$\gcd(F_m,F_n)=F_{\gcd(m,n)}$ 与 $F_m\mid F_n$

4.1 关键引理：从"下标相减"看最大公约数

这条定理是整个 Fibonacci 数论的地基，证明的核心是一个欧几里得式的递推。先证引理：对 $n>m\ge1$，

$$\gcd(F_m,F_n)=\gcd(F_m,F_{n-m})$$

由加法公式 (3.1)，取 $F_n=F_{m+(n-m)}=F_mF_{n-m+1}+F_{m-1}F_{n-m}$。两边对 $F_m$ 取最大公约数，第一项被 $F_m$ 整除，因此

$$\gcd(F_m,F_n)=\gcd(F_m,F_{m-1}F_{n-m})$$

此时需要 $\gcd(F_m,F_{m-1})=1$。这个也很好证：由 Cassini，$F_{m+1}F_{m-1}-F_m^2=(-1)^m$，任何同时整除 $F_m$ 和 $F_{m-1}$ 的数必整除右边 $\pm1$，故互素。于是

$$\gcd(F_m,F_n)=\gcd(F_m,F_{n-m})$$

这就把"两个大下标"降成了"一次减法"。反复做带余除法，最终 $\gcd(m,n)$ 出现，定理得证。整个过程和欧几里得算法完全同构，这也是为什么很多人说"Fibonacci 数把整数除法抄了一遍"。

4.2 推论：整除关系的完全刻画

从主定理立刻得到：$F_m\mid F_n$ 当且仅当 $m\mid n$（在 $m\ge1$ 的前提下）。充分性直接由主定理推出——若 $m\mid n$，则 $\gcd(F_m,F_n)=F_{\gcd(m,n)}=F_m$。必要性的边角在于 $m=1,2$ 时要单独看，因为 $F_1=F_2=1$ 会让下标不唯一，写严谨的证明必须声明"$m\ge3$"或"取下标的规范表示"。

这条推论还有几个好用的衍生结论。第一，$F_n$ 是偶数的充要条件是 $3\mid n$，因为 $F_3=2$。第二，$L_n$ 是偶数的充要条件是 $3\mid n$，验证 $L_3=4$。第三，若 $p$ 是素数且 $p\mid F_n$，则 $n$ 是某个"最小出现下标"的倍数，这个最小下标记作 $z(p)$，称为 $p$ 在 Fibonacci 数列中的秩，它是研究 Fibonacci 素数的核心工具。

注意 $5$ 那一行：$F_5=5$，所以 $F_n$ 被 $5$ 整除当且仅当下标被 $5$ 整除。但 $F_{10}=55$ 已经含两个因子 $5$，$F_{25}$ 含更多，这里有不规则的 $p$-进赋值规律（LTE 引理的适用范围），没法用一张表打发。

4.3 Lucas 数与 Fibonacci 数的互素性

$\gcd(F_n,L_n)$ 有完全确定的答案。由 $L_n=F_{n-1}+F_{n+1}=F_{n-1}+(F_n+F_{n-1})=2F_{n-1}+F_n$，取最大公约数：

$$\gcd(F_n,L_n)=\gcd(F_n,2F_{n-1})=\gcd(F_n,2)$$

最后一步用了 $\gcd(F_n,F_{n-1})=1$。因此 $\gcd(F_n,L_n)$ 只可能是 $1$ 或 $2$，取 $2$ 当且仅当 $F_n$ 是偶数，即 $3\mid n$。这个结论很干净，说明两条数列几乎处处互素，搭在一起不会互相"污染"。

反过来，$\gcd(L_m,L_n)$ 就不那么整齐了，一般结论是 $\gcd(L_m,L_n)$ 整除 $L_{\gcd(m,n)}$，且当 $\frac{m}{\gcd(m,n)}$ 与 $\frac{n}{\gcd(m,n)}$ 都是奇数时等于 $L_{\gcd(m,n)}$，否则等于 $1$ 或 $2$（取决于 $3$ 的整除情况）。这个分类讨论我当年写了整整一页纸，写代码验证过 $m,n\le30$ 的全部组合才敢用。

实操心得：涉及 Lucas 数的 gcd 结论，强烈建议先写个暴力脚本跑一遍小范围，把表格打出来再动笔证。纯靠直觉推符号，出错率远高于 Fibonacci 那边，因为 $L_0=2$ 引入了额外的因子 $2$。

5. 模周期、矩阵快速幂与工程侧实现

5.1 Pisano 周期的定义与两个实用结论

把 Fibonacci 数列逐项对 $m$ 取模，得到的序列必然是周期序列，因为相邻两项的组合只有 $m^2$ 种，一旦某个二元组重复，后面就整段重复。这个最小正周期记作 $\pi(m)$，叫 Pisano 周期。前几个值：$\pi(2)=3$，$\pi(3)=8$，$\pi(4)=6$，$\pi(5)=20$，$\pi(10)=60$。

两个结论在写代码时特别管用。第一，$\pi(m)\le6m$，这个上界保证了周期不会爆炸，也给出了"枚举到 $6m$ 必然遇到循环"的终止条件。第二，$\pi(10^k)=15\cdot10^{k-1}$（$k\ge1$），所以十进制下末 $k$ 位的周期是可以精确算出来的。$\pi(10^3)=1500$，意味着 $F_{1500}$ 和 $F_0$ 末三位相同。这个性质常被用来出题"求 $F_{10^9}$ 的末三位"，答案是 $000$，因为 $1500\mid10^9$ 不成立——实际要算 $10^9\bmod1500=1000$，再求 $F_{1000}\bmod1000$，验算得 $875$。

5.2 $\begin{pmatrix}1&1\1&0\end{pmatrix}^n$ 的显式形式与证明

矩阵恒等式是整篇内容里最"工程友好"的一条：

$$\begin{pmatrix}1&1\1&0\end{pmatrix}^n=\begin{pmatrix}F_{n+1}&F_n\F_n&F_{n-1}\end{pmatrix} \tag{5.1}$$

证明用归纳。$n=1$ 时右边是 $\begin{pmatrix}F_2&F_1\F_1&F_0\end{pmatrix}=\begin{pmatrix}1&1\1&0\end{pmatrix}$，成立。设 $n$ 成立，左乘一次 $\begin{pmatrix}1&1\1&0\end{pmatrix}$，新矩阵的 $(1,1)$ 元素是 $F_{n+1}+F_n=F_{n+2}$，$(1,2)$ 是 $F_{n+1}$，$(2,1)$ 是 $F_{n+1}$，$(2,2)$ 是 $F_n$，正好是 $n+1$ 的形式。

对 (5.1) 两边取行列式：左边是 $(-1)^n$，右边是 $F_{n+1}F_{n-1}-F_n^2$，立刻得到 Cassini。这条推理链说明矩阵形式和恒等式是同一件事的两种写法——一个适合算，一个适合证。

5.3 快倍增实现与对拍验证

下面这段基于 (5.1) 推出的倍增公式，是我实际项目里用的版本，避免了矩阵乘法的 $8$ 次乘法，只要 $3$ 次：

def fib_pair(n, mod=None): """返回 (F_n, F_{n+1})，mod 为 None 时不取模""" if n == 0: return (0, 1) a, b = fib_pair(n >> 1, mod) t = a * ((2 * b - a) if mod is None else (2 * b - a) % mod) c = t if mod is None else t % mod # F_{2k} d = a * a + b * b # F_{2k+1} d = d if mod is None else d % mod if n & 1: return (d, (c + d) if mod is None else (c + d) % mod) return (c, d)

推导依据是 $F_{2k}=F_k(2F_{k+1}-F_k)$ 与 $F_{2k+1}=F_k^2+F_{k+1}^2$。第一条由 $F_{2k}=F_kL_k$ 和 $L_k=2F_{k+1}-F_k$ 得到；第二条由 $F_k^2+F_{k+1}^2=F_{2k+1}$ 得到，而后者可以用组合解释（把 $F_{2k+1}$ 拆成两类路径）或 Binet 直接验证。

对拍脚本我一般这样写，用朴素递推做参照，跑前 $200$ 项：

def fib_naive(n): a, b = 0, 1 for _ in range(n): a, b = b, a + b return a for i in range(200): assert fib_pair(i)[0] == fib_naive(i), i MOD = 10**9 + 7 for i in range(200): assert fib_pair(i, MOD)[0] == fib_naive(i) % MOD, i

注意：递归版在 $n$ 极大时（比如 $n=10^{18}$）深度只有 $60$ 层，完全安全；但如果你写成迭代版又忘了在每一步取模，中间值会膨胀到几万位，Python 的大整数运算会突然变慢十倍以上。这个坑我在一次批量计算里踩过，加个% mod就恢复了。

5.4 大数下标下的取模陷阱

计算 $F_n\bmod m$ 时，$n$ 本身可能是天文数字甚至以字符串形式给入。这时候有两个思路：一是用 Pisano 周期把 $n$ 降下来，$\pi(m)$ 可以暴力枚举到 $6m$ 求得；二是直接把 $n$ 按十进制逐位处理，利用 $F_{10k+r}$ 的加法公式。

第二种更容易写对，因为不依赖周期上界的实际紧致性。思路是把 $n$ 拆成十进制串，维护 $(F_k,F_{k+1})$ 的状态，每读一位 $d$，用 $10$ 次加法把状态推进到 $10k$，再用 $d$ 次加法到位。总复杂度 $O(\log n)$ 次加法，代码朴素但可靠。

6. 组合解释与 Zeckendorf 表示：让恒等式变得"显然"

6.1 $F_{n+1}$ 计数的对象究竟是什么

很多人背了十年 Fibonacci 递推，却说不清 $F_{n+1}$ 到底数了什么。答案是：长度为 $n$ 的二进制串中，不含相邻两个 $1$ 的串的个数。记这个数为 $a_n$，按末位分类：末位为 $0$ 时，前面任意合法，共 $a_{n-1}$ 个；末位为 $1$ 时，倒数第二位必须是 $0$，前面任意合法，共 $a_{n-2}$ 个。所以 $a_n=a_{n-1}+a_{n-2}$，初值 $a_1=2=F_3$，$a_2=3=F_4$，归纳得 $a_n=F_{n+1}$。

这个解释的威力在于，很多求和恒等式在这个模型下是"显然"的。比如 $\sum_{k=0}^{n}F_k^2=F_nF_{n+1}$：左边可以理解成按"最后一个 $1$ 的位置"对所有合法串分类计数。而 $\sum_kF_k=F_{n+2}-1$ 可以理解成所有合法串（长度不超过 $n$）的总数减一。

6.2 Zeckendorf 定理的陈述与唯一性证明

定理：任何正整数 $N$ 都能唯一地表示为若干个互不相邻的 Fibonacci 数之和，且这些 Fibonacci 数的下标不小于 $2$。

存在性用贪心：取不超过 $N$ 的最大 Fibonacci 数 $F_{k_1}$，递归处理 $N-F_{k_1}$。关键引理是 $N-F_{k_1}<F_{k_1-1}$，否则 $F_{k_1}+F_{k_1-1}=F_{k_1+1}\le N$，与 $F_{k_1}$ 的最大性矛盾。这条引理保证了贪心后剩下的部分不会用到 $F_{k_1-1}$，从而下标不相邻。

唯一性需要更细的估计：任意 $k$ 个互不相邻的 Fibonacci 数（下标从 $2$ 起）之和严格小于 $F_{k+2}$。用归纳证：设最大的下标是 $m$，则总和不超过 $F_m+F_{m-2}+F_{m-4}+\cdots$，而 $F_m+F_{m-2}+\cdots+F_{2}\le F_{m+1}-1<F_{m+1}$。于是若两种表示不同，取最大的分歧位置，会导致一方之和严格大于另一方，矛盾。

这个定理在编码里有实际用处：Zeckendorf 表示可以做定长压缩，且相邻位不会同时为 $1$，天然避免了某些传输中的模式冲突。我做过一个小实验，把一批随机整数用 Zeckendorf 表示后统计位宽，比二进制平均多约 $44%$ 的位数，但相邻位约束带来的模式简化在某些场景下反而更省。

6.3 用组合模型直接证 $\sum_k\binom{n-1-k}{k}=F_n$

这条恒等式我第一次见时觉得莫名其妙，用组合模型一解释就很自然。仍然数长度为 $n-1$ 的合法串，按"$1$ 出现的个数"分类：若恰有 $k$ 个 $1$，它们把串分成若干段，且每两个 $1$ 之间至少隔一个 $0$。选位置等价于从 $n-k$ 个"压缩后"的位置里选 $k$ 个，即 $\binom{n-k}{k}$……下标需要按具体约定调整，标准形式的写法是

$$F_n=\sum_{k=0}^{\lfloor (n-1)/2\rfloor}\binom{n-1-k}{k}$$

验证 $n=6$：$\binom{5}{0}+\binom{4}{1}+\binom{3}{2}=1+4+3=8=F_6$，成立。这条式子在需要"把 Fibonacci 数拆成二项式系数之和"时非常好用，比如证明 $F_n$ 的某些同余性质时，二项式系数可以逐项分析。

我个人的体会是，组合解释不是"锦上添花"，而是判断一个恒等式是否写错的快速手段。当你在两个看似不同的表达式之间犹豫时，把它们各自翻译成计数问题，往往一眼就能看出哪个对。

最后分享一个我用了很久的小习惯：每证完一条恒等式，就用 Python 跑一遍 $n\le20$ 的数值校验，把结果和手推的表格并排放。数学推导里的符号错误极其隐蔽，尤其是 $(-1)^n$ 这类交替项，肉眼检查十遍不如机器跑一遍。真正让证明可靠的，从来不是推导时的自信，而是推导之后的验证。