Grossman 常数

考虑由如下递推关系确定的实数数列 $\lbrace A_n \rbrace$：

$\begin{aligned} A_{n+2} = \frac{A_n}{1+A_{n+1}} \\ A_0=1,\; A_1=x \end{aligned}$

可以证明，有且仅有一个 $x=x_0$ 使得 $\lbrace A_n \rbrace$ 收敛。这个 $x_0 = 0.7373383…$ 被称为 Grossman 常数。

Grossman 常数在 Wolfram 百科里面有讲，也在 Finch, S. R.《 Mathematical Constants》又讲，但是都依赖于核心论文 Janssen, A. J. E. M. and Tjaden, D. L. A. Solution to Problem 86-2. Math. Intel. 9, 40-43, 1987. 折腾终于下下来了。

吐槽一下 Wolfram 百科提供的所有 Reference 链接没法访问。。。

为了方便起见，我们记：

$\begin{aligned} A_0(x) = \alpha >0 ,\; A_1(x) = x \\ A_{n+2}(x) = \frac{A_{n}(x)}{1+A_{n+1}(x)} \end{aligned}$

首先罗列一些显而易见的结果：

如果 $x>0$，则 $A_n(x)>0$，且 $A_{2n}(0)=\alpha,A_{2n+1}(0)=0$
$a(x) = \lim A_{2n}(x),\; b(x)= \lim A_{2n+1}(x)$ 均存在，且 $a(x)b(x)=0$
如果 $\lim A_n(x)$ 存在，则为 $0$
如果 $x \leq 0$，则 $\lim A_n(x)$ 不存在（反证，奇偶项写出两个递推关系分析）

以下仅考虑 $x\geq 0$ 的情形
$A_{2n}(x)$ 是连续单调递减的函数（数学归纳）
$A_{2n+1}(x)$ 是连续单调递增的函数（数学归纳）
$a(x) \geq 0$ 单调递减，$b(x) \geq 0$ 单调递增
$A_{2n}(x),\;A_{2n+1}(x)$ 都关于 $n$ 单调递减
重要公式（累和相加）：
$\alpha - A_{2N+2}(x) = \sum_{n=0} ^N A_{2n+1}(x) A_{2n+2}(x) \\ x - A_{2N+3}(x) = \sum_{n=0} ^N A_{2n+3}(x) A_{2n+2}(x)$

以上罗列的结果按顺序证明是容易的！

$\lim A_n(x) =0$ 当且仅当 $A_n(x)$ 关于 $n$ 单调递减

Proof：若 $\lim A_n(x) =0$ ，再由上面的 “重要公式” 易知：

$A_{2N+2}(x) = \sum_{n=N+1} ^ \infty A_{2n+1}(x) A_{2n+2}(x) \\ A_{2N+3}(x) = \sum_{n=N+1} ^ \infty A_{2n+3}(x) A_{2n+2}(x)$

所以 $A_{2N+2}>A_{2N+3}$ ，紧接着 $A_{2N+1} = \sum_{n=N+1} ^ \infty A_{2n+1}A_{2n} > A_{2N+2}$，所以 $A_n(x)$ 关于 $n$ 单调递减

这也提供了一个求解 Grossman 常数的数值依据。

最多只有一个 $x$ 使得 $\lim A_n(x) =0$

Proof：若 $\lim A_n(y) = \lim A_n(x) = 0,\; y>x$，则：

$\frac{A_{n+2}(y)}{A_{n+2}(x)} = \frac{A_{n}(y)}{A_{n}(x)} \frac{1+A_{n+1}(x)}{1+A_{n+1}(y)}$

从而

$\frac{A_{2n+2}(y)}{A_{2n+2}(x)} = \prod _{k=1} ^n \frac{1+A_{2k+1}(y)}{1+A_{2k+1}(x)} \\ \frac{A_{2n+1}(y)}{A_{2n+1}(x)} = \frac{y}{x} \prod _{k=1} ^n \frac{1+A_{2k}(y)}{1+A_{2k}(x)}$

从而 $\frac{A_{2n+2}(y)}{A_{2n+2}(x)}$ 单调递减收敛于 $L_1 \leq 1$，$\frac{A_{2n+1}(y)}{A_{2n+1}(x)}$ 单调递增收敛于 $L_2>1$。所以

