线性递推

线性递推把最近的若干项当作有限窗口。每向前一步，按指定系数混合窗口里的数，再加上外部输入 $g(n)$。常系数意味着每一步使用同一套混合规则；齐次意味着没有额外输入。

齐次解可以线性叠加，这是“线性”的直接后果。若 $u_n,v_n$ 都满足同一个齐次递推，那么 $A{u}_n+B{v}_n$ 也满足。非齐次方程的两个解相减会消去 $g(n)$，所以其解集是“一个特解加上全部齐次解”。

特征根为什么出现 ​

对常系数齐次递推试代 $a_n=r^n$，移位变成乘以 $r$，得到

若 $c_k\ne 0$，且 $p$ 在复数域分解为非零根 $r_i$，重数为 $m_i$，通解由 $n^j{r}_i^n$（$0\le j<m_i$）的线性组合组成。不同根的模式和重根的多项式因子合计提供 $k$ 个参数，再由初值确定。重根不能只保留一个 $r_i^n$，否则参数不够。

先求模式，再代初值 ​

Fibonacci 递推 $F_{n+2}=F_{n+1}+F_n$ 的根是 $\varphi =(1+\sqrt{5})/2$ 与 $\psi =(1-\sqrt{5})/2$。写成 $F_n=A{\varphi }^n+B{\psi }^n$ 后，初值 $F_0=0,F_1=1$ 给出 $A+B=0$、$A\varphi +B\psi =1$，故

这里无理数表达式仍给出整数，因为它与整数初值下的递推解完全相同；验证初值和递推，再用唯一性即可，不必逐项猜测根号如何抵消。

对于 $a_{n+2}-2a_{n+1}+a_n=0$，也可以不求根：改写成 $a_{n+2}-a_{n+1}=a_{n+1}-a_n$，可知相邻差恒定。因此初值 $a_0=2,a_1=5$ 给出 $a_n=2+3n$。它具体展示了重根 $1$ 对应的 $1,n$ 两种模式。

“线性”不等于“常系数” ​

阶乘满足 $a_n=n{a}_{n-1}$、$a_0=1$，是变系数齐次线性递推。不能把 $n$ 当成固定常数求一张特征方程。递推 $a_n=a_{n-1}^2+1$ 则是非线性的；系数是否常数与未知项是否平方是两回事。

若关系写成 $b(n)a_n=\cdots$，在一般环中未必能除以 $b(n)$。例如整数上 $2a_n=a_{n-1}$ 不一定允许整数后继；显式递推的唯一性不能不加条件地推广给这种隐式方程。

常系数齐次递推的普通生成函数理路普通生成函数Ordinary generating function把序列编码为形式幂级数 Σ a_n x^n。是有理函数。令 $A(x)=\sum _{n\ge 0}{a}_n{x}^n$，逐项消去递推尾部便得

其中 $P$ 只由前 $k$ 项决定，次数小于 $k$。反过来，在分母常数项可逆时，比较有理生成函数的系数得到最终成立的常系数齐次递推。这个结论不适用于任意变系数或任意非齐次递推。 非齐次项的生成函数也参与右端，不能忽略。

把 $k$ 个连续项写成列向量，常系数齐次递推就成为固定矩阵理路矩阵Matrix以有限行列集合为索引、取值于半环，并以中间指标求和定义乘法的函数。的反复作用。矩阵快速幂适合直接求远处某一项；逐项递推适合需要全部前缀的场景。增长率取决于初值实际激活的特征根，最大模根的系数可能恰为零。

如果只给序列值而没有递推系数，Prony重构理路Prony 有限幂和重构Prony finite-sum reconstruction · Classical Prony method · 普罗尼方法在不同节点与非零振幅的精确有限幂和模型中，从两倍阶数的连续样本恢复湮灭递推、节点和权重，并核清模型、重根及噪声边界。在已知阶数、不同节点和非零振幅的准确幂和合同下，用 $2r$ 个连续值解Hankel系统，恢复湮灭多项式与权重。它必须区分从 $k=0$ 开始的完整关系与只在尾部成立的递推：零节点只影响第一项，删掉开头可能降低可见阶数；有限段拟合也不自动证明未知尾部继续服从该关系。