1 基本定义
线性递推是描述序列演化的一类递推关系。它的核心特征在于：某一项可以由前若干项经过线性运算得到，因此常被用来刻画具有“记忆性”的离散过程。与一般递推相比，线性递推更便于代数化处理，也更容易借助方程、矩阵和生成函数等工具求解。
1.1 递推关系的概念
递推关系是指用序列已有的若干项来定义后续项的关系式。若一个序列的每一项都能通过前面有限多个项计算出来，则称该序列满足递推关系。递推关系常见于数列定义、组合计数以及离散过程建模。
递推关系的特点是“由前推后”。它与显式公式不同，后者直接给出第 n 项的表达，而递推式强调项与项之间的依赖结构。很多数列一开始只给出少数初值，再由递推式延展整个序列。
1.2 线性递推的形式
线性递推是递推关系中的重要类型。所谓“线性”，是指未知项及其前导项只以一次幂出现，并通过加法和数乘组合，不涉及乘积、平方或其他非线性运算。
一般而言，线性递推可写成若干前项的线性组合，有时还允许加入一个与序列无关的外部项，用来描述外力、输入或偏置。
1.2.1 齐次线性递推
若递推式右侧只由前项的线性组合构成，不含额外独立项，则称为齐次线性递推。其一般形式可以写为 a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k}。
这里的系数 c_1, c_2, ..., c_k 可以是常数，也可以随 n 变化。齐次线性递推常用于描述没有外部输入的系统演化。
1.2.2 非齐次线性递推
若递推式除前项线性组合外，还含有独立的附加项，则称为非齐次线性递推。其形式可写为 a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k} + f(n)。
其中 f(n) 表示外部驱动或补充项。非齐次递推在实际模型中非常常见，例如带常量增量、外部输入或边界补偿的离散系统。
1.3 阶数与初值
递推关系中依赖前多少项，称为递推的阶数。若每一项由前 k 项确定，则称为 k 阶递推。阶数越高，通常需要越多的初值才能唯一确定整个序列。
初值是递推起点所需提供的已知项。对于 k 阶递推，一般需要给出 k 个相邻初值。初值与递推式共同决定序列的具体形态；缺少初值时，递推关系往往只能描述一族解，而不能确定唯一序列。
1.4 常系数与变系数
当递推式中的系数与 n 无关时，称为常系数线性递推。常系数情形结构稳定，便于使用特征方程法、矩阵对角化法等工具，是最经典也最常见的类别。
若系数随着项号变化，则称为变系数线性递推。变系数递推更具一般性，能够描述参数随时间变化的过程，但求解通常更复杂，常需借助特殊技巧或数值方法。
2 典型表示方法
线性递推除了原始递推式之外，还常用若干等价或近似等价的写法表达。不同表示方式有助于突出其结构、便于计算，或与其他数学工具衔接。
2.1 一般表达式
n 阶线性递推的常见一般表达式为 a_n = c_1(n)a_{n-1} + c_2(n)a_{n-2} + ... + c_k(n)a_{n-k} + f(n)。
若系数为常数，则可简写为 a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k} + f(n)。
这种写法清晰地展示了当前项与前若干项之间的线性依赖关系。
2.2 标准化写法
在具体研究中，常将递推式移到同一侧，写成 a_n - c_1 a_{n-1} - c_2 a_{n-2} - ... - c_k a_{n-k} = f(n)。
若 f(n)=0，则得到齐次形式。标准化写法便于统一处理，也方便与特征多项式、线性算子等概念对应。
2.3 递推矩阵形式
许多高阶递推可以改写成矩阵形式，把多个历史状态合并到一个向量中，再通过矩阵乘法描述序列推进。这种方式特别适合计算机实现，也便于研究整体动态。
2.3.1 状态向量表示
定义状态向量 v_n = [a_n, a_{n-1}, ..., a_{n-k+1}]^T。
这样，递推过程就不再只关注单个数列项，而是关注包含若干历史信息的状态。状态向量可以把高阶递推转化为一阶向量递推。
2.3.2 转移矩阵表示
若存在矩阵 M，使得 v_{n+1} = M v_n， 则称 M 为转移矩阵。对常系数线性递推而言，转移矩阵通常由递推系数构造而成。迭代多次后可得 v_n = M^{n-n_0} v_{n_0}， 从而把求第 n 项的问题转化为矩阵幂计算。
3 求解方法
线性递推的求解目标通常是得到闭式表达、分析增长趋势，或高效计算某一项。不同方法适用于不同形式的递推式，常见技巧之间也可以相互配合。
3.1 逐项迭代法
逐项迭代法是最直接的解法，即根据递推式从初值开始逐步计算后续各项。它思路简单，适合求前若干项或验证规律，但当 n 很大时效率较低。
这种方法常用于发现序列模式、检验猜想，或作为其他求解方法的辅助步骤。对于低阶、结构简单的递推，逐项展开有时还能手工归纳出显式公式。
3.2 特征方程法
特征方程法是常系数齐次线性递推的经典工具。其核心思想是设解具有指数型形式 a_n = r^n，然后将其代入递推式，转化为关于 r 的代数方程。
3.2.1 特征根的求取
对齐次常系数递推式代入 a_n=r^n 后，可得到一个关于 r 的多项式方程，称为特征方程。其根称为特征根。若不同特征根互异，则解通常是若干指数项的线性组合。
3.2.2 重根情形
当特征方程存在重根时，解的形式会相应调整。若根 r 的重数为 m，则对应部分解通常包含 r^n, n r^n, n^2 r^n, ..., n^{m-1} r^n。
这反映了重根导致的线性无关解数量增加，类似于连续情形中重特征值的处理方式。
3.2.3 复根情形
当特征方程出现复根时，解可以写成复指数形式，进一步可化为实数形式的振荡解。若复根为 ρe^{±iθ}，则对应的实解常表示为 ρ^n (A cos nθ + B sin nθ)。
这类解常用于描述带有周期波动或振荡特征的离散系统。
3.3 生成函数法
生成函数法把序列编码为一个形式幂级数，通过代数运算将递推关系转化为函数方程。对于常系数递推，生成函数往往能直接导出闭式表达或部分分式分解结果。
该方法的优势在于适用范围广，既能处理齐次形式，也能处理许多非齐次情形。它特别适合组合计数问题，因为许多计数对象天然对应生成函数。
3.4 矩阵对角化法
若递推可表示为矩阵迭代，并且转移矩阵可对角化，则可借助相似变换把矩阵幂化为更易计算的形式。设 M = PDP^{-1}，则 M^n = P D^n P^{-1}。
由于 D 是对角矩阵，其幂次计算非常简单，因此可有效得到递推的显式解。该方法与特征方程法在本质上密切相关。
3.5 待定系数法
待定系数法常用于求解特定形式的非齐次线性递推。做法是先求齐次方程的通解，再根据非齐次项的类型猜测一个特解形式，并代入确定未知系数。
该方法尤其适用于非齐次项为多项式、指数函数、三角函数或其组合的情形。它操作简洁，常见于手工推导和竞赛题解中。
4 解的性质
线性递推不仅关心如何求解，也关心解本身具备的结构性质。这些性质有助于理解序列的可分解性、稳定性以及长期行为。
4.1 线性叠加性质
对于齐次线性递推，如果 a_n 和 b_n 都是解，那么它们的任意线性组合 αa_n + βb_n 仍然是解。这个性质称为线性叠加性质。
叠加性说明解空间具有线性结构，因此可通过寻找一组基解来构造全部解。这也是特征方程法和矩阵法得以成立的重要基础。
4.2 解的唯一性
在给定递推式和足够初值的条件下，线性递推通常对应唯一解。也就是说，一旦初值数量与阶数匹配，并且递推关系在每一步都可正常求出下一项，那么整个序列便被唯一确定。
唯一性使递推系统具有良好的可预测性。若初值不足，则一般会出现多解；若递推式退化，可能还会出现不能向前推进的情况。
4.3 解的稳定性
稳定性描述的是初值或参数发生微小变化时，解的响应情况。对于某些线性递推，误差会逐步放大，导致序列偏离明显；而在另一些情形中，扰动会逐渐衰减，序列趋于平稳。
稳定性与特征根大小密切相关。若主导特征根的模较大，序列增长较快，误差也可能被放大；若主导根模较小，则序列往往更稳定。
4.4 渐近增长行为
渐近增长行为关注 n 很大时序列的整体趋势。线性递推的长期增长通常由模最大的特征根主导。若存在多个同阶主导项，还需考虑它们的相互叠加。
这类分析在估计数列规模、复杂度上界以及组合对象数量时非常重要。即使无法得到完全闭式表达，仍可通过渐近形式把握主要增长速度。
5 常见实例
许多著名数列都可以看作线性递推的典型例子。它们既具有代表性，也常作为教学和应用中的标准模型。
5.1 Fibonacci 数列
Fibonacci 数列满足 F_n = F_{n-1} + F_{n-2}。
配合初值即可唯一确定整个序列。它是二阶齐次常系数线性递推的经典例子，在组合计数、树结构和算法分析中都非常常见。
5.2 Lucas 数列
Lucas 数列与 Fibonacci 数列有类似的递推结构，同样满足 L_n = L_{n-1} + L_{n-2}， 但初值不同，因此得到另一组序列。它与 Fibonacci 数列在许多性质上相近，常被并列讨论。
5.3 等差与等比型递推
等差数列可看作一阶非齐次递推，例如 a_n = a_{n-1} + d。 等比数列则对应一阶齐次递推，例如 a_n = q a_{n-1}。
这说明常见初等数列本身就可纳入线性递推框架，形式简单而直观。
5.4 计数问题中的递推
在组合数学中，线性递推经常来源于对对象进行分类计数。根据最后一步、最后一位或局部结构的不同情况，可以建立关于总数的递推式。
5.4.1 台阶走法问题
台阶走法问题通常询问：从起点走到第 n 级台阶，有多少种走法。若每次可走一阶或两阶，则方案数满足 Fibonacci 型递推。通过按最后一步分类，可以自然得到递推关系。
5.4.2 二叉树计数问题
二叉树计数常与递推结构密切相关。根据根节点左右子树的规模分配，可以导出有关树的数量、形态或路径数目的递推式。此类问题中，递推往往反映了“分治式”结构。
5.4.3 字符串与排列计数
在字符串匹配、禁止子串计数或特定排列统计中，状态往往取决于前一个或前几个位置的情况。通过划分末尾字符类别或局部状态，可以建立线性递推来描述合法方案数。
6 相关工具与理论
线性递推的研究通常离不开一组配套工具。这些工具既帮助建立模型，也帮助完成求解与分类。
6.1 生成函数基础
生成函数是把数列表示为幂级数的方法。给定序列 a_n，可构造 A(x) = Σ a_n x^n。
通过对幂级数进行平移、乘法和分解，递推关系可转换为代数方程，从而使求解变得系统化。生成函数在组合学中特别常用。
6.2 特征多项式
对于常系数齐次递推，特征多项式由递推系数组成，其根决定通解的基本形态。它是判断解结构、重根情况和增长趋势的关键对象。
特征多项式也把递推问题转化为多项式求根问题，便于与代数方法连接。不同根的重数与模长会直接影响解的表达和长期行为。
6.3 差分方程
线性递推可看作离散时间上的差分方程。差分方程研究的是变量在相邻离散点之间的变化关系，与连续情形中的微分方程相对应。
这一对应关系使线性递推能够借用不少分析思想，例如平稳解、特解、初值问题和渐近分析等。对于离散系统建模，差分方程是重要基础。
6.4 线性代数方法
线性代数为递推提供了统一的向量与矩阵语言。通过把高阶递推转化为一阶向量系统，可以利用矩阵运算、特征值分解和相似变换进行处理。
6.4.1 向量空间观点
从向量空间角度看，线性递推的解集通常构成一个线性空间，齐次方程的解可进行线性组合。初值则相当于选择了空间中的一个具体向量，从而确定唯一轨道。
6.4.2 Jordan 标准形
当转移矩阵不能完全对角化时，可使用 Jordan 标准形进行分析。该方法把矩阵分解为若干 Jordan 块，从而处理重特征值或不可对角化情形。
Jordan 标准形与重根特征方程之间具有对应关系。它不仅可给出解的结构，还能说明为什么会出现多项式因子与指数项的乘积形式。
7 应用领域
线性递推在许多离散问题中都十分实用。它既是理论分析工具，也是算法设计和系统建模中的基础方法。
7.1 算法分析
在算法分析中，很多运行时间和空间占用都可写成递推式。例如分治算法常产生 T(n)=2T(n/2)+f(n) 一类关系。通过求解递推式，可以估计算法的复杂度增长。
线性递推在这里起到桥梁作用，将程序步骤与数学结构联系起来，便于比较不同算法的效率。
7.2 组合数学
组合数学中大量计数问题都可通过递推处理。只要能按最后一步、最后元素或局部结构进行分类，就可能建立线性递推式，从而得到总数公式。
这类方法常与生成函数相结合，在求解路径计数、排列限制和结构枚举时尤其有效。
7.3 动态规划建模
动态规划本质上是一类“状态转移”思想，很多状态转移方程都可以视作线性递推。通过把复杂问题拆成相互关联的子问题，再根据最优子结构或计数结构逐步推进，就能建立递推模型。
当状态数量较少且转移线性时，问题往往能写成递推或矩阵形式，便于分析和实现。
7.4 离散系统与信号处理
在线性离散系统中，输出常由前若干时刻的输出与输入线性组合而成，这与线性递推完全一致。因而线性递推也可用于描述滤波、采样后的演化以及离散控制系统的响应。
在信号处理中，这种表达有助于分析系统的稳定性、冲激响应和频率特性，是离散时间模型的重要组成部分。