$\lim \frac{A_{2n+2}(y)}{A_{2n+2}(x)} \frac{A_{2n+1}(x)}{A_{2n+1}(y)} = \frac{L_1}{L_2} <1$

但是另一方面

$1 \geq \frac{A_{2n+2}(y)}{A_{2n+1}(y)} \geq \frac{A_{2n+3}(y)}{A_{2n+1}(y)} = \frac{1}{1+A_{2n+2}(y)} \to 1 \\ 1 \leq \frac{A_{2n+1}(x)}{A_{2n+2}(x)} \geq \frac{A_{2n+1}(x)}{A_{2n+3}(x)} = 1+A_{2n+2}(x) \to 1$

矛盾！

Dini 定理

为了证明的连贯性，先给出下面需要引用 Dini 定理（证明见陈纪修《数学分析》下册定理 10.2.7）

设函数序列 $\{S_n(x)\}$ 在闭区间 $[a,b]$ 上（点态）收敛于 $S(x)$，且满足：

$S_n(x)$ 在 $[a,b]$ 上连续
$\{S_n(x)\}$ 关于 $n$ 单调

则 $\{S_n(x)\}$ 在 $[a,b]$ 一致收敛于 $S(x)$ 当且仅当 $S(x)$ 在 $[a,b]$ 上连续（”$\Rightarrow$”易证，”$\Leftarrow$” 称作 Dini 定理）

存在唯一的 $x$ 使得 $\lim A_{n}(x) = 0$

由“重要公式”知：

$\alpha - a(x) = \sum_{n=0} ^{\infty} A_{2n+1}(x) A_{2n+2}(x) \\ x - b(x) = \sum_{n=0} ^{\infty} A_{2n+3}(x) A_{2n+2}(x) \\$

从而 $\alpha - a(x) > x - b(x)$，所以 $b(\alpha) > 0$，从而 $a(\alpha) = 0$，并且 $a(0) = \alpha,\; b(0) = 0$。令

$x_0 = \sup \{ x \in [0, \alpha] \mid a(x) >0 \} \\ x_1 = \inf \{ x \in [0,\alpha] \mid b(x)>0 \}$

显然 $x_0 \leq x_1$，若 $x_0 < x_1$，则对任意 $x_0 < x < x_1$ 有，$a(x) = b(x) = 0$，矛盾于收敛于 0 的 $x$ 最多只有一个，从而 $x_0 = x_1$。

注意到 $\frac{1}{1+\alpha} A_{2n+1}(x) A_{2n+2}(x) \leq A_{2n+3}(x) A_{2n+2}(x) \leq A_{2n+1}(x) A_{2n+2}(x)$，所以 $a(x),b(x)$ 在闭区间 $D$ 上有共同的一致收敛性，从而由 Dini 定理 知，$a(x)$ 在闭区间 $D$ 上连续当且仅当 $b(x)$ 在闭区间 $D$ 上连续。

我们想要证明 $a(x),b(x) $ 在区间 $[0,\alpha]$ 上连续，从而 $a(x_0) = b(x_0) = 0$。

当 $x < x_0$ 时，$b(x)=0$，当 $x > x_0$ 时，$a(x)=0$，所以 $a(x),b(x)$ 在 $[0,x_0) \cup (x_0, \alpha]$ 上连续。

若 $a(x_0) >0$，则 $b(x_0) = 0$，记 $b_0 = \lim_{x \to x_0 ^{+}} b(x)$，若 $b_0>0$，则

$A_{2k+2}(x) = \prod_{j=1} ^k \frac{1}{1+A_{2j-1}(x)} < \frac{1}{(1+b_0)^k} \quad x \in (x_0, \alpha ] \\ A_{2k+1}(x) = \prod_{j=1}^k \frac{1}{1+A_{2j}(x)} < \frac{1}{(1+a(x_0))^k} \quad x \in [0,x_0]$

