[【数列】浅谈“不动点”求数列通项的方法](https://www.zhihu.com/tardis/zm/art/104544760)

一、不动点的概念与性质

对于函数 $f(x)$，若存在实数 $x_0$，使得 $f(x_0) = x_0$，则称 $x = x_0$ 是函数 $f(x)$ 的（一阶）不动点。

同样地，若 $f(f(x_0)) = x_0$，则称 $x = x_0$ 是函数 $f(x)$ 的二阶不动点。容易发现，对于一阶不动点 $x = x_0$，有 $f(f(x_0)) = f(x_0) = x_0$，因此一阶不动点必然是二阶不动点。

在几何上，曲线 $y = f(x)$ 与曲线 $y = x$ 的交点的横坐标即为函数 $f(x)$ 的不动点。

一般地，数列 $\{x_n\}$ 的递推式可以由公式 $x_{n+1} = f(x_n)$ 给出，因此可以定义递推数列的不动点：对于递推数列 $\{x_n\}$，若其递推式为 $x_{n+1} = f(x_n)$，且存在实数 $x_0$，使得 $f(x_0) = x_0$，则称 $x_0$ 是数列 $\{x_n\}$ 的不动点。

数列的不动点有什么性质呢？若从某一项 $x_k$ 开始，数列的取值即为 $x_0$，也即 $x_k = x_0$，则 $x_{k+1} = f(x_k) = f(x_0) = x_0$，$x_{k+2} = f(x_{k+1}) = f(x_0) = x_0$，以此类推，根据数学归纳法，可以得到当 $n \geq k$ 时，$x_n = x_0$，也即数列 $\{x_n\}$ 在 $k$ 之后“不动”了。

有时候，数列 $\{x_n\}$ 中的值可能无法取到 $x_0$，但会“接近” $x_0$，也即收敛于 $x_0$。所谓“收敛”是指当 $n$ 充分大时，数列 $\{x_n\}$ 趋向于某个值 $x$，也即 $\lim_{n \to \infty} x_n = x$，代入递推式即可得到 $f(x) = x$。

值得注意的是，不动点也可能不存在（或者说为复数）。文章的最后将会给出一个非常有意思的例子。


二、一阶线性递推数列
所谓“一阶线性递推数列”非常常见，是指下面的这种数列：若数列 $\{x_n\}$ 满足 $x_{n+1} = px_n + q$，其中 $p$，$q$ 是给定的实数，求数列 $\{x_n\}$ 的通项公式。
一般来说，当 $p = 1$ 时，原数列即为公差为 $q$ 的等差数列，故 $x_n = x_1 + (n-1) \cdot q$。
当 $p \ne 1$ 时，我们可以通过待定系数法构造一个公比为 $p$ 的等比数列：假设存在实数 $x_0$，使得 $x_{n+1} - x_0 = p \cdot (x_n - x_0)$，展开得到 $(1-p) \cdot x_0 = q$，解得 $x_0 = \dfrac{q}{1-p}$。
因此数列 $\left\{x_n - \dfrac{q}{1-p}\right\}$ 是等比数列，累乘得 $x_n - \dfrac{q}{1-p} = p^{n-1} \cdot \left(x_1 - \dfrac{q}{1-p}\right)$，移项后即可得到通项公式为
$$x_n = \dfrac{q}{1-p} + p^{n-1} \cdot \left(x_1 - \dfrac{q}{1-p}\right),\text{ 其中 } p \ne 1。$$

事实上，上面得到的 $x_0$ 非常特殊：可以发现 $x_0$ 满足方程 $x_0 = px_0 + q$，也即 $x_0$ 是数列 $\{x_n\}$ 的不动点。这便可以给我们启发：形如 $x_{n+1} = px_n + q$ 的递推数列，在处理的时候可以分以下两种情况：

（1）$p \ne 1$，可以求出它的不动点 $x_0$，之后 $\{x - x_0\}$ 为等比数列；

（2）$p = 1$，此时不动点不存在，$\{x_n\}$ 是等差数列。

并且由上面的例子得到启发，在数列的递推式两边减去不动点，可以得到较为特殊的结构。

接下来来看一个比较简单例子：  
例 1 设数列 $\{a_n\}$ 满足 $a_1=1$，$a_{n+1}=2a_n+1$，求数列 $\{a_n\}$ 的通项公式。  
解 令 $x=2x+1$，解得不动点 $x=-1$，因此变形得到 $a_{n+1}+1=2a_n+2=2(a_n+1)$。  
也即 $\{a_n+1\}$ 是等比数列，且 $a_1+1=2$，累乘得 $a_n+1=2^n$，因此 $a_n=2^n-1$。  

由此看来，不动点法虽然可以说“花里胡哨”的方法，但是在解决问题时比待定系数法直接得多。  

三、分式递推数列  

接下来我们来看分式递推数列，这也是不动点法主要应用的范围。所谓分式递推数列是指以下类型：若数列 $\{x_n\}$ 满足 $x_{n+1}=\dfrac{ax_n+b}{cx_n+d}$，其中 $a$，$b$，$c$，$d$ 是给定的实数，求数列 $\{x_n\}$ 的通项公式。  

这时候要求它的不动点，考虑方程 $x=\dfrac{ax+b}{cx+d}\Leftrightarrow cx^2+(d-a)x-b=0$，得到了一个二次方程！情况就比上面的题目复杂得多了。  

我们从几个例子出发：

例 2 设数列 $\{a_n\}$ 满足 $a_1=2$，$a_{n+1}=\dfrac{5a_n-1}{a_n+3}$，求数列 $\{a_n\}$ 的通项公式。
考虑方程 $x=\dfrac{5x-1}{x+3}\Leftrightarrow (x-1)^2=0$，故 $1$ 是数列 $\{a_n\}$ 的不动点，根据上面的思路，尝试在递推式两边同时减去 $1$，得到
$$a_{n+1}-1=\dfrac{5a_n-1}{a_n+3}-1=\dfrac{4(a_n-1)}{a_n+3}。$$
注意到左右两边分别出现了 $a_{n+1}-1$ 和 $a_n-1$ 这样相似的结构，并且都是在分母，我们可以尝试构造新数列 $\{a_n-1\}$，当然也可以直接变形：
$$
a_{n+1}-1=\dfrac{4(a_n-1)}{a_n+3}\Leftrightarrow \dfrac{1}{a_{n+1}-1}=\dfrac{a_n+3}{4(a_n-1)}=\dfrac{a_n-1+4}{4(a_n-1)}=\dfrac{1}{a_n-1}+\dfrac{1}{4}$$
也即 $\dfrac{1}{a_{n+1}-1}=\dfrac{1}{a_n-1}+\dfrac{1}{4}$，因此数列 $\left\{\dfrac{1}{a_n-1}\right\}$ 是首项为 $1$，公差为 $\dfrac{1}{4}$ 的等差数列，累加得 $\dfrac{1}{a_n-1}=\dfrac{1}{4}\cdot(n+3)$，因此 $a_n=\dfrac{4}{n+3}+1=\dfrac{n+7}{n+3}$。

例 3 设数列 $\{a_n\}$ 满足 $a_1=3$，$a_{n+1}=\frac{4a_n-2}{a_n+1}$，求数列 $\{a_n\}$ 的通项公式。
同样地，考虑方程 $\frac{4x-2}{x+1}=x \Leftrightarrow (x-1)(x-2)=0$，这时假数列 $\{a_n\}$ 有两个不动点 $1$ 和 $2$，分别在递推式两边减去 $1$ 和 $2$ 后，可以得到：
$$a_{n+1}-1=\frac{4a_n-2}{a_n+1}-1=\frac{3(a_n-1)}{a_n+1}\ ,\quad a_{n+1}-2=\frac{4a_n-2}{a_n+1}-2=\frac{2(a_n-2)}{a_n+1}\ .$$
两式相除得 $\frac{a_{n+1}-1}{a_{n+1}-2}=\frac{3}{2}\cdot\frac{a_n-1}{a_n-2}$，因此数列 $\left\{\frac{a_n-1}{a_n-2}\right\}$ 是首项为 $2$，公比为 $\frac{3}{2}$ 的等比数列，累乘得 $\frac{a_n-1}{a_n-2}=2\cdot\left(\frac{3}{2}\right)^{n-1}$，因此 $a_n=\frac{8\cdot 3^n-3\cdot 2^n}{4\cdot 3^n-3\cdot 2^n}$。

做一个小小的总结：形如 $x_{n+1}=\frac{ax_n+b}{cx_n+d}$ 的递推数列，处理时也可以分两种情况：

（1）若其有一个不动点 $x_0$，则 $\left\{\frac{1}{x-x_0}\right\}$ 是等差数列；

（2）若其有两个不动点 $\alpha$，$\beta$，则 $\left\{\frac{x_n-\alpha}{x_n-\beta}\right\}$ 是等比数列。

例 4 设数列 $\{a_n\}$ 满足 $a_1 = 2$，$a_{n+1} = \frac{1}{2} \cdot (a_n + \frac{1}{a_n})$，求求数列 $\{a_n\}$ 的通项公式。

事实上，$a_{n+1} = \frac{1}{2} \cdot (a_n + \frac{1}{a_n}) = \frac{a_n^2 + 1}{2a_n}$，这不同于上面的类型，但是否可以用同样的方法处理呢？

同样尝试求它的不动点：$x = \frac{1}{2} \cdot (x + \frac{1}{x}) \Leftrightarrow (x - 1)(x + 1) = 0$，因此 $1$ 和 $-1$ 是数列 $\{a_n\}$ 的两个不动点，变形得到：

$a_{n+1} - 1 = \frac{a_n^2 + 1}{2a_n} - 1 = \frac{(a_n - 1)^2}{2a_n}$，$a_{n+1} + 1 = \frac{a_n^2 + 1}{2a_n} + 1 = \frac{(a_n + 1)^2}{2a_n}$。

两式相除得 $\frac{a_{n+1} + 1}{a_{n+1} - 1} = (\frac{a_n + 1}{a_n - 1})^2$，又 $\frac{a_1 + 1}{a_1 - 1} = 3$，迭代得到 $\frac{a_{n+1} + 1}{a_{n+1} - 1} = 3^{2^n}$，由此解得数列的通项公式 $a_n = \frac{3^{2^{n-1}} + 1}{3^{2^{n-1}} - 1}$。

由此看来，对于比较复杂的分式型递推数列，也可以通过减去不动点来进行代数变形，从而使等式的两边出现类似的结构，更易于处理。


四、没有不动点的情况？

其实我觉得吧，这里才是这篇文章比较精彩的地方。这就是我在开头讲的，比较有意思的不动点不存在的情况。

例 5 设数列 $\{a_n\}$ 满足 $a_1 = 2$， $a_{n+1} = \frac{1}{2} \cdot (a_n - \frac{1}{a_n})$，求数列 $\{a_n\}$ 的通项公式。

考虑方程 $x = \frac{1}{2} \cdot (x - \frac{1}{x}) \Leftrightarrow x^2 + 1 = 0$，这时候数列的不动点不存在！

但将不动点扩展到复数域内，可以得到 $i$ 与 $-i$ 是数列 $\{a_n\}$ 的两个不动点，接下来根据复数的四则运算，我们看看能得到上面结果：

$a_{n+1} - i = \frac{a_n^2 - 1}{2a_n} - i = \frac{a_n^2 - 2i a_n - 1}{2a_n} = \frac{(a_n - i)^2}{2a_n}$， $a_{n+1} + i = \frac{a_n^2 - 1}{2a_n} + i = \frac{a_n^2 + 2i a_n - 1}{2a_n} = \frac{(a_n + i)^2}{2a_n}$。

两式相除得 $\frac{a_{n+1} + i}{a_{n+1} - i} = (\frac{a_n + i}{a_n - i})^2$，又 $\frac{a_1 + i}{a_1 - i} = \frac{2 + i}{2 - i} = \frac{3}{5} + \frac{4}{5}i$，迭代得 $\frac{a_{n+1} + i}{a_{n+1} - i} = (\frac{3}{5} + \frac{4}{5}i)^{2^n}$，由此解得

$a_n = i \cdot \frac{(3 + 4i)^{2^{n-1}} + 5^{2^{n-1}}}{(3 + 4i)^{2^{n-1}} - 5^{2^{n-1}}}$，并且根据上面的递推公式可以知道，数列的通项公式虽然由复数给出，但是每一项都是实数。

当然，这道题目还有一种比较漂亮的做法：注意到 $\tan 2\theta = \frac{2\tan\theta}{1 - \tan^2\theta}$，根据 $\cot\theta = \frac{1}{\tan\theta}$ 变形即可得到

$\cot 2\theta = \frac{1}{2} \cdot (\cot\theta - \frac{1}{\cot\theta})$。

因此作换元 $a_n = \cot \theta_n$，整理得到 $\theta_{n+1} = 2\theta_n$，故此 $\{\theta_n\}$ 是等比数列，又根据 $a_1 = 2$ 得到 $\theta_1 = \arctan \frac{1}{2}$，故 $\theta_n = \arctan \frac{1}{2} \cdot 2^{n-1}$，因此 $a_n = \cot(\arctan \frac{1}{2} \cdot 2^{n-1})$。

通过这个例子也可以看出“三角复数不分家”。

当不动点是复数的时候，数列可以是周期数列，例如上面的这个例子。

例 6 设数列 $\{a_n\}$ 满足 $a_1 = \frac{1}{2}$，$a_{n+1} = \frac{1 + a_n}{1 - a_n}$，求数列 $\{a_n\}$ 的通项公式。

其中 $a_{n+1} = \frac{1 + a_n}{1 - a_n} = \frac{1 + \frac{1 + a_{n-1}}{1 - a_{n-1}}}{1 - \frac{1 + a_{n-1}}{1 - a_{n-1}}} = -\frac{1}{a_{n-1}} = a_{n-3}$，因此数列以 4 为周期。

考虑方程 $x = \frac{1 + x}{1 - x} \Leftrightarrow x^2 + 1 = 0$，此时数列也没有不动点（或者说不动点为复数）。

另外，关于周期数列的情况，时隔好几年，我在另外一个问题下面的回答下给出了严格的证明。