前面两章已经把归纳法、强归纳和递归定义放在一起看过。现在我们把注意力转向另一类很常见的问题：一个对象不是一次写完，而是从初始状态出发，按照同一条规则一步一步生成。
每天账户余额的变化、算法每次调用后剩下的工作量、树的高度和节点数、斐波那契数列、动态规划表格，背后都可以出现递推关系。递推关系的语言很短：给出前面的值，再说明后面的值怎样由它们得到。真正要学会的是三件事：会生成序列，会把递推式展开成结构，会用归纳法验证得到的闭式。
序列可以看成按自然数编号的一串对象。最常见的是数列：
有些教材从 开始编号，有些从 开始编号。两种都可以，但同一道题里必须保持一致。本章主要使用 作为起点，因为递归算法和计算机数组常把第一个位置记作 。
递推定义通常包括两部分。第一部分是初始条件，例如 。第二部分是递推规则，例如
这两部分合在一起，才能逐项生成：
递推式中的下标范围不是装饰。写 时，必须说明它从哪个 开始成立。若从 开始，它使用的是已经给出的 ；若从 开始，就会出现 ，除非题目另外定义了这个对象。
递推关系也可以定义集合、字符串、树或算法运行时间。例如长度为 的二进制字符串有多少个，可以记为 。因为每个长度为 的字符串后面可以接 或 ，所以
这里的 表示空字符串只有一个。这个例子提醒我们，初始值常常不是“看起来最小的非空对象”，而是让递推规则从一开始就正确运转的基准对象。
给定递推式后，最稳妥的第一步常常是列出前几项。列项不是证明，但它能帮助我们检查定义是否理解正确，也能给闭式猜想提供线索。
例如递推式
生成的前几项是
每一步都只看前一项，所以它是一阶递推。这个“一阶”不是说公式简单，而是说新项只依赖前一项。
前几项相同并不保证两条递推定义完全相同。递推关系要由初始条件、递推规则和适用范围共同决定。只比较前三四项，很容易把不同序列误认成同一个序列。
生成前几项之后，下一步常常是把递推式往回代入。这个动作叫迭代展开。它的目的不是机械地把式子写长，而是看清反复出现的结构。
考虑
先展开一次：
再把 替换成 ：
再展开一次：
照这个模式继续到 ，得到
因为 ，所以
等比和公式给出
于是
设 ，且对 有
写出 的展开形式。
先展开前两层，观察系数如何累积：
整理第二层：
展开 层后，会得到
代入 ，得到
迭代展开常常比直接猜闭式更可靠，因为它保留了每一步替换的来源。以后遇到更复杂的递推式时，也可以先展开几层，不急着套公式。
一阶线性递推最常见的形状是
其中 和 是常数。它可以描述“旧量按比例保留，再加上固定新量”的过程。账户每期按利率增长后再存入固定金额，库存每期保留一部分后再补货，算法规模每步按比例缩小后增加固定开销，都能写出这种结构。
通过迭代展开，可以得到统一形式：
当 时，等比和给出
当 时，递推式变成
所以
一阶线性递推有两个常用视角。迭代展开适合找闭式；固定点视角适合理解长期趋势。若 有固定值 ，满足 ，那么 。这说明序列与固定值的距离每步乘以 。
递推式擅长说明“下一步怎么来”，闭式擅长直接计算“第 项是多少”。下面的工具把两种计算放在同一张表里，适合用来检查展开是否正确。
注意闭式不是比递推式“更真实”的定义。很多问题天然就是按步发生的，递推式反而更贴近问题本身。闭式的好处是计算和比较更方便；递推式的好处是建模和证明更直接。
如果下一项需要前两项一起决定，就得到二阶递推。典型形式是
这时只给一个初始值不够。因为要算 ，需要知道 和 ；要算 ，需要知道 和 。所以二阶递推通常要给两个初始条件。
斐波那契数列是最常见的二阶递推：
前几项是
它的规则很朴素，却已经展示了二阶递推的关键特征：当前位置不是只看上一项，而是同时保留两个相邻状态。
设
如果只知道 ，仍然无法确定 。不同的 会生成不同序列：
和
都满足同一条递推规则，却不是同一条序列。这说明递推规则本身不是完整定义，初始条件的数量要和依赖的历史长度相匹配。
不要把“递推式的阶数”和“公式里最高次幂”混在一起。 仍然是一阶递推，因为它只依赖 ； 是二阶递推，因为它依赖前两项。
递推式描述值之间的关系；递归过程描述计算时如何调用自己。二者经常写成相似的形式，但含义不同。
例如斐波那契数列的递推定义是数学对象：
如果把它直接翻译成递归计算，就会出现这样的过程：要算 ，先算 和 ；要算 ，又要算 和 。同一个 、 会被多次计算。
递归定义很适合表达对象本身。它短、清楚、贴近结构。但计算同一个对象时，可以有不同过程：
这三种过程可以计算同一条数列，但运行时间差别很大。离散数学关心的不只是“值是什么”，也关心“过程为什么正确”和“过程会花多少步”。
看到递归定义时，不要立刻把它等同于低效程序。低效的往往不是递归思想本身，而是不保存重复子问题的直接计算方式。递推关系、递归过程和具体实现要分开判断。
递归算法的运行时间也常用递推式描述。若某个算法处理规模为 的问题时，会递归处理一个规模为 的子问题，并额外做 步工作，那么可以写成
若它把问题拆成两个规模为 的子问题，并额外做 步合并工作，就可能写成
本章不展开算法复杂度的完整理论，只要先抓住一点：递推式可以描述数列本身，也可以描述一个递归过程的成本。
闭式是不用前面各项就能直接表示 的公式。例如
就是闭式；而
是递推定义。它们描述的是同一条序列：
从递推式到闭式，常见路线有三步：先算前几项，观察差、比或重复结构；再迭代展开；最后用归纳证明闭式确实满足原递推定义。
不同递推式会留下不同痕迹：
这些只是线索，不是证明。线索帮我们提出候选公式，证明要检查候选公式是否真的覆盖所有 。
要证明一个闭式和递推定义一致，最常用的方法是数学归纳法。证明时需要检查两件事：闭式是否给出正确初始值；如果前一项符合闭式，代入递推式后下一项是否也符合闭式。
设
证明
先检查初始值。当 时，闭式右边为
这与 一致。
作归纳假设。设某个 时有
使用递推式，把 写成 ：
代入归纳假设并整理：
因此闭式对 成立，且从任意 成立能推出 成立。由数学归纳法， 对所有 成立。
这个证明的关键是：归纳步骤必须使用原来的递推式。如果只把闭式自己变形一遍，没有说明它和递推定义如何连接。
验证闭式时，只要闭式满足同一组初始条件和同一条递推规则，就确定了同一条序列。递推定义的“唯一生成”性质，正是归纳法在背后起作用。
先定义 表示什么。不要只写公式，要说明下标 代表时间、规模、长度、步数还是对象数量。
写出足够的初始条件。一阶递推通常需要一个初始值，二阶递推通常需要两个初始值，分段递推可能需要更多说明。
写出从旧状态到新状态的规则，并标明它从哪个 开始适用。
计算前几项，检查结果是否符合问题语境。如果数值已经和直观矛盾，先回到定义和下标。
若需要闭式，先展开或观察结构，再用归纳法验证，不把猜想当作结论。
本章的重点不是记住某个万能公式，而是把“按步生成”的对象说清楚。递推关系给出局部规则，递归过程展示计算结构，闭式帮助直接计算，而归纳法负责把猜出的公式重新固定在递推定义上。
这里已经出现了等比和的影子。
当 时，下标降到 。
若继续使用等比和公式，还可以化成 。
我们要证明 。
这正是闭式在 时的形式。