企业官网建设流程全解析

前阵子帮人看一段算法题的代码，题目要求输出第 n 个 Fibonacci 数对 1000000007 取模，n 给到 10^18。代码用矩阵快速幂写的，格式规整，推导也像模像样，可样例就是差一位。顺着往下查，问题既不在快速幂，也不在取模，而在他自己推的一条恒等式上——他把 F_{2n} = F_n·L_n 记成了 F_{2n} = F_n²，然后一路往下套。这个错误光盯着 Fibonacci 一个数列是很难自查出来的，因为 L_n（Lucas 数）根本不在他的视野里，等号右边的"另一个数列"被他在记忆里悄悄抹掉了。

这就是我把 Fibonacci 数列和 Lucas 数列放在一起讲的原因：它们是同一个二次特征方程下的两族解，一个是"差"，一个是"和"，很多看起来突兀的恒等式，一旦把两者并排摆出来，就变成了同一个式子的两种特例。这篇内容会从递推关系、Binet 公式、矩阵幂、组合计数四个角度把这些性质和证明过一遍，中间夹着我在刷题、写库、做数值验证时踩过的坑。适合三类人：准备笔试面试、需要快速调用恒等式的同学；写算法库、需要处理大 n 取模的开发者；以及纯粹想把初等数论里这块内容捋顺的读者。不需要高深前置知识，会解一元二次方程、知道数学归纳法怎么写，就能跟下来。

1. 先把两个数列摆在同一张桌子上

1.1 单看 Fibonacci 会卡在哪

Fibonacci 数列的定义很干净：F_0 = 0，F_1 = 1，n ≥ 2 时 F_n = F_{n-1} + F_{n-2}。前几项是 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89……这个递推是二阶线性齐次递推，对应的特征方程是 x² = x + 1，也就是 x² - x - 1 = 0。

问题就出在这里：二次方程有两个根。如果你只用 F_0 = 0、F_1 = 1 这一组初值去定解，你得到的是两族解里的一族，另一族被初值"筛掉"了。这在解微分方程时是常识——二阶方程的通解是两个线性无关解的线性组合——但在数列这里，很多人下意识觉得"定义唯一，所以只有一个数列"。

被筛掉的那一族，取初值 L_0 = 2、L_1 = 1，就是 Lucas 数列：2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123……它跟 Fibonacci 满足完全相同的递推式，只是起点不同。这个"起点不同"带来的差异非常关键：F_n 从 0 出发，天然带着整除性、可以被 F_m 反复分解；L_n 从 2 出发，天然带着"始终与某个 Fibonacci 数相差 1"的味道，因此大量出现在判别式、二次域范数、素性检验里。

我的经验是，凡是你推导到一半发现式子左边出现了 F_n²，右边出现了 F_{2n}，或者出现了一个莫名其妙的 ±1，那基本就是 Lucas 数该登场了。它不是在给 Fibonacci 打补丁，它就是另一半答案。

1.2 用 Binet 公式把两条主线拧成一股

把 α = (1+√5)/2，β = (1-√5)/2 记下来。这两个数有几个立刻能用的关系：

• α + β = 1（两根之和等于 -(-1)/1）
• αβ = -1（两根之积等于常数项 -1）
• α - β = √5
• α² = α + 1，β² = β + 1

于是两个数列的通项可以直接写出来：

F_n = (αⁿ - βⁿ)/√5，L_n = αⁿ + βⁿ

这里我要强调一个容易被忽略的细节：为什么 F_n 前面要除 √5？因为 n = 0 时 α⁰ - β⁰ = 0，已经满足 F_0 = 0；n = 1 时 α - β = √5，要让它等于 1，就必须除以 √5。而 L_n 不除，是因为 α⁰ + β⁰ = 2，正好是 L_0。换句话说，这个 √5 不是凭空冒出来的，是被 F_1 = 1 这个初值"逼"出来的。

有了这个统一形式，两条主线的关系一目了然：F_n 是两个共轭数的"差商"，L_n 是"和"。所有涉及 F 和 L 的桥接恒等式，本质上都是在对 αⁿ 和 βⁿ 做加减消元。你在纸上写 (αⁿ + βⁿ)² 和 (αⁿ - βⁿ)²，展开相减，立刻就能看出为什么会有 5F_n² 这种因子。

