针对分式递推求数列通项的“不动点法”的代数理解 \(a_{n+1}=\frac{Aa_n+B}{Ca_n+D}\)

“不动点法”的做法是把两边的数列项都代为x，然后求解一个关于x的一元二次方程解得两个根（或者一个重根） \(Cx^2+(D-A)x-B=0\) \(x=x_1,x=x_2\) 然后在原递推关系式两侧同时减去$x_1$或者$x_2$，会发现减完后两边会出现相同的结构$a_{n+1}-x_i$, $a_n-x_i$，这时两个方程相除（如果有两个不同的根）或者对两边取倒数（如果有重根），即可构造出一个等差数列进而求解$a_n$的通项。

以前我一直不太理解为什么这个方法叫“不动点法”，不动点本身应该出现在函数范畴$f(x)=x$，本文将简单地从代数视角揭示其本质。

本质我们在研究一个递推关系 \(a_{n+1}=f(a_n)=\frac{Aa_n+B}{Ca_n+D}\)

假设函数$f$存在不动点$x_0, s.t. \quad f(x_0)=x_0$

则对上式两边同时减去$x_0$，即可得到 \(a_{n+1}-x_0=f(a_n)-x_0\)

考察右手边$g(x)=f(x)-x_0$，注意到$x_0$会是$g(x)$的零点，这时候如果给出一些先验假设，如$g(x)$是多项式函数，或者是有理函数(即两个多项式函数相除的分式形式)，由多项式的根与多项式的关系，必有 \((x-x_0)|g(x)\) 即$g(x)$的表达式中会蕴含$(x-x_0)$这个因式。

以求解数列$a_n$的通项为目的，我们本质是要从递推式中构造等差或者等比，这要求RHS的分子和LHS出现相同的结构如$a_{n+1}-x_i$, $a_n-x_i$, 而减去不动点$x_0$保证了RHS分子上会出现$(a_n-x_0)$这个因式。