方法简述

对于递推数列 ，满足

若存在 满足 ，则

上式会有比较好的性质。

example

例如，若

由于 的解为 ，在等式两侧同时减 ：

这里 为等比数列。

原理

对于不动点简化递推，这里引入两种解释。

你可以发现这些解释都是有局限性的，这是因为不动点法本身也不能解决所有问题。

解释 1

对于常见的递推式 ，递推函数 一般为分式函数。不妨令 ，这里 和 为多项式函数。

若 存在不动点 ，即 ，则 存在零点 ，这意味着 必定存在因式 。

因此可以作换元 。

解释 2

首先，对于递推数列

求其通项 的过程实际上就是在求 。

对于递推函数 ，考虑作换元 ，令 为 的递推函数，则

或者写作

注意到

这就是迭代在换元下的表达。

我们将 和 这种由换元联系起来的函数叫做相似函数。

对于函数 和 ，若存在 及其反函数 ，使得 ，就称 和 通过 相似，称 为桥函数，记作 。

已经证明，若 ，则 。

并且，若 为 的不动点，则 ，即 ，即 为 的不动点，因此 的不动点与 的不动点一一对应。

由于相似函数之间紧密的联系，我们可以通过换元将一个函数转化为易于求解的相似函数。

而不动点正可以被利用构造简单的 。

不加定义地引入 及其运算，我们有 （等差型）的不动点为 和 （等比型）的不动点为 。

一般地，

• 若函数 有一个不动点 ，作换元 ，则 的不动点为 ，恰好为等差型的不动点；
• 若函数 有两个不动点 ，作换元 ，则 的不动点为 ，恰好为等比型的不动点。