需要注意，Binet 公式里的 αⁿ、βⁿ 本身是无理数，但组合出来的结果一定是整数——这不是巧合，而是因为 α、β 是同一个整系数二次方程的根，它们的对称多项式必然落在整数环里。理解这一点，你就能预判哪些式子是"应该成立"的，哪些是你推错了。

1.3 四条证明路线，什么时候用哪条

同一批恒等式，至少有四条路可以走。我在不同场合用不同的路，选错路会浪费大量时间，所以先做一张取舍表。

归纳法是最稳的，但它有个硬性要求：因为递推是二阶的，你必须验证 n = 0 和 n = 1（或者 n = 1 和 n = 2），只验一个不够。我见过太多次只写"n = 1 时成立"就直接跳到归纳步骤的，逻辑链在这里断了。

Binet 代入最快，但它对"手算基本功"要求高。比如证明 L_n² - 5F_n² = 4(-1)ⁿ，你直接把两个式子代进去：L_n² - 5F_n² = (αⁿ + βⁿ)² - (αⁿ - βⁿ)² = 4αⁿβⁿ = 4(αβ)ⁿ = 4(-1)ⁿ。三行搞定，中间只用了平方差和 αβ = -1。这条路线之所以快，是因为它把"数列的递推结构"换成了"代数数的乘法结构"。

矩阵幂这条路的附加值最高，因为它顺手就给了你一个 O(log n) 的算法。第四章我会详细用它。

2. 核心恒等式：从加法公式到 Cassini 家族

2.1 加法公式：矩阵给的一次性推导

定义矩阵 A = [[1, 1], [1, 0]]，则 A 的特征多项式是 λ² - λ - 1，恰好是那个特征方程。用归纳法可以证明：

Aⁿ = [[F_{n+1}, F_n], [F_n, F_{n-1}]]（n ≥ 1）

起点 n = 1 时右边是 [[F_2, F_1], [F_1, F_0]] = [[1, 1], [1, 0]] = A，成立。归纳步骤左乘一个 A，用递推式整理即得。这个结论不是炫技，它把"数列的第 n 项"变成了"矩阵的幂"，于是两个数列的乘法关系就自动浮现了。

既然 A^{m+n} = Aᵐ·Aⁿ，把两边都用上式展开比较元素，得到两条核心公式：

• F_{m+n} = F_{m+1}F_n + F_mF_{n-1}
• F_{m+n+1} = F_{m+1}F_{n+1} + F_mF_n

第二条式子取 m = n 就得到 F_{2n+1} = F_{n+1}² + F_n²。这个式子我非常喜欢，因为在快速倍增算法里它是核心：给定 (F_n, F_{n+1})，一步就能跳到 (F_{2n}, F_{2n+1})。

Lucas 数的加法公式稍微麻烦一点，因为它是"和"而不是"差"，直接乘开会带出交叉项。标准结论是：

2L_{m+n} = L_mL_n + 5F_mF_n

代 m = n = 1 验一下：左边 2L_2 = 6，右边 L_1L_1 + 5F_1F_1 = 1 + 5 = 6，对上了。这条式子的证明用 Binet 最快：把 L_mL_n 和 5F_mF_n 都展开成 α、β 的幂，交叉项正好抵消，剩下 2(α^{m+n} + β^{m+n})。

这里有个实操提醒：凡是看到左边系数是 2 的 Lucas 公式，多半是因为展开时产生了 2α^{m+n} 这样的项，为了让右边凑成 L_{m+n} = α^{m+n} + β^{m+n}，左边就得写 2L_{m+n}。记不住公式的时候，用这个方法现推，比硬背可靠得多。

2.2 Cassini 恒等式与它的推广形式

Cassini 恒等式是这块内容里最常被考到的一条：

F_{n+1}·F_{n-1} - F_n² = (-1)ⁿ

验算：n = 1 时 F_2F_0 - F_1² = 1·0 - 1 = -1 = (-1)¹；n = 2 时 F_3F_1 - F_2² = 2·1 - 1 = 1 = (-1)²。成立。

最漂亮的证明还是走矩阵：对 Aⁿ = [[F_{n+1}, F_n], [F_n, F_{n-1}]] 两边取行列式，左边是 det(Aⁿ) = (det A)ⁿ = (-1)ⁿ，右边是 F_{n+1}F_{n-1} - F_n²。一行完事。

