第1卷第4章斐波那契数列和生成函数

从等比数列与无穷级数出发，把斐波那契递推编码为生成函数，经移位消元、分母分解与取系数推导封闭表达式，并用多条证据回验。

学习目标

能用两个初值、适用下标和递推关系完整定义斐波那契数列，并解释递推来自什么分类
能从有限等比和过渡到生成函数，用乘以 x 的移位对齐递推并推导有理式
能通过分母分解、特征方程和取系数得到斐波那契封闭表达式，并区分形式与解析证据
能用初值、递推、系数和增长率四条独立证据验收推导，指出浮点近似的边界

从找规律开始追问生成机制

看到 $0,1,1,2,3,5,8,\ldots$ ，我们很容易回答“后一项等于前两项之和”。但有限前缀可以由许多不同规则延拓，因此这句话还不是定义。本章的必须和初值、适用下标一起出现：

F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\quad(n\ge2).

先预测：递推式依赖前项，为什么还能得到第 $n$ 项的整体公式？含无理数的表达式为什么能精确产生整数？无穷级数不收敛时，生成函数的系数运算是否也全部失效？下面用“定义—编码—消元—取系数—验收”逐步回答。

乘以 x 是下标移位；按同次幂对齐后，递推被压缩为函数方程。

第1卷第4章的四个关键词

本章的官方单元是“斐波那契数列和生成函数”，其中四个关键词分别是：斐波那契数列提供对象，等比数列与无穷级数提供展开模板，生成函数把整条数列编码成一个对象，递推关系与封闭表达式连接局部生成规则与任意下标的整体计算。作者目录可在《数学女孩》系列页面核对。

这四个关键词不是四个并列结论。等比级数先告诉我们怎样展开 $(1-\alpha x)^{-1}$ ；生成函数再把递推中的相邻项放到同一组幂次；分母因子最后暴露特征根，取系数才回到数列。每一次换表示，都要说明输入对象和回译方式。

斐波那契数列：局部规则和组合理由

前几项为

0,1,1,2,3,5,8,13,21,34,\ldots

由 $F_0=0$ 、 $F_1=1$ 开始， $F_2=F_1+F_0=1$ ， $F_3=F_2+F_1=2$ 。有些展示从 $1,1$ 开始，但只要明确索引约定，就可以与本章的 $F_0$ 版本互相换算；如果不写 $F_0$ ，生成函数的常数项和一次项很容易错位。

递推还可以来自分类计数。设 $T_n$ 是用长度 1 或 2 的砖铺满长度 $n$ 的铺法数。最后一块若长 1，删去它后有 $T_{n-1}$ 种；若长 2，删去它后有 $T_{n-2}$ 种。两类互斥且覆盖全部铺法，于是

T_n=T_{n-1}+T_{n-2},\qquad T_0=1,\quad T_1=1.

所以 $T_n=F_{n+1}$ 。这个例子说明，加法不是数字表面的巧合，而是来自互斥分类；若分类重叠会重复计数，若遗漏情况会少计。

递推式不仅生成数字，还可以来自互斥且完备的组合分类。

等比数列与无穷级数：生成函数的展开模板

先看有限等比和。令

S_N=1+r+r^2+\cdots+r^N.

乘以 $r$ 并相减，得到

(1-r)S_N=1-r^{N+1},\qquad S_N=\frac{1-r^{N+1}}{1-r}\quad(r\ne1).

有限公式是代数恒等式，不需要极限。若让 $N$ 趋于无穷并希望写成普通数值等式，则必须检查 $r^{N+1}$ 是否趋于零；在实数或复数的通常解析意义下，只有 $|r|<1$ 时才有

1+r+r^2+\cdots=\frac1{1-r}.

当 $r=2$ 时，代数分式 $1/(1-r)=-1$ 虽然有定义，但部分和发散，不能把普通无穷和写成 $-1$ 。这个边界提醒我们：解析收敛和形式系数运算使用相似符号，却承担不同证明职责。

生成函数：把整条数列编码成一个对象

给定数列 $a_0,a_1,a_2,\ldots$ ，定义

A(x)=\sum_{n\ge0}a_nx^n=a_0+a_1x+a_2x^2+\cdots.