从而 $a(x),b(x)$ 在 $[0,\alpha]$ 上一致收敛，矛盾，从而 $b_0 = 0$，从而 $b(x)$ 连续，从而 $a(x)$ 连续，矛盾，从而 $a(x_0) = 0$。同理 $b(x_0) = 0$。所以 $\lim A_n(x) = 0$。

Grossman 常数的推广

由上述过程可知，本质上，对每个给定的 $A_0 \geq 0$, 都存在唯一的 $0 \leq A_1 \leq A_0$ ，使得 $\lim A_n$ 存在（且等于 0）。我们不妨 $A_1 = F(A_0)$，其中 $F: [0, +\infty] \to [0, \infty]$，满足 $F(0)= 0$，若$x>0$ 则，$0<F(x)<x$ ，假设 $A_0 = \alpha$，则 $A_1 = F(\alpha),\;A_2 = \frac{\alpha}{1+F(\alpha)}$，而 $(A_0, A_1) = (F(\alpha),\frac{\alpha}{1+F(\alpha)})$ 必然能使得 $\lim A_n = 0$，所以 $F(F(\alpha)) = \frac{\alpha}{1+F(\alpha)}$，写成

$x = (1+F(x))F(F(x))$

由于 $a(x)$ 关于 $\alpha$ 连续，所以 $x_0(\alpha) = \sup \{ x \in [0, \alpha] \mid a(x) >0 \}$ 关于 $\alpha$ 连续，即上述 $F(x)$ 连续，若可导，则 $F(x)$ 单调递增。

上述形式最早由 Gabor Nyerges 给出（由于找不到文献，所以就自己推导了一下）

按照上述观点，从而 Grossman 常数就是 $F(1)$。

Grossman 常数的数值计算

由于 $\lim A_n(x) =0$ 当且仅当 $A_n(x)$ 关于 $n$ 单调递减。令 $n_0$ 是最小的 $n$ 使得 $A_{n+1}(x) > A_n(x)$，则

$A_{n+3}(x) - A_{n+2}(x) = \frac{(A_{n+1} - A_n) + (A_{n+1}^2 - A_n A_{n+2}) }{(1+A_{n+2})(1+A_{n-1})} > 0$

从而对任意 $k \geq 0$，$A_{n+2k+1} > A_{n+2k}$。

若 $n$ 为偶数，则 $b(x)>a(x)$，从而 $b(x) > 0 = a(x)$，即 $x>x_0$。反之，若 $n$ 为奇数，则 $x < x_0$。

#include <bits/stdc++.h>
using namespace std;

bool bigercheck(double x,double m,int step = 10000){
    bool ans=true;
    while(--step&&x>m){
        ans = !ans;
        double t=x/(1+m);
        x = m;
        m = t;
    }
    return x>m||ans;
}

double F(double x,double eps = 1e-12){
    double l =x/(1+x),r = x;
    while(r-l>eps){
        double m = (l+r)*0.5;
        if(bigercheck(x,m))  r=m;
        else l=m;
    }
    return r;
}

int main(){
    double x;
    while(cin>>x){
        cout<<F(x)<<endl;
        cout<<F(F(x))*(F(x)+1)-x<<endl;
    }
    return 0;
}

高精度太耗时了！参考 A085835

后来的故事

Gabor Nyerges 在 2014 年的论文《On the convergence of $x_n = f(x_{n–2}, x_{n–1})$ when $f (x, y) < x$. Advances in Difference Equations2014, 2014:8》中证明，只需 $f: (0,\infty)^2 \to (0,\infty)$，$f (x, y) < x$，且$f(x,y)$ 关于 $y$ 递减，则对任意 $x_0 > 0$，存在 $f(x_0,x_0)<x_1<x_0$ 使得 $x_n$ 单调递减趋于 0 。但是没法保证唯一性，毕竟条件这么弱。证明过程巧妙的应用了闭区间套定理。

明显的推论：若 $x_n = \frac{x_{n-2}}{1+f(x_{n-1})}$，其中 $f: (0,\infty) \to (0, \infty)$为单调递增的连续函数，则，对任意 $x \geq 0$，存在唯一的 $\frac{x_0}{1+f(x_0)} \leq x_1 \leq x_0$

Proof ：存在性由 Gabor Nyerges 的证明显然，唯一性模仿之前的过程显然。