但如果你手边没有矩阵工具，归纳法也能走，只是要小心：假设 F_{n+1}F_{n-1} - F_n² = (-1)ⁿ，要证 n+1 时的式子，需要把 F_{n+2}F_n - F_{n+1}² 拆开。具体做法是把 F_{n+2} = F_{n+1} + F_n 代入，得到 (F_{n+1} + F_n)F_n - F_{n+1}² = F_{n+1}F_n + F_n² - F_{n+1}² = F_n² - F_{n+1}(F_{n+1} - F_n) = F_n² - F_{n+1}F_{n-1}，正好是上一步结果的相反数，符号翻转，与 (-1)^{n+1} = -(-1)ⁿ 吻合。这个推导里最关键的一步是认出 F_{n+1} - F_n = F_{n-1}，很多人在这一步卡住，就是因为对递推式的变形不熟。

Cassini 的推广叫 d'Ocagne 恒等式：

F_m·F_{n+1} - F_{m+1}·F_n = (-1)ⁿ·F_{m-n}

取 m = n+1 就退化成 Cassini 的形式，所以它是原式的推广。验算一组：m = 5，n = 2，左边 F_5F_3 - F_6F_2 = 5·2 - 8·1 = 2，右边 (-1)²F_3 = 2，对上。

还有一个更对称的形态，我把它叫做"双指标版本"：

F_{n+k}·F_{n-k} - F_n² = (-1)^{n+k+1}·F_k²

这个式子在处理"两个下标关于中心对称"的问题时特别好用，比如你想估 F_{n+k}F_{n-k} 和 F_n² 差多少，答案是差一个 F_k² 量级的整数，符号由 n+k 的奇偶决定。我验算过 n = 4、k = 2 的情形：F_6F_2 - F_4² = 8·1 - 9 = -1，而 (-1)^{7}F_2² = -1，一致。

提示：这三个式子建议按"Cassini → d'Ocagne → 双指标版"的顺序记。它们的证明都走 Binet 最快，因为 (αᵐ - βᵐ)(αⁿ⁺¹ - βⁿ⁺¹) 展开后交叉项会自然合并。

2.3 桥接恒等式：F 与 L 之间的换算表

这一节是整篇内容里最实用的部分。工程代码里很少同时用两个数列，但推导过程中几乎必然会遇到"这边是 F，那边是 L"的情况。下面这张表是我自己整理并反复验证过的。

这张表里我最想强调的是 F_{2n} = F_n·L_n。它其实是"我开头提到的那个 bug"的正解。很多人会把它记成 F_{2n} = F_n²，因为在 n 较小时两者数值接近（n = 3 时 F_3² = 4，F_6 = 8，差一倍），一旦 n 上去就天差地别。记住右边的因子是 L_n 而不是 F_n，可以省掉大量调试时间。

L_n² - 5F_n² = 4(-1)ⁿ 这条也值得单独说。它说明 L_n 和 F_n·√5 是一对 Pell 型方程的解，因此 (L_n + F_n√5)/2 是单位群里的元素，这也是为什么 Fibonacci 数会跟二次域的算术扯上关系。如果你在做什么"求不定方程整数解"的题目，看到 x² - 5y² = ±4 这种形式，别犹豫，直接往这两个数列上靠。

2.4 求和恒等式与生成函数

单点恒等式解决了"项与项"的关系，求和恒等式解决"前缀和"的关系。常用的几条：

• Σ_{i=1}^{n} F_i = F_{n+2} - 1
• Σ_{i=1}^{n} F_i² = F_n·F_{n+1}
• Σ_{i=0}^{n} L_i = L_{n+2} - 1
• Σ_{i=1}^{n} F_{2i-1} = F_{2n}
• Σ_{i=1}^{n} F_{2i} = F_{2n+1} - 1

第二条的证明有个很漂亮的几何解释：把边长分别为 F_1, F_2, …, F_n 的正方形拼成一个矩形，矩形的短边是 F_n，长边是 F_{n+1}。面积法一步到位，不需要归纳。这也是我给学生讲"为什么平方和恰好是两个相邻项的乘积"时最喜欢用的例子。

生成函数这条路值得单独提一句，因为它是"从递推直接读出通项"的机械方法。设 G(x) = Σ_{n≥0} F_n xⁿ，把递推式两边乘 xⁿ 并对 n ≥ 2 求和，得到 G - x = xG + x²G，解出：