记号 $[x^n]A(x)$ 表示取 $x^n$ 的系数，所以 $[x^n]A(x)=a_n$ 。这里的 $x$ 首先是位置标记：幂次保存下标，系数保存数值。系数层面可以像处理多项式一样逐项运算，只要目标次数的系数由有限次运算确定。

更严格地说，关注系数恒等式；解析幂级数还要把 $x$ 当成数，并说明收敛区域。推导斐波那契系数时，形式观点已经足够；解释最近奇点和增长率时，才需要补上解析观点。

移位消元：让递推变成代数方程

定义

F(x)=\sum_{n\ge0}F_nx^n.

乘以 $x$ 会把每个系数向高一次幂移动一格，乘以 $x^2$ 移动两格：

\begin{aligned} F(x)&=F_0+F_1x+F_2x^2+F_3x^3+\cdots,\\ xF(x)&=F_0x+F_1x^2+F_2x^3+\cdots,\\ x^2F(x)&=F_0x^2+F_1x^3+\cdots. \end{aligned}

计算 $F-xF-x^2F$ 。对所有 $n\ge2$ ， $x^n$ 的系数是 $F_n-F_{n-1}-F_{n-2}=0$ ；只剩边界项 $F_0=0$ 和 $F_1-F_0=1$ ，因此

(1-x-x^2)F(x)=x,\qquad F(x)=\frac{x}{1-x-x^2}.

这就是生成函数方法的机械核心：乘 $x$ 完成下标移位，按同次幂对齐后，高阶递推项全部消去，初值留下分子。更一般地，若 $G_0=a$ 、 $G_1=b$ 且仍满足同一递推，则

G(x)=\frac{a+(b-a)x}{1-x-x^2}.

分母编码共同的递推动力，分子编码初始状态。边界项必须单独核对，不能凭记忆把斐波那契的分子 $x$ 复制到所有同类递推。

乘以 x 是下标移位；按同次幂对齐后，递推被压缩为函数方程。

分母分解与封闭表达式

令黄金比及其共轭为

\varphi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2}.

它们都满足 $u^2=u+1$ ，并且 $\varphi+\psi=1$ 、 $\varphi\psi=-1$ ，所以

1-x-x^2=(1-\varphi x)(1-\psi x).

部分分式分解得到

F(x)=\frac1{\sqrt5}\left(\frac1{1-\varphi x}-\frac1{1-\psi x}\right).

使用等比级数模板

\frac1{1-\alpha x}=\sum_{n\ge0}\alpha^nx^n

并比较系数，得到

F_n=\frac{\varphi^n-\psi^n}{\sqrt5}.

这里的特征根不是另一个偶然技巧：试探 $F_n=r^n$ 会得到 $r^2-r-1=0$ ，它的根正是 $\varphi$ 、 $\psi$ ；生成函数分母的因子和下标域的指数模式表达同一结构。

递推的特征根与生成函数分母的因子表达同一增长结构。

无理数为何仍然给出整数

令

B_n=\frac{\varphi^n-\psi^n}{\sqrt5}.

先算 $B_0=0$ 、 $B_1=1$ 。利用 $\varphi^2=\varphi+1$ 和 $\psi^2=\psi+1$ ，可以得到 $B_n=B_{n-1}+B_{n-2}$ 。二阶递推配合两个初值唯一确定数列，因此 $B_n=F_n$ ，整数性来自它与整数递推序列相同，而不是来自浮点四舍五入。

从共轭也能看出抵消：把 $\sqrt5$ 换成 $-\sqrt5$ 会交换 $\varphi$ 和 $\psi$ ，分子与分母同时变号，整个表达式不变。无理数只是中间表示，最终系数由递推和初值唯一确定。

增长率、解析边界与数值实现

因为 $|\psi|<1$ 且 $\varphi>1$ ，所以

F_n\sim\frac{\varphi^n}{\sqrt5},\qquad \frac{F_{n+1}}{F_n}\to\varphi.

这里的 $\sim$ 表示。它解释了斐波那契数列近似按黄金比指数增长。对很大的 $n$ ，普通浮点数会放大舍入误差，不能把“结果接近整数”当成精确算法；需要精确整数时，应使用快速倍增或矩阵幂。

