递推换元：重不动点、根式与三角形式

换元的目标是把迭代变成平移、倍角或乘法。每次开方、取对数、取倒数之前，都应先证明相应的取值条件。

分式递推的重不动点

设 $f(x)=(Ax+B)/(Cx+D)$ ， $C\ne0,AD-BC\ne0$ ，不动点方程有重根 $\alpha$ 。由 $Cx^2+(D-A)x-B=0$ 的重根条件，得 $A-D=2C\alpha$ ，从而 $A-C\alpha=C\alpha+D\ne0$ 。直接计算

\frac1{f(x)-\alpha}=\frac1{x-\alpha}+\frac C{C\alpha+D}.

所以在迭代各步均有定义、初值不等于 $\alpha$ 时， $1/(a_n-\alpha)$ 为等差数列。初值等于 $\alpha$ 则为常数数列。反解时若出现倒数为零，应检查该步是否已对应原迭代的分母为零，不能把无穷大当作实数列的一项。

设 $a_1=2$ ， $a_{n+1}=(3a_n+1)/(a_n+3)$ 。若 $a_n>1$ ，则 $a_{n+1}-1=2(a_n-1)/(a_n+3)>0$ ；归纳知所有分母正且 $a_n>1$ 。

不动点为 $1,-1$ ，设 $b_n=(a_n-1)/(a_n+1)$ ，得到 $b_{n+1}=b_n/2$ ， $b_1=1/3$ 。故

a_n=\frac{3\cdot2^{n-1}+1}{3\cdot2^{n-1}-1}.

分母对每个 $n\ge1$ 都正，故通项确实给出完整数列。

设 $a_1\in[-2,2]$ ， $a_{n+1}=\sqrt{2+a_n}$ 。取唯一 $\theta\in[0,\pi]$ 使 $a_1=2\cos\theta$ 。由半角公式及 $\cos(\theta/2)\ge0$ ，

a_n=2\cos\frac{\theta}{2^{n-1}}.

归纳验证时，根号 $\sqrt{4\cos^2u}=2|\cos u|$ ，所选角度范围正好允许去掉绝对值。若不控制角度，直接去绝对值可能出错。

若 $a_{n+1}=2a_n^2-1$ ， $a_1=\cos\theta$ ，则由余弦倍角公式归纳得 $a_n=\cos(2^{n-1}\theta)$ 。例如 $\theta=2\pi/3$ 时所有项均为 $-1/2$ 。

这个公式并不说明所有初值都产生周期数列。如果 $a_1=2$ ，数列从区间 $[-1,1]$ 外出发，不能使用实角余弦换元；而且对 $x\ge2$ ， $2x^2-1>x$ ，故数列严格递增、不可能周期。即使有复特征根，也必须检查模长与角度，不能仅凭“复根”断言周期性。

设 $a_1=\pi/6$ ， $a_{n+1}=\arctan(1/\cos a_n)$ ，其中反正切取值于 $(-\pi/2,\pi/2)$ 。归纳可知每项都在 $(0,\pi/2)$ ，所以递推有意义。令 $u_n=\tan^2a_n$ ，则

u_{n+1}=\frac1{\cos^2a_n}=1+u_n,\qquad u_1=\frac13.

因此 $u_n=n-2/3$ ，且

\sin^2a_n=\frac{3n-2}{3n+1},\qquad \prod_{n=1}^m\sin a_n=\frac1{\sqrt{3m+1}}.

最后一步由连乘消去相邻的分子分母并取正平方根得到；若不先确定各角所在区间，就不能从平方积直接断定积为正。

在 $x_n$ 处作 $y=f(x)$ 的切线，令切线上的 $y=0$ ，在 $f'(x_n)\ne0$ 时得到

x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.

这是切线迭代公式；它描述一种构造，不能保证从任意初值出发都接近根。

对 $f(x)=x^2-2$ 、 $x_0=2$ ，公式成为 $x_{n+1}=(x_n+2/x_n)/2$ 。前两步得到 $x_1=3/2,x_2=17/12$ 。且对任何正的 $x_n$ ，

x_{n+1}-\sqrt2=\frac{(x_n-\sqrt2)^2}{2x_n}\ge0.

若 $x_n\ge\sqrt2$ ，还有 $x_{n+1}\le x_n$ ，所以从本例初值出发始终在根的上方递减。这些性质是具体代数证明的结果。

反例取 $f(x)=x^3-2x+2$ ，从 $x_0=0$ 出发依次得到 $x_1=1,x_2=0$ ，此后循环，两个位置的导数均非零。因而“每一步显然更接近根”是不成立的一般断言；若某一步导数为零，公式甚至无法继续使用。

对 $a_{n+1}=a_n/(pa_n+q)$ ，首先要求每个原分母非零。若 $a_n\ne0$ ，令 $b_n=1/a_n$ ，直接取倒数得到

b_{n+1}=qb_n+p.

按一阶线性递推求出 $b_n$ 后再取倒数，同时检查 $b_n\ne0$ 。若首项为零且原递推在零处有定义，则为零常数列，应先单独保留。

对于一般分式 $f(x)=(px+q)/(rx+s)$ ，选择如下：

情形	换元与得到的关系	证明位置
$r=0,s\ne0$	化为一次或常值递推	一阶线性递推
$r\ne0,ps-qr\ne0$ ，不同不动点 $\alpha,\beta$	$u=(x-\alpha)/(x-\beta)$ ，得到 $u_{n+1}=\lambda u_n$ ， $\lambda=(p-r\alpha)/(p-r\beta)$	两个不动点的换元
$r\ne0,ps-qr\ne0$ ，重不动点 $\alpha$	$v=1/(x-\alpha)$ ，得到 $v_{n+1}=v_n+r/(p-r\alpha)$	重不动点的推导

第二、三行中，初值本身为不动点时都应先保留常数列。第二行的 $\beta$ 不能代入换元分母；还原式 $a_n=(u_n\beta-\alpha)/(u_n-1)$ 又要求 $u_n\ne1$ 。第三行还原时须 $v_n\ne0$ 。每一步都要同时检查原递推的分母，形式通项并不自动代表无限实数列。

当 $ps-qr=0$ 且原分母不是零多项式时，分式在其自然定义域内退化为常值。初值合法还不够：若输出的这个常值恰是原分母零点，第二步就无法继续。不能使用上表的可逆分式换元。

一般的一阶递推写成 $a_n=f^{\circ(n-1)}(a_1)$ 。若存在双射 $h:D\to E$ ，使 $f=h^{-1}\circ g\circ h$ ，则

a_n=h^{-1}\bigl(g^{\circ(n-1)}(h(a_1))\bigr).

这个公式来自相邻 $h\circ h^{-1}$ 的抵消，完整证明见桥函数。把不动点送到零往往便于识别倍乘关系，但仅有 $h(\alpha)=0$ 并不保证变换后一定简单。