G(x) = x / (1 - x - x²)

Lucas 数同理，只是初值不同，结果是 (2 - x)/(1 - x - x²)。把分母因式分解成 (1 - αx)(1 - βx)，做部分分式展开，Binet 公式就自动掉出来了。这条路的好处是不用"猜"通项长什么样，输入初值和递推，输出就是通项公式。

我实测过，用生成函数推 F_n 的 Binet 公式，从设 G(x) 到整理出结果，熟练的话五分钟以内。比记公式靠谱，尤其适合那些"背了就忘"的读者。

3. 整除结构：gcd 定理与素性线索

3.1 相邻互素与整除链

先立一个地基：对任意 n ≥ 1，gcd(F_n, F_{n+1}) = 1。

证明用欧几里得算法：gcd(F_{n+1}, F_n) = gcd(F_{n+1} - F_n, F_n) = gcd(F_{n-1}, F_n)，一路递降，最后落到 gcd(F_1, F_0) = gcd(1, 0) = 1。这个链条非常干净，而且它和"辗转相除法求最大公约数"是同一套逻辑，只是把整数换成了数列项。

有了相邻互素，就能推出整除链：若 m | n，则 F_m | F_n。

证明的思路是用加法公式 F_{a+b} = F_{a-1}F_b + F_aF_{b+1}。取 a = m，b = (k-1)m，假设 F_m | F_{km}（记为 P(k)），那么 F_{(k+1)m} = F_{m + km} = F_{m-1}F_{km} + F_mF_{km+1}。第一项被归纳假设整除，第二项显式含 F_m，所以整体被 F_m 整除。奠基 k = 1 时 F_m | F_m 显然成立。

这里有个常见误区：很多人把这个命题记成"充要条件"，写成"F_m | F_n 当且仅当 m | n"。这个说法在 m ≥ 3 时是对的，但在小下标上是错的。比如 F_2 = 1，它整除所有 F_n，但 2 并不整除所有 n。再比如 F_1 = 1，同理。所以严谨的表述应该是：m | n ⟹ F_m | F_n 恒成立；反过来，若 m ≥ 3 且 F_m | F_n，则 m | n。

这个"反过来"的证明需要用到下一节的 gcd 定理，我们放在那里一起处理。顺便说一个直接推论，面试里很常见：若 F_n 是素数，则 n 是素数（n = 4 是唯一例外，因为 F_4 = 3 是素数但 4 不是素数）。理由是如果 n = ab 且 a、b 都大于 1，那么 F_a | F_n 且 1 < F_a < F_n，直接矛盾。

3.2 gcd(F_m, F_n) = F_gcd(m,n) 的完整推导

这是整块内容里最有分量的一条定理，值得写清楚每一步。

第一步，证明递推关系 gcd(F_m, F_n) = gcd(F_m, F_{n-m})，其中 n > m。用加法公式取 a = m，b = n - m：

F_n = F_{m + (n-m)} = F_{m-1}F_{n-m} + F_mF_{n-m+1}

右边第二项显然被 F_m 整除，所以 gcd(F_m, F_n) = gcd(F_m, F_{m-1}F_{n-m})。又由 3.1 可知 gcd(F_m, F_{m-1}) = 1，因此 F_m 与 F_{m-1} 互素，可以把它从 gcd 里"约掉"，得到 gcd(F_m, F_n) = gcd(F_m, F_{n-m})。

第二步，注意到这个式子的形式和欧几里得算法完全一致：对下标做减法，gcd 不变。反复应用直到其中一个下标变成 0（或者两者相等），最后得到的就是 F_gcd(m,n)。

第三步，处理边界：gcd(F_m, F_0) = gcd(F_m, 0) = F_m，而 gcd(m, 0) = m，所以 F_gcd(m,0) = F_m，一致。完美闭合。

举个具体的例子练手：求 gcd(F_24, F_36)。由定理，等于 F_gcd(24,36) = F_12 = 144。你可以验证一下 F_24 = 46368 = 144 × 322，F_36 = 14930352 = 144 × 103683，而 322 和 103683 互素（103683 = 322² - 1，所以 gcd(322, 103683) = gcd(322, 1) = 1）。结果吻合。

