递推关系

递推不是单独的一条等式，而是生成序列的局部规则加足够初始条件。阶数表示确定下一项需要追溯多长历史；初值不足会留下多解，初值与规则冲突则可能无解。递推适合揭示对象如何由更小对象构成，闭式则适合直接读取增长，两者各有用途。

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

规则 $a_n=a_{n-1}+2$ 若给 $a_0=1$，唯一生成 $1,3,5,\dots$；不指定 $a_0$ 时有一族平移解。Catalan 递推包含卷积，Fibonacci 是二阶线性递推，二者求解工具不同。若递推只对 $n\ge 2$ 成立，就必须明确 $a_0,a_1$，不能从公式向负索引任意倒推。

序列公理库序列Sequence以自然数为定义域的函数。配合局部函数公理库函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。关系形成递推，线性递推公理库线性递推Linear recurrence relation当前项由固定数量先前项的线性组合给出。可用迭代展开、特征根、矩阵或普通生成函数公理库普通生成函数Ordinary generating function把序列编码为形式幂级数 Σ a_n x^n。处理。分治算法的运行时间常使用主定理估计，组合对象的根分解和动态规划状态转移也会先自然产生递推，再通过界估计或闭式求解理解规模增长；方法能否使用取决于线性、齐次性和系数结构。