线性递推

常系数线性递推把有限窗口状态线性推进，因此整个无穷序列由有限个初值决定。试探 $a_n=r^n$ 把移位操作转成乘法，特征多项式的根给出基本增长模式；重根需要乘上 $n^k$，正对应矩阵 Jordan 块的多项式因子。非齐次项则可看作外部输入，解由齐次响应与特解叠加。

Fibonacci 数满足 $F_n=F_{n-1}+F_{n-2}$，特征根为 $\frac{1\pm \sqrt{5}}{2}$。递推“阶数 $k$”通常还隐含最高滞后项实际出现；若 $c_k=0$，可降低有效阶数。特征根方法需在包含足够根的域中解释，非齐次或变系数情形需要其他方法。

Fibonacci 递推 $F_{n+2}=F_{n+1}+F_n$ 的特征方程为 $r^2-r-1=0$，两根给出 Binet 形式。递推 $a_{n+2}-2a_{n+1}+a_n=0$ 有重根 $r=1$，通解是 $a_n=A+Bn$，不能只写常数倍 $1^n$。若系数随 $n$ 变化，标准常系数特征根法不再直接适用。

递推关系公理库递推关系Recurrence relation用先前项规定序列当前项的关系。在环公理库环Ring带加法阿贝尔群和相容乘法的代数结构。上线性化后，可由普通生成函数转成有理函数；反过来，有理普通生成函数的系数最终满足常系数线性递推。伴随矩阵又把序列推进写成矩阵公理库矩阵Matrix以有限行列集合为索引、取值于半环，并以中间指标求和定义乘法的函数。幂。快速幂计算第 $n$ 项、动态规划、自动机计数和线性动态系统都利用有限状态维数，而序列的渐近增长通常由实际出现的最大模特征根控制。