递推数列与不动点法

递推公式给出相邻项的关系，求通项就是把这个关系解开。高中范围内能解开的类型不多，但都对应一个固定套路：差已知的累加，比已知的累乘，形如 $a_{n+1} = pa_n + q$ 的借不动点平移成等比数列。

1 · 累加法与累乘法

$a_{n+1} - a_n = f(n)$ 时把 $n = 1, 2, \dots, n-1$ 各式相加，左端只剩首末两项：

于是求通项化归成求和，$f$ 是等差或等比时直接套闭式。$a_{n+1} = a_n + 2n$、$a_1 = 1$ 给出 $a_n = 1 + 2 \cdot \frac{(n-1)n}{2} = 1 + n(n-1)$，前几项 $1, 3, 7, 13, 21$。

$\frac{a_{n+1}}{a_n} = g(n)$ 时把各式相乘，左端只剩首末两项：$a_n = a_1 \prod_{k=1}^{n-1} g(k)$。$a_{n+1} = \frac{n+1}{n} a_n$、$a_1 = 2$ 时连乘的中间因子逐个抵消，得 $a_n = 2n$。累乘法要求各项非零，否则比值无意义。

2 · 一阶线性递推与不动点

$a_{n+1} = pa_n + q$ 里既有倍数又有常数项，直接累加或累乘都不成。办法是先把常数项吸收掉：解方程 $x = px + q$ 得不动点 $x = \frac{q}{1 - p}$，两边同减这个 $x$：

于是 $\{a_n - x\}$ 是公比 $p$ 的等比数列，$a_n = (a_1 - x)p^{n-1} + x$。不动点的几何意义是这个递推的常数解：首项恰取 $x$ 时数列恒等于 $x$，一步也不动。

$|p| < 1$ 时 $p^{n-1} \to 0$，各项收敛到不动点；$|p| > 1$ 时偏离被逐次放大，数列发散。$p < 0$ 时偏离每步换一次符号，各项在不动点两侧交替出现。这三种形态由 $p$ 单独决定，$q$ 只挪动不动点的位置，$a_1$ 只决定初始偏离的大小与方向。

3 · p = 1 处不动点不存在

$p = 1$ 时方程 $x = x + q$ 无解（除 $q = 0$ 外），不动点不存在。此时递推本就是 $a_{n+1} = a_n + q$，即公差为 $q$ 的等差数列，通项 $a_n = a_1 + (n-1)q$。

这一支在代码里必须单列。linearRecurrence 若不判 $p = 1$ 就直接算 $\frac{q}{1-p}$，得到的是 Infinity；再拿它去算 $(a_1 - x)p^{n-1} + x$ 就是 $-\infty + \infty$，结果 NaN。而 NaN 不会抛错，它会顺着后续的比较与格式化一路传下去，图上表现为整条数列凭空消失。数值实现里这类「无解」的分支比公式里更要紧：公式失效时人会停下来讨论，浮点数不会。

4 · 参考文献

1. Recurrence relation. Wikipedia. 递推关系的分类与一阶线性递推的解法。https://en.wikipedia.org/wiki/Recurrence_relation
2. Fixed point (mathematics). Wikipedia. 不动点的定义及其在迭代中的作用。https://en.wikipedia.org/wiki/Fixed_point_(mathematics)
3. Linear difference equation. Wikipedia. 线性差分方程的通解结构。https://en.wikipedia.org/wiki/Linear_difference_equation