一阶递推与换元

递推换元的选择顺序

先看相邻项如何连接，再决定变换：差 $a_{n+1}-a_n$ 只含 $n$ 时累加；比 $a_{n+1}/a_n$ 只含 $n$ 且各项非零时累乘；$a_{n+1}=pa_n+q$ 时平移到不动点；分母含 $a_n$ 的简单分式可尝试取倒数；$a_{n+2}$ 只与 $a_n$ 相连时先分奇偶。

例如 $a_1=2,a_{n+1}-a_n=2n+1$，累加 $n-1$ 个等式得 $a_n=2+\sum_{k=1}^{n-1}(2k+1)=n^2+1$。若 $a_1=3,a_{n+1}/a_n=(n+1)/n$，连乘得 $a_n=3n$。前者可以有零项；后者必须先确认比值有定义。

为什么平移到不动点

对 $a_{n+1}=pa_n+q$，希望将常数项吸收到一个固定中心 $\alpha$ 中。要求

比较常数项就得到 $\alpha=p\alpha+q$。所以 $p\ne1$ 时取 $\alpha=q/(1-p)$。平移后的数列满足倍乘关系，完整通项及 $p=0,1$ 的处理见下方“累加、累乘与一阶线性递推”。

这个选择有明确目的：使递推只描述相对于平衡值的变化。一般非线性递推即使存在不动点，减去它后也未必成为等比数列；须实际变形检查。

累加、累乘与一阶线性递推的三种解法

对 $n\ge1$，若 $a_{n+1}=a_n+F(n)$，逐个相加消去中间项，得到

若 $a_{n+1}=a_nF(n)$，逐次代入得

空和取0、空积取1，故两式也覆盖 $n=1$。乘积公式不要求各项非零；但把它写成比值连乘就必须先排除零项。

对 $a_{n+1}=pa_n+q$：若 $p=1$，累加得 $a_n=a_1+(n-1)q$；若 $p\ne1$，令 $b_n=a_n+q/(p-1)$，则 $b_{n+1}=pb_n$，因而

$p=0$ 时直接解释为 $a_n=q$（$n\ge2$）并保留首项；不必使用含 $0^0$ 的记号。$q=0$ 时回到倍乘递推。$b_n$ 可能全零，此时倍乘等式仍成立。

对于 $a_{n+1}=pa_n+F(n)$、$p\ne0$，除以 $p^{n+1}$，令 $b_n=a_n/p^n$，得到 $b_{n+1}-b_n=F(n)/p^{n+1}$。累加后

这是第二种归一化解法。$p=0$ 另有 $a_{n+1}=F(n)$。

第三种为待定系数：若 $F$ 为 $d$ 次多项式且 $p\ne1$，设同次多项式 $g(n)$，使

从最高次系数开始逐次比较：最高次项的系数乘 $1-p\ne0$，可唯一解出；往低次依次解出余下系数。于是 $a_n+g(n)$ 满足倍乘递推。这既说明为何可设同次，也说明 $p=1$ 时不能照用这个次数判断，应改为累加求和。

变系数归一化与消元

把乘数吸收到归一化因子中

设 $a_{n+1}=p_n a_n+q_n$，且各 $p_n\ne0$。令 $P_1=1$、$P_n=\prod_{j=1}^{n-1}p_j$，则 $P_{n+1}=p_nP_n$。除以 $P_{n+1}$ 得

从 $1$ 累加到 $n-1$，得到

例如 $p_n=n+1$ 时 $P_n=n!$，正是将递推除以阶乘的依据。若某个 $p_n=0$，该步直接给出 $a_{n+1}=q_n$；应从这个新初值重新处理后续区段，不能除以为零的连乘积。

作差消去常量，或消去部分和

若递推含同一个未知常量 $c$，可把相邻两个等式相减消去 $c$。但差分后的关系可能丢失原首个等式，恢复通项时必须保留它。例如 $a_{n+1}=pa_n+c$ 作差后得到

这只能说明 $a_{n+1}-pa_n$ 是某个常量；要保证恰为原来的 $c$，还须使用 $a_2-pa_1=c$。

当 $S_n$ 与 $a_n$ 同时出现时，可利用 $a_n=S_n-S_{n-1}$（$n\ge2$）消去 $a_n$，或者将含 $S_n$ 的关系与前一项相减，利用 $S_n-S_{n-1}=a_n$ 消去 $S_n$。两种办法都应单独保留 $S_1=a_1$；若约定 $S_0=0$，仍要检查原递推是否允许在 $n=1$ 使用。消元后还需把结果代回原关系，排除差分引入的额外常量。

分式线性递推：两个不动点的换元

设 $f(x)=(Ax+B)/(Cx+D)$，$C\ne0$，$AD-BC\ne0$。数列满足 $a_{n+1}=f(a_n)$，每一步须有 $Ca_n+D\ne0$。不动点是满足 $f(x)=x$ 的数，即方程

的根；在行列式非零的条件下，该方程的根不会使 $Cx+D=0$。

设有两个不同不动点 $\alpha,\beta$。由 $B-D\alpha=-\alpha(A-C\alpha)$ 得

对 $\beta$ 写出相同形式并相除，得到

这里 $A-C\beta\ne0$，否则由不动点等式将推出 $AD-BC=0$。若初值为任一不动点，原数列恒定；除此之外，令 $u_n=(a_n-\alpha)/(a_n-\beta)$，则

反解要求 $u_n\ne1$。若某项使反解分母或原递推分母为零，所求实数数列只能定义到此前，不能把形式通项当成无限数列。

重不动点的换元另见递推换元。非实不动点也可在复数范围内作同样变换，但周期须检查乘子 $\lambda$ 是否为单位根及所有项是否有定义，不能只凭“不动点为复数”判断周期。