Fibonacci与Lucas数列全解析：Binet公式、恒等式与矩阵快速幂

做竞赛题和写数值代码的人多少都遇到过这样的时刻明明只想算个数列结果题面里同时冒出 Fibonacci 数列和 Lucas 数列还要求你证明一串看起来毫不相干的性质与推论。我早年在整理一份手写笔记时也卡在这个地方——单独看 Fibonacci 数列的性质每条都能背下来可一旦把 Lucas 数列摆在旁边很多结论就有了更短、更统一的证明路径。这篇内容想做的事情很具体把这两个数列的定义、互推关系、Binet 公式、恒等式、整除结构、模周期和组合解释串成一条完整的线把每条性质的证明过程写透把为什么这么证讲清楚。它既适合正在准备数学竞赛、需要把证明写严谨的读者也适合写高性能计算代码、需要把公式落成实现的工程读者。文中所有推导我都配了可直接运行的校验代码你抄下去跑一遍就能验证每一步没有虚构。1. 两条数列为什么必须成对出现定义、初值与互推关系1.1 递推定义与前若干项的对照表先把地基打平。Fibonacci 数列的递推是 $F_00,\ F_11,\ F_nF_{n-1}F_{n-2}$Lucas 数列的递推结构完全相同只是初值换成 $L_02,\ L_11$。初学者最容易犯的错是把递推关系相同误当成这两个数列是同一回事的两种写法。实际上递推关系只是一个二阶线性变换初值才决定了你最终落在哪条轨道上。二阶线性递推的状态空间是二维的任何一个满足 $x_nx_{n-1}x_{n-2}$ 的数列都可以唯一地写成 $x_naF_nbL_n$ 的形式。换个说法Fibonacci 数列和 Lucas 数列构成了这个递推关系的一组基。这就是它们必须成对出现的第一层原因——不是数学家喜欢凑对而是二维空间需要两个基向量。$n$0123456789101112$F_n$01123581321345589144$L_n$213471118294776123199322$L_n-2F_n$2-110112358132134最后一行很关键$L_n-2F_nF_{n-2}$$n\ge 2$。这不是巧合而是基变换的显式写法。你可以马上写出 $F_n\frac{L_n-L_{n-1}}{2}$ 或者 $L_nF_{n-1}F_{n1}$这些换算在证明里能省掉大量代数运算。1.2 $L_nF_{n-1}F_{n1}$ 的两种证明路径这条恒等式是我用得最多的一条必须证到位。归纳法的写法是这样的$n1$ 时 $F_0F_2011L_1$$n2$ 时 $F_1F_3123L_2$。设 $n-1,n$ 时成立则$$F_nF_{n2}(F_{n-1}F_{n-2})(F_{n1}F_n)(F_{n-1}F_{n1})(F_{n-2}F_n)L_nL_{n-1}L_{n1}$$归纳成立。这条路稳妥但不够透明看不出为什么会这样。代数法更直观。设 $\alpha\frac{1\sqrt5}{2},\ \beta\frac{1-\sqrt5}{2}$则 $F_n\frac{\alpha^n-\beta^n}{\sqrt5}$。于是$$F_{n-1}F_{n1}\frac{\alpha^{n-1}(1\alpha^2)-\beta^{n-1}(1\beta^2)}{\sqrt5}$$注意到 $\alpha^2\alpha1$所以 $1\alpha^2\alpha2$同理 $1\beta^2\beta2$。又因为 $\alpha^2\alpha1$ 两边乘 $\alpha$ 得 $\alpha^3\alpha^2\alpha2\alpha1$即 $\alpha(\alpha2)2\alpha^2\alpha$……这里绕了一圈换个更干净的做法直接验证 $\alpha(1\alpha^2)\alpha(\alpha2)2\alpha1$同理 $\beta(\beta2)2\beta1$。于是$$F_{n-1}F_{n1}\frac{(2\alpha1)\alpha^{n-1}-(2\beta1)\beta^{n-1}}{\sqrt5}\frac{\alpha^n\alpha^{n-1}-\beta^n-\beta^{n-1}}{\sqrt5}$$而 $\alpha^n\alpha^{n-1}\alpha^{n-1}(\alpha1)\alpha^{n1}$因为 $\alpha1\alpha^2$所以上式变成 $\frac{\alpha^{n1}-\beta^{n1}}{\sqrt5}F_{n1}$。诶这算出的是 $F_{n1}$ 而不是 $L_{n1}$说明我中间跳了步骤。正确的收尾应该是$F_{n-1}F_{n1}\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\beta1$于是 $\alpha^n\alpha^{n-1}\alpha^{n1}$……这样又回到同一个地方。提示这条路我实测容易绕真正干净的做法是先证明 $L_n\alpha^n\beta^n$ 作为定义再用 $\alpha^n\beta^n(\alpha^{n-1}\beta^{n-1})(\alpha^{n-2}\beta^{n-2})$ 验证它满足 Lucas 递推和初值从而 $L_nF_{n-1}F_{n1}$ 由 $\frac{\alpha^n-\beta^n}{\sqrt5}$ 的移位相减直接得出。绕路说明一件事不要把Lucas 数的闭式当成需要从 $F$ 推出来的结论它本身就是定义的一部分。1.3 负下标延拓与一般 Lucas 序列的统一视角把递推式改写成 $x_{n-2}x_n-x_{n-1}$就能把两条数列延拓到全整数下标。$F_00,F_11$ 给出 $F_{-1}1,F_{-2}-1,F_{-3}2,F_{-4}-3$规律是$$F_{-n}(-1)^{n1}F_n$$同理 $L_{-n}(-1)^nL_n$。这两条式子在处理下标差为负的恒等式时特别有用比如 dOcagne 恒等式里 $mn$ 的情形直接套用就能避免分类讨论。更值得推广的是Lucas 序列$U_n(P,Q)$ 与 $V_n(P,Q)$设 $\alpha\betaP,\ \alpha\betaQ$定义$$U_n\frac{\alpha^n-\beta^n}{\alpha-\beta},\qquad V_n\alpha^n\beta^n$$取 $P1,Q-1$ 时 $U_nF_n,\ V_nL_n$取 $P2,Q-1$ 得到 Pell 序列取 $P1,Q-2$ 得到 Jacobsthal 序列其闭式里出现 $2^n$。这个统一视角的价值在于你在 Fibonacci 上证的每一条恒等式几乎都能原封不动搬到 $U_n,V_n$ 上只是 $\DeltaP^2-4Q$ 和 $Q^n$ 需要替换。一般形式对应 Fibonacci/Lucas 形式$U_{2n}U_nV_n$$F_{2n}F_nL_n$$V_n^2-\Delta U_n^24Q^n$$L_n^2-5F_n^24(-1)^n$$U_{mn}U_mV_n-Q^nU_{m-n}$$F_{mn}F_mL_n-(-1)^nF_{m-n}$$2U_{mn}U_mV_nU_nV_m$$2F_{mn}F_mL_nF_nL_m$我把这张表贴在显示器边上用了很久它比任何单条恒等式都好记因为右边只是左边的一个特例。要注意 $Q-1$ 带来的符号翻转这是最容易写错的地方。2. Binet 公式的完整推导与它作为证明工具的使用边界2.1 特征方程法从递推到闭式的标准流程常系数线性递推的通项求解有一套固定流程值得完整走一遍。设 $x_nrx^{n}$ 形式的解代入 $x_nx_{n-1}x_{n-2}$ 得 $r^nr^{n-1}r^{n-2}$约掉 $r^{n-2}$ 得特征方程$$r^2r1\quad\Longrightarrow\quad r\frac{1\pm\sqrt5}{2}$$两根互异因此通解是 $x_nA\alpha^nB\beta^n$。用初值定系数$F_00$ 给出 $AB0$$F_11$ 给出 $A\alphaB\beta1$。联立得 $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.6180341$。后者意味着 $\beta^n\to0$所以 $F_n$ 就是 $\frac{\alpha^n}{\sqrt5}$ 四舍五入到最近整数。这个四舍五入性质在算大数下标、判断某数是否 Fibonacci 数时非常实用——只要检查 $5x^2\pm4$ 是否完全平方即可这是判别法的完整依据。2.2 $\alpha$、$\beta$ 的代数关系表Binet 公式的证明力全部来自 $\alpha,\beta$ 之间那几条几乎不证自明的关系。我整理成表做恒等式证明时逐条对照使用关系式数值核对用途$\alpha\beta1$$1.618(-0.618)1$降幂、合并同类项$\alpha\beta-1$$1.618\times(-0.618)-1$处理 $\alpha^{-1}-\beta$$\alpha-\beta\sqrt5$$1.6180.6182.236$分母有理化$\alpha^2\alpha1$$2.6182.618$把 $\alpha^2$ 降为一次$\beta^2\beta1$$0.3820.382$同上$\alpha^k\alpha F_kF_{k-1}$$k3$$4.2364.236$连通幂与数列最后一条值得单独立出来它把$\alpha$ 的幂翻译成Fibonacci 数的线性组合很多竞赛题的突破口就在这里。证明只需归纳$k1$ 时 $\alpha\alpha\cdot10$ 成立设 $k$ 成立则 $\alpha^{k1}\alpha(\alpha F_kF_{k-1})\alpha^2F_k\alpha F_{k-1}\alpha(F_kF_{k-1})F_k\alpha F_{k1}F_k$。同理有 $\beta^k\beta F_kF_{k-1}$。2.3 用 Binet 公式一次性推平三条经典恒等式Cassini 恒等式$F_{n1}F_{n-1}-F_n^2(-1)^n$。代入 Binet 公式分子是$$(\alpha^{n1}-\beta^{n1})(\alpha^{n-1}-\beta^{n-1})-(\alpha^n-\beta^n)^2$$展开第一项为 $\alpha^{2n}-\alpha^{n1}\beta^{n-1}-\alpha^{n-1}\beta^{n1}\beta^{2n}$第二项为 $\alpha^{2n}-2\alpha^n\beta^n\beta^{2n}$。相减得$$-\alpha^{n1}\beta^{n-1}-\alpha^{n-1}\beta^{n1}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)^25$分子为 $-(-1)^{n-1}\cdot55(-1)^n$。除以 $(\sqrt5)^25$得 $(-1)^n$。证毕。Lucas 数的范数恒等式$L_n^2-5F_n^24(-1)^n$。这个更简单因为 $L_n^2-5F_n^2(\alpha^n\beta^n)^2-(\alpha^n-\beta^n)^24(\alpha\beta)^n4(-1)^n$。一行出结果。乘法公式$F_nL_nF_{2n}$。左边等于 $\frac{(\alpha^n-\beta^n)(\alpha^n\beta^n)}{\sqrt5}\frac{\alpha^{2n}-\beta^{2n}}{\sqrt5}F_{2n}$。这三条我建议你亲手推一遍尤其 Cassini 的展开能练出对 $\alpha\beta-1$ 的敏感度。实际做题时凡出现 $F_{n1}F_{n-1}-F_n^2$ 这种错位乘积减平方的形状第一反应就该是 Cassini。2.4 Binet 公式在模意义下的失效与补救这是很多人踩坑的地方。Binet 公式里含 $\sqrt5$在有理数域外没有意义但你写代码对 $10^97$ 取模时又想用它怎么办答案是二次剩余只要 $5$ 是模 $p$ 的二次剩余就能在 $\mathbb{F}_p$ 里找到 $\sqrt5$公式照用。$5$ 是模奇素数 $p$ 的二次剩余的充要条件是 $p\equiv\pm1\pmod 5$。而 $p\equiv\pm2\pmod 5$ 时$\sqrt5$ 落在扩域 $\mathbb{F}_{p^2}$ 里此时仍可用公式但要用复数对表示元素 $ab\sqrt5$ 并按 $(ab\sqrt5)(cd\sqrt5)(ac5bd)(adbc)\sqrt5$ 做乘法。我写过一版这样的实现跑起来比矩阵快速幂慢三成左右唯一的优势是不需要 $2\times2$ 矩阵乘法。注意$p5$ 时 $\sqrt5\equiv0$Binet 公式退化成 $F_n\equiv n\cdot3^{n-1}\cdot\ldots$ 形式需要单独处理。我吃过这个亏用通用代码跑 $p5$ 直接除零查了半小时才发现是模数选择的问题。3. 恒等式清单与四条证明路线的取舍3.1 加法公式家族及其相互推出关系加法公式是整组恒等式的枢纽我把它拆成四条$$F_{mn}F_mF_{n1}F_{m-1}F_n \tag{3.1}$$$$L_{mn}L_mL_n-(-1)^nL_{m-n} \tag{3.2}$$$$2F_{mn}F_mL_nF_nL_m \tag{3.3}$$$$2L_{mn}5F_mF_nL_mL_n \tag{3.4}$$(3.3) 和 (3.4) 是最对称的两条来源都是 $\alpha^{mn}\pm\beta^{mn}$ 的展开。以 (3.3) 为例$2F_{mn}\frac{2(\alpha^{mn}-\beta^{mn})}{\sqrt5}$而 $F_mL_nF_nL_m\frac{(\alpha^m-\beta^m)(\alpha^n\beta^n)(\alpha^n-\beta^n)(\alpha^m\beta^m)}{\sqrt5}$分子展开后交叉项恰好抵消剩下 $2\alpha^{mn}-2\beta^{mn}$两边相等。(3.1) 的证明推荐用归纳因为它的系数最不对称用 Binet 展开容易写错符号。归纳的关键一步是 $F_{mn1}F_{mn}F_{mn-1}$把两个归纳假设代进去整理成 $F_m(F_{n1}F_n)F_{m-1}(F_nF_{n-1})F_mF_{n2}F_{m-1}F_{n1}$正好是 $n1$ 的形式。一个实用的记忆技巧把 (3.1) 看成矩阵等式$$\begin{pmatrix}F_{mn}\F_{mn-1}\end{pmatrix}\begin{pmatrix}F_{n1}F_n\F_nF_{n-1}\end{pmatrix}\begin{pmatrix}F_m\F_{m-1}\end{pmatrix}$$矩阵的第一列是 $(F_{n1},F_n)$第二列是 $(F_n,F_{n-1})$你永远不需要记哪个下标是 $n1$ 哪个是 $m-1$只要保证行内下标之和恒为 $mn$ 附近即可。3.2 dOcagne 恒等式与它的三个特殊化$$F_mF_{n1}-F_{m1}F_n(-1)^nF_{m-n} \tag{3.5}$$这条式子在线性代数里有个漂亮的解释它是二阶行列式衡量的是相邻两项构成的向量的线性相关性。取 $nm$ 得 $F_mF_{m1}-F_{m1}F_m0$平凡取 $mn1$ 得 $F_{n1}^2-F_{n2}F_n(-1)^n$这就是 Cassini取 $m2n$ 得 $F_{2n}F_{n1}-F_{2n1}F_n(-1)^nF_n$稍作整理可以导出 $F_n\mid F_{2n}$。我实测过一个常见错误把 (3.5) 右边写成 $(-1)^{m-n}F_{m-n}$ 或 $(-1)^{mn}$。核对时用 $m5,n2$左边 $F_5F_3-F_6F_25\times2-8\times12$右边 $(-1)^2F_32$。用这个小例子验一遍比反复推符号可靠。3.3 求和类恒等式从平方和到卷积这几条属于必须会的档位$$\sum_{k0}^{n}F_k^2F_nF_{n1},\qquad \sum_{k0}^{n}F_kF_{n2}-1,\qquad \sum_{k0}^{n}L_kL_{n2}-1$$平方和那条的几何证明非常漂亮把边长为 $F_1,F_2,\ldots,F_n$ 的正方形依次按照 Fibonacci 螺旋的方式拼接拼成的矩形两边恰为 $F_{n1}$ 和 $F_n$于是面积等于 $F_nF_{n1}$。这个证明比归纳法更能让你理解为什么右边是两个相邻项之积。卷积恒等式 $\sum_{k0}^{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 公式一步到位不需要构造含根式符号易错模运算受限涉及 $\alpha^n\pm\beta^n$ 的恒等式数学归纳严谨、无技巧要求需先猜到结论单下标、结构规则的等式组合计数揭示本质需要构造双射难度大求和、计数、不等式下界矩阵可移植到算法自动给出取模实现手算推导较繁琐需要快速计算或模运算的场景我的习惯是先看结论里有没有错位乘积或幂的形状有就用 Binet结论是求和或计数找组合解释要写代码落地直接走矩阵。四条路线不是互斥的很多题目用两条交叉验证能立刻发现笔误。4. 整除结构$\gcd(F_m,F_n)F_{\gcd(m,n)}$ 与 $F_m\mid F_n$4.1 关键引理从下标相减看最大公约数这条定理是整个 Fibonacci 数论的地基证明的核心是一个欧几里得式的递推。先证引理对 $nm\ge1$$$\gcd(F_m,F_n)\gcd(F_m,F_{n-m})$$由加法公式 (3.1)取 $F_nF_{m(n-m)}F_mF_{n-m1}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_{m1}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$。必要性的边角在于 $m1,2$ 时要单独看因为 $F_1F_21$ 会让下标不唯一写严谨的证明必须声明$m\ge3$或取下标的规范表示。这条推论还有几个好用的衍生结论。第一$F_n$ 是偶数的充要条件是 $3\mid n$因为 $F_32$。第二$L_n$ 是偶数的充要条件是 $3\mid n$验证 $L_34$。第三若 $p$ 是素数且 $p\mid F_n$则 $n$ 是某个最小出现下标的倍数这个最小下标记作 $z(p)$称为 $p$ 在 Fibonacci 数列中的秩它是研究 Fibonacci 素数的核心工具。结论等价条件首次出现$F_n$ 为偶数$3\mid n$$F_32$$F_n$ 被 $4$ 整除$6\mid n$$F_68$$F_n$ 被 $5$ 整除$5\mid n$$F_55$$L_n$ 为偶数$3\mid n$$L_34$注意 $5$ 那一行$F_55$所以 $F_n$ 被 $5$ 整除当且仅当下标被 $5$ 整除。但 $F_{10}55$ 已经含两个因子 $5$$F_{25}$ 含更多这里有不规则的 $p$-进赋值规律LTE 引理的适用范围没法用一张表打发。4.3 Lucas 数与 Fibonacci 数的互素性$\gcd(F_n,L_n)$ 有完全确定的答案。由 $L_nF_{n-1}F_{n1}F_{n-1}(F_nF_{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_02$ 引入了额外的因子 $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\bmod15001000$再求 $F_{1000}\bmod1000$验算得 $875$。5.2 $\begin{pmatrix}11\10\end{pmatrix}^n$ 的显式形式与证明矩阵恒等式是整篇内容里最工程友好的一条$$\begin{pmatrix}11\10\end{pmatrix}^n\begin{pmatrix}F_{n1}F_n\F_nF_{n-1}\end{pmatrix} \tag{5.1}$$证明用归纳。$n1$ 时右边是 $\begin{pmatrix}F_2F_1\F_1F_0\end{pmatrix}\begin{pmatrix}11\10\end{pmatrix}$成立。设 $n$ 成立左乘一次 $\begin{pmatrix}11\10\end{pmatrix}$新矩阵的 $(1,1)$ 元素是 $F_{n1}F_nF_{n2}$$(1,2)$ 是 $F_{n1}$$(2,1)$ 是 $F_{n1}$$(2,2)$ 是 $F_n$正好是 $n1$ 的形式。对 (5.1) 两边取行列式左边是 $(-1)^n$右边是 $F_{n1}F_{n-1}-F_n^2$立刻得到 Cassini。这条推理链说明矩阵形式和恒等式是同一件事的两种写法——一个适合算一个适合证。5.3 快倍增实现与对拍验证下面这段基于 (5.1) 推出的倍增公式是我实际项目里用的版本避免了矩阵乘法的 $8$ 次乘法只要 $3$ 次def fib_pair(n, modNone): 返回 (F_n, F_{n1})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_{2k1} 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_{k1}-F_k)$ 与 $F_{2k1}F_k^2F_{k1}^2$。第一条由 $F_{2k}F_kL_k$ 和 $L_k2F_{k1}-F_k$ 得到第二条由 $F_k^2F_{k1}^2F_{2k1}$ 得到而后者可以用组合解释把 $F_{2k1}$ 拆成两类路径或 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$ 极大时比如 $n10^{18}$深度只有 $60$ 层完全安全但如果你写成迭代版又忘了在每一步取模中间值会膨胀到几万位Python 的大整数运算会突然变慢十倍以上。这个坑我在一次批量计算里踩过加个% mod就恢复了。5.4 大数下标下的取模陷阱计算 $F_n\bmod m$ 时$n$ 本身可能是天文数字甚至以字符串形式给入。这时候有两个思路一是用 Pisano 周期把 $n$ 降下来$\pi(m)$ 可以暴力枚举到 $6m$ 求得二是直接把 $n$ 按十进制逐位处理利用 $F_{10kr}$ 的加法公式。第二种更容易写对因为不依赖周期上界的实际紧致性。思路是把 $n$ 拆成十进制串维护 $(F_k,F_{k1})$ 的状态每读一位 $d$用 $10$ 次加法把状态推进到 $10k$再用 $d$ 次加法到位。总复杂度 $O(\log n)$ 次加法代码朴素但可靠。6. 组合解释与 Zeckendorf 表示让恒等式变得显然6.1 $F_{n1}$ 计数的对象究竟是什么很多人背了十年 Fibonacci 递推却说不清 $F_{n1}$ 到底数了什么。答案是长度为 $n$ 的二进制串中不含相邻两个 $1$ 的串的个数。记这个数为 $a_n$按末位分类末位为 $0$ 时前面任意合法共 $a_{n-1}$ 个末位为 $1$ 时倒数第二位必须是 $0$前面任意合法共 $a_{n-2}$ 个。所以 $a_na_{n-1}a_{n-2}$初值 $a_12F_3$$a_23F_4$归纳得 $a_nF_{n1}$。这个解释的威力在于很多求和恒等式在这个模型下是显然的。比如 $\sum_{k0}^{n}F_k^2F_nF_{n1}$左边可以理解成按最后一个 $1$ 的位置对所有合法串分类计数。而 $\sum_kF_kF_{n2}-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_11}\le N$与 $F_{k_1}$ 的最大性矛盾。这条引理保证了贪心后剩下的部分不会用到 $F_{k_1-1}$从而下标不相邻。唯一性需要更细的估计任意 $k$ 个互不相邻的 Fibonacci 数下标从 $2$ 起之和严格小于 $F_{k2}$。用归纳证设最大的下标是 $m$则总和不超过 $F_mF_{m-2}F_{m-4}\cdots$而 $F_mF_{m-2}\cdotsF_{2}\le F_{m1}-1F_{m1}$。于是若两种表示不同取最大的分歧位置会导致一方之和严格大于另一方矛盾。这个定理在编码里有实际用处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_{k0}^{\lfloor (n-1)/2\rfloor}\binom{n-1-k}{k}$$验证 $n6$$\binom{5}{0}\binom{4}{1}\binom{3}{2}1438F_6$成立。这条式子在需要把 Fibonacci 数拆成二项式系数之和时非常好用比如证明 $F_n$ 的某些同余性质时二项式系数可以逐项分析。组合对象计数结果典型用途长度 $n$ 的无相邻 $1$ 二进制串$F_{n2}$求和恒等式的组合证明用 $1\times2$ 与 $2\times1$ 铺 $2\times n$ 棋盘$F_{n1}$递推关系的直观来源$n$ 级台阶每步走 $1$ 或 $2$ 级$F_{n1}$算法题的状态定义Zeckendorf 表示中的项数约 $\log_\alpha N$压缩编码的位宽估计我个人的体会是组合解释不是锦上添花而是判断一个恒等式是否写错的快速手段。当你在两个看似不同的表达式之间犹豫时把它们各自翻译成计数问题往往一眼就能看出哪个对。最后分享一个我用了很久的小习惯每证完一条恒等式就用 Python 跑一遍 $n\le20$ 的数值校验把结果和手推的表格并排放。数学推导里的符号错误极其隐蔽尤其是 $(-1)^n$ 这类交替项肉眼检查十遍不如机器跑一遍。真正让证明可靠的从来不是推导时的自信而是推导之后的验证。