不动点

hbghlyj

不动点法求数列通项

定义:方程$f(x)=x$的根称为函数$f(x)$的不动点.

$f(x)$的不动点,可将某些递推关系$a_{n}=f\left(a_{n-1}\right)$所确定的数列化为等比数列或较易求通项的数列,这种方法称为不动点法.
定理1:若 $f(x)=a x+b(a \neq 0, a \neq 1)$,$p$是$f(x)$的不动点, $a_{n}$满足递推关系$a_{n}=f\left(a_{n-1}\right),(n>1)$,则$a_{n}-p=a\left(a_{n-1}-p\right)$,即$\left\{a_{n}-p\right\}$是公比为$a$的等比数列.
证明:因为$p$是$f(x)$的不动点,$\therefore a p+b=p$, $\therefore b-p=-a p$,由$a_{n}=a \cdot a_{n-1}+b$得$a_{n}-p=a-a_{n-1}+b-p=a\left(a_{n-1}-p\right)$,所以$\left\{a_{n}-p\right\}$是公比为$a$的等比数列.
定理2:设$f(x)=\frac{a x+b}{c x+d}(c \neq 0, a d-b c \neq 0)$,$\left\{a_{n}\right\}$满足递推关系$a_{n}=f\left(a_{n-1}\right), n>1$,初值条件$a_{1} \neq f\left(a_{1}\right)$
(1):若$f(x)$有两个相异的不动点$p,q$,则$\frac{a_{n}-p}{a_{n}-q}=k \cdot \frac{a_{n-1}-p}{a_{n-1}-q}$  (这里$k=\frac{a-p c}{a-q c}$ )
(2):若$f(x)$只有唯一不动点$p$,则$\frac{1}{a_{n}-p}=\frac{1}{a_{n-1}-p}+k$   (这里$k=\frac{2 c}{a+d}$)
证明:由$f(x)=x$得$f(x)=\frac{a x+b}{c x+d}=x$,所以$c x^{2}+(d-a) x-b=0$.
(1)因为$p,q$是不动点,所以$\left\{\begin{array}{l}c p^{2}+(d-a) p-b=0 \\ c q^{2}+(d-a) q-b=0\end{array}\right.$⇒$\left\{\begin{array}{l}p=\frac{p d-b}{a-p c} \\ q=\frac{q d-b}{a-q c}\end{array}\right.$,所以$\frac{a_{n}-p}{a_{n}-q}=\frac{\frac{a a_{n-1}+b}{c a_{n-1}+d}-p}{\frac{a a_{n-1}+b}{c a_{n-1}+d}-q}=\frac{(a-p c) a_{n-1}+b-p d}{(a-q c) a_{n-1}+b-q d}=\frac{a-p c}{a-q c}·\frac{a_{n-1}-\frac{p d-b}{a-p c}}{a_{n-1}-\frac{qd-b}{a-q c}}=\frac{a-p c}{a+q c}·\frac{a_{k-1}-p}{a_{k-1}-q}$
令$k=\frac{a-p c}{a-q c}$,则$\frac{a_{n}-p}{a_{n}-q}=k \frac{a_{n-1}-p}{a_{n-1}-q}$
(2)因为$p$是方程$c x^{2}+(d-a) x-b=0$的唯一解,所以$c p^{2}+(d-a) p-b=0$.
所以$b-p d=c p^{2}-a p$,$p=\frac{a-d}{2 c}$.所以$a_{n}-p=\frac{a a_{n-1}+b}{c a_{n-1}+d}-p=\frac{(a-c p) a_{n-1}+b-p d}{c a_{n-1}+d}=\frac{(a-c p) \cdot a_{n-1}+c p^{2}-a p}{c a_{n-1}+d}=\frac{(a-c p)\left(a_{n-1}-p\right)}{c a_{k-1}+d}$.
所以$\frac{1}{a_{n}-p}=\frac{1}{a-c p} \cdot \frac{c a_{n-1}+d}{a_{n-1}-p}=\frac{1}{a-c p} \cdot \frac{c\left(a_{n-1}-p\right)+d+c p}{a_{n-1}-p}=\frac{c}{a-c p}+\frac{d+c p}{a-c p} \cdot \frac{1}{a_{n-1}-p}=\frac{1}{a_{n-1}-p}+\frac{2 c}{a+d}$.
令$k=\frac{2 c}{a+d}$,则$\frac{1}{a_{n}-p}=\frac{1}{a_{n-1}-p}+k$
例1:设$\left\{a_{n}\right\}$满足$a_{1}=1, a_{n+1}=\frac{a_{n}+2}{a_{n}}, n \in N^{*}$,求数列$\left\{a_{n}\right\}$的通项公式
例2:数列$\left\{a_{n}\right\}$满足下列关系:$a_{1}=2 a, a_{n+1}=2 a-\frac{a^{2}}{a_{n}}, a \neq 0$,求数列$\left\{a_{n}\right\}$的通项公式
定理3:设函数$f(x)=\frac{a x^{2}+b x+c}{e x+f}(a \neq 0, e \neq 0)$有两个不同的不动点$x_{1}, x_{2}$,且由$u_{n+1}=f\left(u_{n}\right)$确定着数列$\left\{u_{n}\right\}$,那么当且仅当$b=0,e=2a$时,$\frac{u_{n+1}-x_{1}}{u_{n+1}-x_{2}}=\left(\frac{u_{n}-x_{1}}{u_{n}-x_{2}}\right)^{2}$
证明: $x_{k}$是$f(x)$的两个不动点,∴$x_{k}=\frac{a x_{k}^{2}+b x_{k}+c}{e x_{k}+f}$,即$c-x_{k} f=(e-a) x_{k}^{2}-b x_{k}\;(k=1,2)$
$\therefore\frac{u_{n+1}-x_{1}}{u_{n+1}-x_{2}}=\frac{a u_{n}^{2}+b u_{n}+c-x_{1}\left(e u_{n}+f\right)}{a u_{n}{ }^{2}+b u_{n}+c-x_{2}\left(e u_{n}+f\right)}=\frac{a u_{n}^{2}+\left(b-e x_{1}\right) u_{n}+c-x_{1} f}{a u_{n}^{2}+\left(b-e x_{1}\right) u_{n}+c-x_{2} f}=\frac{a u_n^{2}+\left(b-e x_{1}\right) u_{n}+(e-a) x_{1}^{2}-b x_{1}}{a u_n^{2}+\left(b-e x_{2}\right) u_{n}+(e-a) x_{2}^{2}-b x_{2}}$
于是$\frac{u_{n+1}-x_{1}}{u_{n+1}-x_{2}}=\left(\frac{u_{n}-x_{1}}{u_{n}-x_{2}}\right)^{2}$
⇔$\frac{a u_{n}^{2}+\left(b-e x_{1}\right) u_{n}+(e-a) x_{1}^{2}-b x_{1}}{a u_{n}^{2}+\left(b-e x_{2}\right) u_{n}+(e-a) x_{2}^{2}-b x_{2}}=\frac{u_{n}^{2}-2 x_{1} u_{n}+x_{1}^{2}}{u_{n}^{2}-2 x_{2} u_{n}+x_{2}^{2}}$
⇔$\frac{u_{n}^{2}+\frac{b-e x_{1}}{a} u_{n}+\frac{(e-a) x_{1}^{2}-b x_{1}}{a}}{u_{n}^{2}+\frac{b-e x_{2}}{a} u_{n}+\frac{(e-a) x_{2}^{2}-b x_{2}}{a}}=\frac{u_{n}^{2}-2 x_{1} u_{n}+x_{1}^{2}}{u_{n}^{2}-2 x_{2} u_{n}+x_{2}^{2}}$
⇔$\left\{\begin{array}{l}\frac{b-e x_{1}}{a}=-2 x_{1} \\ \frac{b-e x_{2}}{a}=-2 x_{2}\end{array}\right.$⇔$\left\{\begin{array}{l}b+(2 a-e) x_{1}=0 \\ b+(2 a-e) x_{2}=0\end{array}\right.$
于是,$\begin{vmatrix}1&x_1\\1&x_2\end{vmatrix}\ne0$,方程组有唯一解$b=0, e=2 a$.
例3:已知数列$\left\{a_{n}\right\}$中,$a_{1}=2, a_{n+1}=\frac{a_{n}^{2}+2}{2 a_{n}}, n \in N^{*}$,求数列$\left\{a_{n}\right\}$的通项.
其实不动点法除了解决上面所考虑的求数列通项的几种情形,还可以解决如下问题:
例4:已知$a_{1}>0, a_{1} \neq 1$且$a_{n+1}=\frac{a_{n}^{4}+6 a_{n}^{2}+1}{4 a_{n}\left(a_{n}^{2}+1\right)}$,求数列$\left\{a_{n}\right\}$的通项.
解:作函数为$f(x)=\frac{x^{4}+6 x^{2}+1}{4 x\left(x^{2}+1\right)}$,解方程 $f(x)=x$得$f(x)$的不动点为$x_{1}=-1, x_{2}=1, x_{3}=-\frac{\sqrt{3}}{3} i, x_{4}=\frac{\sqrt{3}}{3} i$.取$p=1,q=-1$,作如下代换:$\frac{a_{n+1}+1}{a_{n+1}-1}=\frac{\frac{a_{n}^{4}+6 a_{n}^{2}+1}{4 a_{n}\left(a_{n}^{2}+1\right)}+1}{\frac{a_{n}^{4}+6 a_{n}^{2}+1}{4 a_{n}\left(a_{n}^{2}+1\right)}-1}=\frac{a_{n}^{4}+4 a_{n}^{3}+6 a_{n}^{2}+4 a_{n}+1}{a_{n}^{4}-4 a_{n}^{3}+6 a_{n}^{2}-4 a_{n}+1}=\left(\frac{a_{n}+1}{a_{n}-1}\right)^{4}$
逐次迭代后,得: $a_{n}=\frac{\left(a_{1}+1\right)^{4^{n-1}}+\left(a_{1}-1\right)^{4^{n-1}}}{\left(a_{1}+1\right)^{4^{n-1}}-\left(a_{1}-1\right)^{4^{n-1}}}$
已知曲线$C_{n}: x^{2}-2 nx+y^{2}=0(n=1,2, \ldots)$.从点$P(-1,0)$向曲线$C_{n}$引斜率为$k_{n}\left(k_{n}>0\right)$的切线 $l_{n}$,切点为$P_{n}\left(x_{n}, y_{n}\right)$．
(１)求数列$\left\{x_{n}\right\}$与$\left\{y_{n}\right\}$的通项公式;
(２)证明:$x_{1} \cdot x_{3}·x_{5} \cdots x_{2 n-1}<\sqrt{\frac{1-x_{n}}{1+x_{n}}}<\sqrt{2} \sin \frac{x_{n}}{y_{n}}$
设$p,q$为实数,$α,β$是方程$x^{2}-p x+q=0$的两个实根,数列$\{x_n\}$满足$x_{1}=p$,\(x_{2} = p^{2} - q\),\(x_{n} = px_{n - 1} - qx_{n - 2}\),$x_{n}=p x_{n-1}-q x_{n-2}$($n=3,4,⋯$)．(1)证明:\(\alpha + \beta = p\),\(\alpha\beta = q\);(2)求数列\(\{x_n\}\)的通项公式;(3)若\(p = 1\),\(q = \frac{1}{4}\),求\(\{ x_{n}\}\)的前\(n\)项和\(S_{n}\)．
已知函数\(f(x) = x^{2} + x - 1\),\(\alpha ,\beta\)是方程\(f(x) = 0\)的两个根(\(\alpha > \beta\)), \(f^{'}(x)\)是\(f(x)\)的导数,设\(a_{1} = 1\),$a_{n+1}=a_{n}-\frac{f\left(a_{n}\right)}{f^{\prime}\left(a_{n}\right)}(n=1,2, \cdots)$．
(1)求$\alpha,\beta$的值;
(2)证明:对任意的正整数$n$,都有$a_n\gt\alpha$;
(3)记$b_{n}=\ln \frac{a_{n}-\beta}{a_{n}-\alpha}(n=1,2, \cdots)$,求数列$\{b_n\}$的前$n$项和$S_n$.
13陕西文21．(本小题满分12分)已知数列$\left\{a_{n}\right\}$满足$a_{1}=1, a_{2}=2, a_{n+2}=\frac{a_{n}+a_{n+1}}{2}, n \in N^{*}$.
(I)令$b_{n}=a_{n+1}-a_{n}$,证明:$\left\{b_{n}\right\}$是等比数列;
(Ⅱ)求$\{a_n\}$的通项公式.
山东文20.(本小题满分12分)等比数列$\{a_n\}$的前$n$项和为$S_n$, 已知对任意的$n \in N^{+}$,点$\left(n, S_{n}\right)$均在函数$y=b^{x}+r$($b>0$且$b \neq 1, b, r$均为常数)的图像上.(1)求$r$的值;(2)当b=2时,记$b_{n}=\frac{n+1}{4 a_{n}}\left(n \in N^{+}\right)$.求数列$\left\{b_{n}\right\}$的前$n$项和$T_{n}$

hbghlyj

zhuanlan.zhihu.com/p/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 \rightarrow \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\ne1$ 时，我们可以通过待定系数法构造一个公比为 $p$ 的等比数列：假设存在实数 $x_0$ ，使得 $x_{n+1}-x_0=p\cdot(x_n-x_0)$ ，展开得到 $(1-p)\cdot x_0=q$ ，解得 $x_0=\frac{q}{1-p}$ 。

因此数列 $\{x_n-\frac{q}{1-p}\}$ 是等比数列，累乘得 $x_n-\frac{q}{1-p}=p^{n-1}\cdot(x_1-\frac{q}{1-p})$ ，移项后即可得到通项公式为 $x_n=\frac{q}{1-p}+p^{n-1}\cdot(x_1-\frac{q}{1-p})$ ，其中 $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}=\frac{ax_n+b}{cx_n+d}$ ，其中 $a$ ， $b$ ， $c$ ， $d$ 是给定的实数，求数列 $\{x_n\}$ 的通项公式。

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

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

考虑方程 $x=\frac{5x-1}{x+3}\Leftrightarrow (x-1)^2=0$ ，故 $1$ 是数列 $\{a_n\}$ 的不动点，根据上面的思路，尝试在递推式两边同时减去 $1$ ，得到 $a_{n+1}-1=\frac{5a_n-1}{a_n+3}-1=\frac{4(a_n-1)}{a_n+3}$ 。

注意到左右两边分别出现了 $a_{n+1}-1$ 和 $a_n-1$ 这样相似的结构，并且都是在分母，我们可以尝试构造新数列 $\{a_n-1\}$ ，当然也可以直接变形：

$a_{n+1}-1=\frac{4(a_n-1)}{a_n+3}\Leftrightarrow\frac{1}{a_{n+1}-1}=\frac{a_n+3}{4(a_n-1)}=\frac{a_n-1+4}{4(a_n-1)}=\frac{1}{a_n-1}+\frac{1}{4}$

也即 $\frac{1}{a_{n+1}-1}=\frac{1}{a_n-1}+\frac{1}{4}$ ，因此数列 $\{\frac{1}{a_n-1}\}$ 是首项为 $1$ ，公差为 $\frac{1}{4}$ 的等差数列，累加得 $\frac{1}{a_n-1}=\frac{1}{4}\cdot(n+3)$ ，因此 $a_n=\frac{4}{n+3}+1=\frac{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}$ ， $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}$ ，因此数列 $\{\frac{a_n-1}{a_n-2}\}$ 是首项为 $2$ ，公比为 $\frac{3}{2}$ 的等比数列，累乘得 $\frac{a_n-1}{a_n-2}=2\cdot(\frac{3}{2})^{n-1}$ ，因此 $a_n=\frac{8\cdot3^n-3\cdot2^n}{4\cdot3^n-3\cdot2^n}$ 。

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

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

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

当然，分式递推数列不只有上面那种简单的情况，可以看下面这个例子：

例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-2ia_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+2ia_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}$ 变形即可得到 $\cot2\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}\cdot2^{n-1}$ ，因此 $a_n=\cot(\arctan\frac{1}{2}\cdot2^{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+\dfrac{1+a_{n-1}}{1-a_{n-1}}}{1-\dfrac{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$ ，此时数列也没有不动点（或者说不动点为复数）。

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

如果不动点方程无实数解该怎么办，一定是周期数列吗？170 赞同 · 7 评论回答

大家可以参考~

hbghlyj

不动点定理

• 2 离散数学和理论计算机科学领域
  

λ演算的共同主题是找到给出λ表达式的不动点。每个λ表达式都有一个不动点，不动点组合子是一个“函数”，即输入一个λ表达式并输出该表达式的一个不动点。一个重要的不动点组合是Y 组合子，它使用递归定义。

hbghlyj

不动点定理：在LC和CL中，
对于任意x，存在它的不动点Yx，满足，
Yx -> x(Yx)

其中，
“->”表示LC中的β归约，
或CL中的弱归约。

证明：
取Y ≡ UU
U ≡ λux.x(uux)

Yx ->
UUx ->
(λux.x(uux))Ux ->
(λx.x(UUx))x ->
x(UUx) ->
x(Yx)

hbghlyj

不动点和Y算子

1、不动点理论:

不动点：函数f(x)=x^2.对于某些点，有f(x) = x,这样的点称为不动点。 那么如何计算出函数的不动点？

2、高阶抽象函数的不动点

假定函数f，是阶乘计算函数，f(n)=(f n)=n!。若有F(f)=(F f)=f，对于函数((F f) n) = (f n),f是函数F的不动点。

lambda表达式可以为：

    F = 
       (lambda (f)
           (lambda (n)
               (if (< n 2)
                    1
                    (* n (f (- n 1))))))

 上述是一个柯里化函数，当我们传递函数f给F的时候，由于f是不动点，F(f)=f,那么，上述要计算f，也就是计算出F的真正的不动点。

如何计算函数的不动点？

3、Y算子

Y算子：是一种高阶函数，它用于计算任意函数的不动点。

Y算子基础：假定对于函数f，存在不动点x，有f(x)=x，那么Y（f）=x。因此，f(Y(f))=Y(f),schema格式(f (Y f))=(Y f)这为Y算子。

Y算子的scheme的表达式：

    (define Y
       (lambda (f)
           (let ((g (lambda (h)
                 (lambda (x) ((f (h h)) x)))))
               (g g))))

 验证：使Y作用于上述F可得：

    (let ((f (Y (lambda (h)
                (lambda (n)
                  (if (< n 2) 1 (* n (h (- n 1)))))))))
       (display (f 5)))

//120

分析如下：

1、let赋值里面计算f，f=(Y F)。F函数如上面，在let之后，F的值被唯一确定。
2、将F作为Y的参数计算Y
3、在Y中需要计算g，g是一个lambda表达式(这个lambda表达式中有没有算出来的未知数)
4、Y返回的结果为(g g)，所以f=(g g)=(lambda (x) ((F (g g)) x))，有了f就可以计算(f 5)了
5、(f 5)=((F g g) 5)=((F f) 5),则f是不动点，产生了
6、(f 5)则需要计算的是((F (g g)) 5),而我们知道(g g)的展开结果，带入((F (lambda (x) (F (g g)) x)) 5),对于F计算。带入F则成为依次循环下去,直到n=1.

3.1：Y算子的推导

1、假设定义如下

    (define f
        (lambda (n)
           (if (< n 2)
               1
               (* n (f (- n 1))))))

2、重复传入递归函数本身,避免自身引用的问题

    (let ((g (lambda (h n)
           (if (< n 2) 1 (* n (h h (- n 1))))))) 
       (g g 10)

3、将上面的函数柯里化，转换为下面的函数。

    (let ((g (lambda (h)
           (lambda (n) 
             (if (< n 2) 1 (* n ((h h) (- n 1))))))))
       ((g g) 10))

4、将上面的函数转换为下面的样子。  

    (let ((g (lambda (h) 
           (lambda (n) 
             (let ((f (lambda (q n)
                        (if (< n 2) 1 (* n (q (- n 1)))))))
               (f (h h) n))))))
      (display ((g g) 10)))

5、再柯里化一遍。

    (let ((g (lambda (h)
           (lambda (n)
             (let ((f (lambda (q)
                        (lambda (n)
                          (if (< n 2) 1 (* n (q (- n 1))))))))
               ((f (h h)) n))))))
       (display ((g g) 10)))

上述获得Y算子。

hbghlyj

How to reinvent the Y combinator
重新发明 Y 组合子 JavaScript(ES6) 版

(Y F) = (F (Y F))

接下来的推导为了方便使用ES6

首先来推导公式的左边

(Y F)
=
((h =>
    (f => h ( v => f(f)(v) ))
    (f => h ( v => f(f)(v) ))
) F)
= 
    (f => F ( v => f(f)(v) ))
    (f => F ( v => f(f)(v) ))
=
F( (f => F ( v => f(f)(v) )) (f => F ( v => f(f)(v) )) )

然后来推导公式的右边

(F (Y F) )
=
F ( (f => F ( v => f(f)(v) ))
    (f => F ( v => f(f)(v) )) )

Q.E.D.

hbghlyj

魂断不动点——Y组合子的前世今生 All About Y Combinator
Y不动点组合子用在哪里？
函数式编程的Y Combinator 有哪些实用价值？ - 知乎
λ-演算中，不动点算子（Fixpoint combinator）的形式和作用是 ...
不动点组合子-香蕉空间
函数式编程的基石- Y Combinator - Yaodan's Blog
lambda calculus:Y-combinator - 许炎的个人博客
the little schemer - Y combinator - 柒八块表的博客
Lambda演算之Y-Combinator的推导
计算的本质：深入剖析程序和计算机》读书笔记（第5-9 章
Y Combinator 推导| wkgcass.blogs
对于Y组合子的理解 - Personball's Blog
lambda演算
Rust 中的闭包递归与Y 组合子| Nihil
Y Combinator - Shell's Home
Javascript 中Y 组合子的推导- 一隅
从自输出程序到Y 组合子- /home/ksqsf
如何实现一个没有名字的递归函数
Y组合子
关于循环的证明和完全格上单调函数的不动点定理
与计算机科学的关系基本知识 偏序集合、最小上界、函数的不动点、递归函数定义、递归函数定义的解、不动点算子、最小不动点定理
Js最简Y不动点组合子
Python lambda实现Y组合子 - 马車同学
使用Lambda 表达式编写递归三：实现Y 组合子- 鹤冲天
函数式编程| #02 | Lambda演算中的循环与递归 - GZTime's Blog
计算理论的一些基础知识 - blog | 逍遥郡
《The Little Schemer》笔记1.0 文档
Y 组合子详解 （The Y Combinator）
从递归到Y 组合子 - 星雨之夜
Y组合子的一个启发式推导
十分钟速通Y Combinator - 代码混音师
Y 组合子详解（The Y Combinator）不动点组合子
不动点组合子· Issue #5 · CharLemAznable/blog
不动点组合子| Y Combinator | 「浮生若梦」 - sczyh30
不动点组合子，Y-Combinator - Roselia
不动点组合子Y-Combinator - Calvin's Marbles
Lambda calculus引论(二): 不动点

hbghlyj

Y Combinator、lambda算子和不动点原理

2.3. 不动点原理

2.3.1. 假想一个函数，得到简洁的递归

然而，看看我们的 P 的定义，是不是很丑陋？ “n*self(self, n-1)” ？什么玩意？为什么要多出一个多余的 self ？ DRY ！怎么办呢？我们想起我们一开始定义的那个失败的 P ，虽然行不通，但最初的努力往往是大脑最先想到的最直观的做法，我们来回顾一下：

    let P = lambda self n. If_Else n==0 1 n*self(n-1)

这个 P 的函数体就非常清晰，没有冗余成分，虽然参数列表里面多出一个 self ，但我们其实根本不用管它，看函数体就行了， self 这个名字已经可以说明一切了对不对？但很可惜这个函数不能用。我们再来回想一下为什么不能用呢？因为当你调用 P(P, n) 的时候，里面的 self(n-1) 会展开为 P(n-1) 而 P 是需要两个参数的。唉，要是这里的 self 是一个 “ 真正 ” 的，只需要一个参数的递归阶乘函数，那该多好啊。为什么不呢？干脆我们假设出一个 “ 真正 ” 的递归阶乘函数：

    power(n):

        if(n==0) return 1;

        return n*power(n-1);

但是，前面不是说过了，这个理想的版本无法在 lambda 算子系统中定义出来吗（由于 lambda 函数都是没名字的，无法自己内部调用自己）？不急，我们并不需要它被定义出来，我们只需要在头脑中 “ 假设 ” 它以 “ 某种 ” 方式被定义出来了，现在我们把这个真正完美的 power 传给 P ，这样：

    P(power, 3)

注意它跟 P(P, 3) 的不同， P(P, 3) 我们传递的是一个有缺陷的 P 为参数。而 P(power, 3) 我们则是传递的一个真正的递归函数 power 。我们试着展开 P(power, 3):

    IF_Else 3==0 1 3*power(3-1)

发生了什么？？ power(3-1) 将会计算出 2 的阶乘（别忘了， power 是我们设想的完美递归函数），所以这个式子将会忠实地计算出 3 的阶乘！

回想一下我们是怎么完成这项任务的：我们设想了一个以某种方式构造出来的完美的能够内部自己调用自己的递归阶乘函数 power ，我们发现把这个 power 传给 P 的话， P(power, n) 的展开式就是真正的递归计算 n 阶乘的代码了。

你可能要说：废话！都有了 power 了我们还要费那事把它传给 P 来个 P(power, n) 干嘛？直接 power(n) 不就得了？ ! 别急，之所以设想出这个 power 只是为了引入不动点的概念，而不动点的概念将会带领我们发现 Y combinator 。

2.3.2. 使用部分求值观察“不动点”

什么是不动点？一点都不神秘。让我们考虑刚才的 power 与 P 之间的关系。一个是真正可递归的函数，一个呢，则是以一个额外的 self 参数来试图实现递归的伪递归函数，我们已经看到了把 power 交给 P 为参数发生了什么，对吧？不，似乎还没有，我们只是看到了， “ 把 power 加上一个 n 一起交给 P 为参数 ” 能够实现真正的递归。现在我们想考虑 power 跟 P 之间的关系，直接把 power 交给 P 如何？

    P(power)

这是什么？这叫函数的 部分求值(partial evaluation) 。换句话说，第一个参数是给出来了，但第二个参数还悬在那里，等待给出。那么，光给一个参数得到的是什么呢？是 “ 还剩一个参数待给的一个新的函数 ” 。其实也很简单，只要按照 Beta 转换规则做就是了，把 P 的函数体里面的 self 出现处皆替换为 power 就可以了。我们得到：

    IF_Else n==0 1 n*power(n-1)

当然，这个式子里面还有一个变量没有绑定，那就是 n ，所以这个式子还不能求值，你需要给它一个 n 才能具体求值，对吧。这么说，这可不就是一个以 n 为参数的函数么？实际上就是的。在 lambda 算子系统里面，如果给一个 lambda 函数的参数不足，则得到的就是一个新的 lambda 函数，这个新的 lambda 函数所接受的参数也就是你尚未给出的那些参数。换句话来说，调用一个 lambda 函数可以分若干步来进行，每次只给出一部分参数，而只有等所有参数都给齐了，函数的求值结果才能出来，否则你得到的就是一个 “ 中间函数 ” 。

那么，这跟不动点定理有什么关系？关系大了，刚才不是说了， P(power) 返回的是一个新的 “ 中间函数 ” 嘛？这个 “ 中间函数 ” 的函数体我们刚才已经看到了，就是简单地展开 P(power) 而已，回顾一遍：

    IF_Else n==0 1 n*power(n-1)

我们已经知道，这是个函数，参数 n 待定。因此我们不妨给它加上一个 “lambda n” 的帽子，这样好看一点：

    lambda n. IF_Else n==0 1 n*power(n-1)

这是什么呢？这可不就是 power 本身的定义？（当然，如果我们能够定义 power 的话）。不信我们看看 power 如果能够定义出来像什么样子：

    let power = lambda n. IF_Else n==0 1 n*power(n-1)

一模一样！也就是说， P(power) 展开后跟 power 是一样的。即：

    P(power) = power

以上就是所谓的不动点。即对于函数 P 来说 power 是这样一个 “ 点 ” ：当把 P 用到 power 身上的时候，得到的结果仍然还是 power ，也就是说， power 这个 “ 点 ” 在 P 的作用下是 “ 不动 ” 的。

2.3.3. 构造“不动点”函数

2.3.3.1. 能生成“不动点”函数的函数：Y

可惜的是，这一切居然都是建立在一个不存在的 power 的基础上的，又有什么用呢？可别过早提 “ 不存在 ” 这个词，你觉得一样东西不存在或许只是你没有找到使它存在的正确方法。我们已经看到 power 是跟 P 有着密切联系的。密切到什么程度呢？对于伪递归的 P ，存在一个 power ，满足 P(power)=power 。注意，这里所说的 “ 伪递归 ” 的 P ，是指这样的形式：

    let P = lambda self n. If_Else n==0 1 n*self(n-1)    // 注意， 不是 self(self,n-1)

一般化的描述就是，对任一伪递归 F （回想一下伪递归的 F 如何得到 —— 是我们为了解决 lambda 函数不能引用自身的问题，于是给理想的 f 加一个 self 参数从而得到的），必存在一个理想 f （ F 就是从这个理想 f 演变而来的），满足 F(f) = f 。

那么，现在的问题就归结为如何针对 F 找到它的 f 了。根据 F 和 f 之间的密切联系（ F 就比 f 多出一个 self 参数而已），我们可以从 F 得出 f 吗？假设我们可以（又是假设），也就是说假设我们找到了一根魔棒，把它朝任意一个伪递归的 F 一挥，眼前一花，它就变成了真正的 f 了。这根魔棒如果存在的话，它具有什么性质？我们假设这个神奇的函数叫做 Y ，把 Y 用到任何伪递归的函数 F 上就能够得到真正的 f ，也就是说：

    Y(F) = f

结合上面的 F(f) = f ，我们得到：

    Y(F) = f = F(f) = F(Y(F))

也就是说， Y 具有性质：

    Y(F) = F(Y(F))          // （3）能生成不动点函数的函数性质

性质倒是找出来了，怎么构造出这个 Y 却又成了难题。一个办法就是使用抽象法，这是从工程学的思想的角度，也就是通过不断迭代、重构，最终找到问题的解。然而对于这里的 Y combinator ，接近问题解的过程却显得复杂而费力，甚至过程中的有些点上的思维跳跃有点如羚羊挂角无迹可寻。然而，在这整个 Y combinator 介绍完了之后我们将会介绍著名的哥德尔不完备性定理，然后我们就会发现，通过哥德尔不完备性定理证明中的一个核心构造式，只需一步自然的推导就能得出我们的 Y combinator 。而且，最美妙的是，还可以再往下归约，把一切都归约到康托尔当初提出的对角线方法，到那时我们就会发现原来同样如羚羊挂角般的哥德尔的证明其实是对角线方法的一个自然推论。数学竟是如此奇妙，我们由简单得无法再简单的 lambda calculus 系统的两条公理居然能够导出如此复杂如此令人目眩神迷的 Y Combinator ，而这些复杂性其实也只是荡漾在定理海洋中的涟漪，拨开复杂性的迷雾我们重又发现它们居然寓于极度的简洁之中。这就是数学之美。

2.3.3.2. 构造函数Y

让我们先来看一看 Y combinator 的费力而复杂的工程学构造法，我会尽量让这个过程显得自然而流畅 [7] ：

我们再次回顾一下那个伪递归的求阶乘函数：

    let P = lambda self n. If_Else n==0 1 n*self(n-1)

我们的目标是找出 P 的不动点 power ，根据不动点的性质，只要把 power 传给 P ，即 P(power) ，便能够得到真正的递归函数了。

现在，关键的地方到了，由于：

    power = P(power) // 不动点原理

这就意味着， power 作为一个函数（ lambda calculus 里面一切都是函数），它是自己调用了自己的。那么，我们如何实现这样一个能够自己调用自己的 power 呢？回顾我们当初成功的一次尝试，要实现递归，我们是通过增加一个间接层来进行的：

    let power_gen = lambda self. P(self(self))

还记得 self (self) 这个形式吗？我们在成功实现出求阶乘递归函数的时候不就是这么做的？那么对于现在这个 power_gen ，怎么递归调用？

    power_gen(power_gen)

不明白的话可以回顾一下前面我们调用 P(P, n) 的地方。这里 power_gen(power_gen) 展开后得到的是什么呢？我们根据刚才 power_gen 的定义展开看一看，原来是

    P (power_gen(power_gen))

看到了吗？也就是说：

    power_gen(power_gen) => P(power_gen(power_gen))

现在，我们把 power_gen(power_gen) 当成整体看，不妨令为 power ，就看得更清楚了：

    power => P(power)

这不正是我们要的答案么？

OK ，我们总结一下：对于给定的 P ，只要构造出一个相应的 power_gen 如下：

    let power_gen = lambda self. P(self(self))

我们就会发现， power_gen(power_gen) 这个调用展开后正是 P(power_gen(power_gen)) 。也就是说，我们的 power_gen(power_gen) 就是我们苦苦寻找的不动点了！

2.4. 铸造 Y Combinator

现在我们终于可以铸造我们的 Y Combinator 了， Y Combinator 只要生成一个形如 power_gen 的 lambda 函数然后把它应用到自身，就大功告成：

    let Y = lambda F.

        let f_gen = lambda self. F(self(self))

        return f_gen(f_gen)

稍微解释一下， Y 是一个 lambda 函数，它接受一个伪递归 F ，在内部生成一个 f_gen （还记得我们刚才看到的 power_gen 吧），然后把 f_gen 应用到它自身（记得 power_gen(power_gen) 吧），得到的这个 f_gen(f_gen) 也就是 F 的不动点了（因为 f_gen(f_gen) = F(f_gen(f_gen)) ），而根据不动点的性质， F 的不动点也就是那个对应于 F 的真正的递归函数！

如果你还觉得不相信，我们稍微展开一下看看，还是拿阶乘函数说事，首先我们定义阶乘函数的伪递归版本：

    let Pwr = lambda self n. If_Else n==0 1 n*self(n-1)

让我们把这个 Pwr 交给 Y ，看会发生什么（根据刚才 Y 的定义展开吧）：

    Y(Pwr) =>

        let f_gen = lambda self. Pwr(self(self))

        return f_gen(f_gen)

Y(Pwr) 的求值结果就是里面返回的那个 f_gen(f_gen) ，我们再根据 f_gen 的定义展开 f_gen(f_gen) ，得到：

     Pwr(f_gen(f_gen))

也就是说：

     Y(Pwr) => f_gen(f_gen) => Pwr(f_gen(f_gen))

我们来看看得到的这个 Pwr(f_gen(f_gen)) 到底是不是真有递归的魔力。我们展开它（注意，因为 Pwr 需要两个参数，而我们这里只给出了一个，所以 Pwr(f_gen(f_gen)) 得到的是一个单参（即 n ）的函数）：

    Pwr(f_gen(f_gen)) => If_Else n==0 1 n*f_gen(f_gen) (n-1)

而里面的那个 f_gen (f_gen) ，根据 f_gen 的定义，又会展开为 Pwr(f_gen(f_gen)) ，所以：

    Pwr(f_gen(f_gen)) => If_Else n==0 1 n* Pwr(f_gen(f_gen)) (n-1)

看到加粗的部分了吗？因为 Pwr(f_gen(f_gen)) 是一个接受 n 为参数的函数，所以不妨把它令成 f （ f 的参数是 n ），这样上面的式子就是：

    f => If_Else n==0 1 n*f(n-1)

完美的阶乘函数！

hbghlyj

《不动点与零点的迭代逼近及应用》第1章 引言
1.5 常见的不动点定理及相关概念
不动点定理, 以 Banach 压缩映象定理为最著名. 在 1922 年, Banach 给 出的 Banach 压缩映象定理, 建立了积分方程解的存在性问题. 自从那时, 由于它的简洁性和实用性, 它在解决数学分析的许多分支存在性问题上变成 了非常有用的工具.
（1）布劳威尔不动点定理 (1910)
设 $X$ 是欧氏空间中的紧凸集, 那么 $X$ 到自身的每个连续映射都至少有一个不动点.
用这定理可以证明代数基本定理: 复系数的代数方程一定有复数
解. 把布劳威尔定理中的欧氏空间换成巴拿赫空间, 就是绍德尔不动点定 理(1930), 常用于偏微分方程理论. 这些定理可以从单值映射推广到集值 映射,除微分方程理论外还常用于对策论和数理经济学.
（2）巴拿赫压缩映射原理 (1922)
设 $X$ 是一个完备的度量空间, 映射 $f: X \rightarrow X$ 把每两点的距离至少压缩 $\lambda$ 倍, 即 $\mathrm{d}(f(x), f(y)) \leqslant \lambda \mathrm{d}(x, y)$, 这里 $\lambda$ 是一个小于 1 的常数, 那么 $f$ 必有而且只有一个不动点, 而且从 $X$ 的任何点 $x_0$ 出发作出序列不动点理论这 序列一定收玫到那个不动点.
这一原理不仅可以判定不动点的存在性和唯一性, 而且还能构造一个迭代序列逼近不动点. 从此,构造各种迭代格式来研究不动点的收玫性问 题纷至沓来, 非扩张映象作为 Banach 映象的一种自然推广, 越来越被人们重视. 同时由于分析学的需要, 这定理已被推广到概率度量空间、映射族、 集值映射等许多方面.
（3）不动点指数
不动点的个数有两种数法. 代数上通常说 $n$ 次复多项式有 $n$ 个复根, 是 把一个 $k$ 重根算作 $k$ 个根的; 如果不把重数统计在内, 根的个数就可以小于 $n$. 推广根的重数概念, 可以定义不动点的指数, 它是一个整数, 可正可负可 零, 取决于映射在不动点附近的局部几何性质. 一个映射的所有不动点的 指数的总和, 称为这映射的不动点代数个数, 以别于不动点的实际个数.