递推关系

递推关系（recurrence relation）用较早的值定义较晚的值。只给更新规则还不够，必须同时给出足够的初始值。例如 $F_{n} = F_{n - 1} + F_{n - 2}$ 若没有 $F_{0}, F_{1}$ ，可以产生无数条不同数列；取 $F_{0} = 0, F_{1} = 1$ 才确定常见的斐波那契数列 $0, 1, 1, 2, 3, 5, \dots$ 。

由最后一步分类得到递推

设 $a_{n}$ 为长度为 $n$ 、且没有连续两个 1 的二进制串数量。空串只有一种，所以 $a_{0} = 1$ ；长度 1 有 0、1 两种，所以 $a_{1} = 2$ 。对 $n \geq 2$ ，若串以 0 结尾，前面 $n - 1$ 位有 $a_{n - 1}$ 种；若以 1 结尾，倒数第二位只能是 0，前面 $n - 2$ 位有 $a_{n - 2}$ 种。因此 $a_{n} = a_{n - 1} + a_{n - 2}, a_{0} = 1, a_{1} = 2.$ 依次得 $a_{2} = 3$ （00、01、10）、 $a_{3} = 5$ 。这种按末尾分类的论证同时证明了递推式为何不重不漏。

解递推与验证不是一回事

若猜到一个显式公式，仍要代入初值和递推式验证。比如 $u_{n + 1} = 2 u_{n}$ 、 $u_{0} = 3$ 给出 $u_{n} = 3 \cdot 2^{n}$ ：起点为 3，且 $3 \cdot 2^{n + 1} = 2 (3 \cdot 2^{n})$ 。验证保证公式适用于全部指标；只比对前几项不够。生成函数则把整条递推数列编码进一个代数式。

参考资料

MIT，Mathematics for Computer Science，Recurrences 章节。
MIT 6.042J Fall 2010，Mathematics for Computer Science 课程讲义。
继续阅读：数学归纳法、差分方程模型、生成函数。