有了这条定理，3.1 里那个"反过来"就顺了：若 F_m | F_n，则 gcd(F_m, F_n) = F_m，即 F_gcd(m,n) = F_m。在 m ≥ 3 的前提下 F 严格递增，所以 gcd(m, n) = m，即 m | n。逻辑闭环。

注意：这条定理还顺带解释了为什么 Fibonacci 数的素因子分布如此"规整"——F_n 的每个素因子必定首次出现在某个 F_d 上，其中 d | n。做因式分解题时，先算 d 的所有因子，再逐个检查，比直接从 F_n 硬分解快得多。

3.3 Lucas 数列在数论检验里的位置

Lucas 数列不是配角。它在素性检验里的地位，某种程度上比 Fibonacci 还重要。

原因在于 L_n² - 5F_n² = ±4 这条恒等式。写成 (L_n + F_n√5)/2 的形式，你会发现它是一个范数为 ±1 的代数整数，也就是二次域里的"单位"。而单位在模运算下的行为，恰好可以用来做"这个数是不是素数"的判定：如果 p 是素数，那么某些幂次下的单位必须满足特定的同余关系；反过来，如果一个合数也满足，它就被称为伪素数。

现代常用的组合判定思路大致是这样：先做一次以 2 为底的 Miller–Rabin 测试，再对 Lucas 序列（即递推 U_n = P·U_{n-1} - Q·U_{n-2}，取 P = 1、Q = -1 的那一族，正是 Fibonacci/Lucas 的推广）做一次强伪素数测试。公开文献里，同时通过这两关的合数至今没有被找到，因此这个组合在实际工程中被当作"确定性判定"使用。我在写大整数工具时也是这么处理的：先用小素数试除，再上这个组合，最后对结果做一次平方验证。

这里要提醒一句，别把"Lucas 数列"和"Lucas 数"混为一谈。Lucas 数 L_n 是那个具体数列 2, 1, 3, 4, 7…；而 Lucas 序列 U_n(P, Q) 是一整族由参数 P、Q 决定的数列，Fibonacci 对应 P = 1、Q = -1 时的 U_n，Lucas 数则是同一参数下的 V_n。我在文档里见过太多把两者写混的代码注释，读起来非常误导。

4. 模周期与工程实现

4.1 模周期为什么一定存在

先定义：对正整数 m，把序列 F_n mod m 首次回到 (0, 1) 的那个下标 n 称为模 m 的周期，记作 π(m)。

存在性证明非常朴素，但思路值得学。考虑配对序列 (F_n mod m, F_{n+1} mod m)，每个分量只有 m 种取值，所以配对最多有 m² 种。取前 m² + 1 个配对，由抽屉原理必然有两个相同，设下标为 i < j。

接下来是关键一步：这个重复可以"往回倒推"。因为 F_{k-1} = F_{k+1} - F_k，模 m 下同样成立，所以由 (F_i, F_{i+1}) = (F_j, F_{j+1}) 可以推出 (F_{i-1}, F_i) = (F_{j-1}, F_j)，一路倒推到 (F_0, F_1) = (F_{j-i}, F_{j-i+1})。于是 j - i 就是一个周期。

这个证明里"倒推"那一步是精髓：如果只证"存在重复"而不证"能倒推到起点"，你得到的是"最终周期"而不是"纯周期"，结论会弱一大截。我在写笔记时特意把这一步单独标出来，因为它也是判断"某个递推序列模 m 是否纯周期"的通用手法——只要递推的系数在模 m 下可逆，倒推就成立。

顺带说个上界：π(m) ≤ 6m（m ≥ 2）。这个界不紧，但足够用来写暴力枚举的循环上限。

4.2 具体数值与计算技巧

小模数的周期我手算过一批，整理成表，方便你验证自己的代码。

从表里能读出两条规律。第一条是可乘性：若 gcd(a, b) = 1，则 π(ab) = lcm(π(a), π(b))。所以算大模数的周期，只要分解质因数再取最小公倍数。第二条是素数幂的规律：π(2^k) = 3·2^{k-1}（k ≥ 3），π(5^k) = 20·5^{k-1}。这两条一合，就得到十进制末 k 位的周期 π(10^k) = 15·10^{k-1}。k = 1 时是 15？不对，π(10) = 60。这是因为 k = 1 时 2 的幂指数太小，公式的适用条件没满足，要用 lcm(π(2), π(5)) = lcm(3, 20) = 60。k = 2 时 lcm(π(4), π(25)) = lcm(6, 100) = 300，与表格一致。