生成函数的最近奇点位于 $x=1/\varphi$ ，它控制系数的指数尺度。形式推导告诉我们系数恒等式，解析观点解释增长率；两种证据互相支持，却不能把形式等式直接当作所有数值 $x$ 上的收敛结论。

export function fibonacciFastDoubling(n: bigint): bigint {
  if (n < 0n) throw new RangeError("n must be non-negative");
  if (n === 0n) return 0n;
 
  const [a, b] = fibonacciFastDoublingPair(n / 2n);
  const c = a * (2n * b - a);
  const d = a * a + b * b;
  return n % 2n === 0n ? c : d;
}
 
function fibonacciFastDoublingPair(n: bigint): [bigint, bigint] {
  if (n === 0n) return [0n, 1n];
  const [a, b] = fibonacciFastDoublingPair(n / 2n);
  const c = a * (2n * b - a);
  const d = a * a + b * b;
  return n % 2n === 0n ? [c, d] : [d, c + d];
}

封闭表达式适合揭示结构和渐近增长，快速倍增适合精确计算。选择算法时要说明目标是证明、近似，还是大整数交付，不能因为公式看起来短就把精度和复杂度责任省略。

四条证据验收封闭表达式

可靠推导至少保留四条互相独立的证据：初值 $F_0,F_1$ 一致；封闭式代回原递推成立；生成函数系数确实是目标项；主导增长与 $\varphi$ 的估计相符。它们分别定位边界项、特征根、索引和渐近判断中的错误。

不能只用前十项数值吻合证明公式，因为有限样本仍可能被另一条规则伪造；也不能只做符号分解而不核对系数索引，因为 $F_n$ 和 $F_{n+1}$ 只差一个 $x$ 因子。

独立证据共同定位索引错位、符号错误、分子漏项和增长判断错误。

三步动手复习

分步1 / 3

1. 递推：给局部规则补上语义

先写 $F_0,F_1$ 和适用下标，再用长度 1 或 2 的铺砖分类解释加法。检查两类是否互斥且覆盖全部对象，避免把数字规律当成无证据猜想。

递推式不仅生成数字，还可以来自互斥且完备的组合分类。

本章练习

练习

问题 1：递推定义。 为什么只给出 $0,1,1,2,3,5$ 不能唯一确定后续数列？请写出本章采用的完整定义。

问题 2：生成函数消元。 对斐波那契生成函数说明为什么 $(1-x-x^2)F(x)=x$ ，并指出分子来自哪里。

问题 3：封闭表达式。 说明为什么 $F_n=(\varphi^n-\psi^n)/\sqrt5$ 中的无理数不会让结果失去整数性。

问题 4：证据选择。 如果生成函数分式看起来正确，但 $F_3$ 算错了，应优先检查哪一类证据？为什么？

本章回顾

斐波那契数列由初值、适用下标和递推关系共同定义，递推也可以来自互斥完备的组合分类。
等比数列与无穷级数提供展开模板；有限恒等式、形式幂级数和解析收敛必须区分。
生成函数用幂次保存下标，乘以 x 实现移位；按同次幂消元后，递推变成代数方程。
分母分解暴露特征根，取系数得到封闭表达式；无理数的整数性可由初值和递推回验。
渐近等价解释黄金比主导的指数增长，快速倍增则适合精确大整数计算。
发布级推导应同时保存初值、递推、系数和增长率四条证据，不能只凭有限数值吻合。

名词解释

本章出现的专业名词，用大白话再讲一遍。

递推关系: 用较低下标的已知项构造较高下标项的规则，必须和初值及适用范围一起定义数列。
生成函数: 用幂级数系数记录整个数列的对象，移位、乘法和取系数可以表达递推。
形式幂级数: 只按每个幂次的系数进行运算的符号对象，不先要求把变量代入某个收敛数值。
封闭表达式: 直接用下标 $n$ 表达数列第 $n$ 项的公式，不需要逐项递推。
特征方程: 把指数试探解代入递推关系后得到的多项式方程，其根决定递推的增长模式。
渐近等价: 两个量的比值趋于 1，用来表达主导增长相同，而不是逐项相等。