递推关系

闭式告诉你如何直接从 $n$ 找到 $a_n$，递推告诉你当前问题怎样从较小问题接起来。两者描述同一序列的不同方面：计数模型常先给出递推，增长分析则可能更需要闭式或上下界。

唯一性有一个很短的归纳证明。若两个解具有相同初值，并在 $n$ 之前都相同，那么代入同一个单值函数 $F$ 后，第 $n$ 项也相同。逐步推进便排除了分叉。这个论证依赖“下一步确实有定义”，不是只写几个初始数字就自动成立。

从对象的末尾导出递推 ​

设 $b_n$ 为长度 $n$、不含相邻两个 $1$ 的二进制串数。空串只有一个，所以 $b_0=1$；长度一的串是 $0,1$，所以 $b_1=2$。

对 $n\ge 2$，合法串按末位分两类。末位为 $0$ 时，去掉它得到任意长度 $n-1$ 的合法串；末位为 $1$ 时，末两位必须是 $01$，去掉这两位得到任意长度 $n-2$ 的合法串。两种删除都有唯一的逆操作，且两类不相交，因此

于是 $b_2=3,b_3=5$。长度三的五个串确为 $000,001,010,100,101$。这不是从几个数字猜公式，而是用末尾结构证明每个对象恰被数一次。

初值、值域与分支缺一不可 ​

Fibonacci 关系 $F_n=F_{n-1}+F_{n-2}$ 配合 $F_0=0,F_1=1$ 得到熟悉的序列；改用 $F_0=2,F_1=1$ 会产生另一序列。相同递推并不意味着相同解。

关系 $a_n^2=a_{n-1}$ 不给出唯一的实数后继：从 $a_0=1$ 出发，第一步可选 $1$ 或 $-1$，而选 $-1$ 后再求下一实数项就失败。有限步可继续和可生成整个无限序列也要分清。

即使是显式形式，也可能遇到值域问题。$a_n=1/a_{n-1}$ 在 $a_0=0$ 时第一步无定义；在整数值域中，$a_0=2$ 也无法继续。说明值域和分母条件是数学定义的一部分。

闭式如何核验 ​

若 $a_n=a_{n-1}+2$、$a_0=1$，候选闭式为 $a_n=2n+1$。先检查 $n=0$，再检查 $2n+1=(2(n-1)+1)+2$。两个检查配合唯一性才证明所有项正确；仅核对前十项不能替代归纳论证。

线性递推理路线性递推Linear recurrence relation当前项由固定数量先前项的线性组合给出。是一类结构较强的递推，常系数齐次情形可用特征根或生成函数理路普通生成函数Ordinary generating function把序列编码为形式幂级数 Σ a_n x^n。求解。含卷积的 Catalan 递推不是固定阶数线性递推，不能套同一特征方程。

算法中的递推既可以描述值，也可以描述成本。计算上面的 $b_n$ 时，朴素递归会在计算 $b_{n-1}$ 的过程中再次计算 $b_{n-2}$；按索引递增保存前两项，就能用 $O(n)$ 次加法得到结果。这改变计算过程，不改变序列，而且加法次数不等于大整数运算的位复杂度。分治成本中的 $T(n)=2T(\lfloor n/2\rfloor )+O(n)$ 则是在估计增长，初始规模和取整约定仍然需要明确。

从组合问题建立递推时，最值得核对的是分解是否穷尽、各类是否互斥、删除操作是否可逆。前两项保证可以使用加法原理理路加法原理Sum rule · Addition principle互斥有限选择类的总数等于各类大小之和。，最后一项保证较小对象数真的等于该类对象数。