形式陈述

递推关系用序列先前项约束后续项。阶数为 $k$$k$ 的显式递推可写成

$$ a_n=F(n,a_{n-1},\ldots,a_{n-k})\qquad(n\ge k). $$$$a_n=F(n,a_{n-1},\dots ,a_{n-k})(n\ge k).$$

给定足以启动递推的初始值 $a_0,\ldots,a_{k-1}$$a_0,\dots ,a_{k-1}$ 后，若 $F$$F$ 在相关输入上为单值函数，才唯一确定整个序列。递推也可为隐式、含多个分支或同时定义多条序列。

直觉

递推不是一次给出第 $n$$n$ 项的闭式，而是给出从已知状态推进到下一状态的规则。初始条件相当于选择从哪里开始，缺少它们通常只得到一族解。

例子与边界

Fibonacci 递推 $F_n=F_{n-1}+F_{n-2}$$F_n=F_{n-1}+F_{n-2}$ 单独不能确定序列；配合 $F_0=0,F_1=1$$F_0=0,F_1=1$ 才唯一。递推 $a_n^2=a_{n-1}$$a_n^2=a_{n-1}$ 即使给定初值也可能有符号分支，说明“关系”未必提供唯一更新函数。

推论与应用

递推关系用于算法运行时间、组合对象计数、动态规划与离散动力系统。求解方法包括迭代展开、特征方程、生成函数和主定理；方法适用性取决于线性、齐次性和系数结构。

参考资料

• Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994，Ch. 1。
• Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, 2011，§§1.1–1.2。