对素数模 p，还有两条判据：若 p ≡ ±1 (mod 5)，则 π(p) | p - 1；若 p ≡ ±2 (mod 5)，则 π(p) | 2(p+1)。验一下 p = 11：11 ≡ 1 (mod 5)，π(11) = 10，确实整除 10。p = 7：7 ≡ 2 (mod 5)，π(7) = 16，而 2(7+1) = 16，整除且相等。p = 13：13 ≡ 3 ≡ -2 (mod 5)，π(13) = 28，2(13+1) = 28，整除且相等。这两条判据的价值在于，它把"搜索周期"的范围从 6p 压缩到了 p+1 或 2(p+1) 的量级，写程序时可以当作循环上界。

实现在这里给一个直接可用的版本：

def pisano_period(m): """返回模 m 的 Fibonacci 周期，m >= 2""" a, b = 0, 1 for i in range(1, 6 * m + 1): a, b = b, (a + b) % m if a == 0 and b == 1: return i raise ValueError("超出理论上界，检查输入")

这个函数的时间复杂度是 O(π(m))，对 m 上万的情况还能接受，再大就该上因式分解加 lcm 的组合方案了。

4.3 fast doubling：从递推式直接压到 O(log n)

要算 F_n mod p，n 到 10^18，矩阵快速幂和快速倍增都能做到 O(log n)。但我更推荐后者，因为它常数小、不需要维护 2×2 矩阵、代码短。

核心是两条倍角公式（前面 2.3 已经列过）：

• F_{2k} = F_k · (2F_{k+1} - F_k)
• F_{2k+1} = F_k² + F_{k+1}²

给定 (F_k, F_{k+1})，你能在 O(1) 时间内得到 (F_{2k}, F_{2k+1})。再根据 n 的二进制位决定是否"补一步"（从 2k 走到 2k+1，只需 F_{2k+2} = F_{2k} + F_{2k+1}），整个过程就是从左到右扫描二进制位。

def fib_pair(n, mod=None): """返回 (F_n, F_{n+1})，可选取模""" a, b = 0, 1 # (F_0, F_1) for bit in bin(n)[2:]: c = a * ((b << 1) - a) # F_{2k} d = a * a + b * b # F_{2k+1} if bit == '1': a, b = d, c + d # 走到 2k+1 else: a, b = c, d if mod is not None: a, b = a % mod, b % mod return a, b

我逐位验过：n = 5（二进制 101），初始 (0, 1)；处理第一位得 (1, 1)；处理第二位（0）得 (1, 2)；处理第三位（1）得 (5, 8)，即 F_5 = 5、F_6 = 8，正确。

几个实操要点必须记牢。第一，取模要放在每轮迭代末尾，而不是只在最后取，否则中间数会爆炸。第二，Python 的大整数天然不溢出，但 C++ 里 a * ((b << 1) - a) 这一步很容易在 64 位整型上溢出，做法是先模再乘，或者用 __int128 中转。第三，C++ 里 (b << 1) - a 可能为负，取模前要加一个 mod 再取，否则得到负数。第四，n = 0 时循环不执行，返回 (0, 1)，正好是正确结果，不用特判。

顺便给一个估算位数的公式，调试时很有用。由 F_n ≈ αⁿ/√5，取常用对数得 log10(F_n) ≈ n·log10(α) - log10(√5)，其中 log10(α) ≈ 0.2089876402，log10(√5) ≈ 0.3494850022。所以 F_n 的十进制位数为 floor(n × 0.2089876402 - 0.3494850022) + 1。拿 n = 100 验：100 × 0.2089876402 = 20.89876402，减去 0.3494850022 得 20.54927902，取整加一等于 21，而 F_100 = 354224848179261915075，正好 21 位。这个公式我在写大数库时用来预分配缓冲区，比算完再数位数省事。

5. 踩坑记录与速查表

5.1 归纳法起手式的三个坑

第一个坑是只验一个初始值。二阶递推的归纳必须验两项，因为归纳步骤会同时用到 P(n) 和 P(n-1)。我见过一份笔记证明 Σ F_i = F_{n+2} - 1，只写了 n = 1 成立，然后归纳步骤