高中的时候做过一道题，着实把我难住了。自嵌套本身难度一般，但是它的目标是为这个抽象函数求和，这也就导致了一个问题——在不知道生成方程的时候，我该如何求和。下面我们会从一个例题出发。

已知 \(f:\mathbb{N}^*\rightarrow\mathbb{N}^*\)，\(f(n)\) 为增函数，且满足 \(f(f(n))=2n+1，n\in\mathbb{N}^*\) 求：

\[\sum^{2^n}_{i=1}f(i)\]

自嵌套函数最直接的解决办法就是再套一层，事实上每一个自嵌套的解决方法都是如此，即有：

\[\begin{align} &\Rightarrow f(f(f(n)))=2f(n)+1\\ &\Rightarrow f(2n+1)=2f(n)+1 \end{align}\]

这个式子我们先放在一边，先考虑 $f(f(n))$ 的最小情况，即 $f(f(1))=3$，接下来我们进行假设：

  • 若 $f(1)=1$，那么 $f(f(1))=f(1)=3$ ，矛盾
  • 若 $f(1)=2$，那么 $f(f(1))=f(2)=3$ ，成立
  • 若 $f(1)=t\ge3$，因为 $f(f(1))=3$，函数又递增，显然不成立。

所以我们得知 $f(1)=2$ 和 $f(f(1))=f(2)=3$ 进一步的，根据上面的 $f(2n+1)=2f(n)+1$，我们可以得到一些特定的项 $p$。而所有其余项 $q$ 则需要根据 $p$ 进行范围的缩小，例如 $f(3)=5$ 和 $f(5)=7$，由于函数递增且映射到 $\mathbb{N}^*$，所以 $f(4)=6$。

再往下走一层，我们可以知道 $f(6)=f(f(4))=9$，$f(7)=f(f(5))=11$，$f(9)=f(f(6))=13$，其中 $f(8)$ 由 $f(7)$ 和 $f(9)$ 的范围限定得到为 $12$。

我们似乎可以从中发现一些规律，让我们列一个表：

项数 值 生成方式
1 2 推理
2 3 原式 $p$
3 5 原式 $p$
4 6- 范围限定 $q$
5 7- 原式 $p$
6 9= 原式 $p$
7 11= 原式 $p$
8 12- 范围限定 $q$
9 13- 原式 $p$
10 14- 范围限定 $q$
11 15- 原式 $p$
12 17= 原式 $p$
13 19= 原式 $p$
14 21= 原式 $p$
15 23= 原式 $p$
16 24 范围限定 $q$
17 25- 原式 $p$
18 26- 范围限定 $q$
19 27- 原式 $p$
20 28- 范围限定 $q$
21 29- 原式 $p$
22 30- 范围限定 $q$
23 31- 原式 $p$
24 33= 原式 $p$
25 35= 原式 $p$
… … …

我们考虑 $n$ 个值和序号均连续的项，我们称这些项为 $A_x$：

\[\begin{align} &f(i)=j\quad \cdots\quad f(i+n-1)=j+n-1\\ &f(i+k)=j+k\quad,k\in\{0,\dots,n-1\} \end{align}\]

下标范围为 $[i,i+n-1]$

那么它必定可以生成另外 $n$ 个序号连续，但是值相差 $2$ 的的项，我们称这些项为 $B_x$：

\[\begin{align} &f(f(i))=f(j)=2i+1\quad \cdots\quad f(f(i+n-1))=f(j+n-1)=2i+2n-1\\ &f(f(i+k))=f(j+k)=2(i+k)+1\quad,k\in\{0,\dots,n-1\} \end{align}\]

下标范围为 $[j,j+n-1]$

我们记 $A_i$ 或 $B_i$ 序列中的第 $k$ 项为 \(A_{ik}\quad和\quad B_{ik}\)

再推一次，我们会发现这生成的 $n$ 个项可以再次生成 $2n-1$ 个值和序号连续的项，其中 $n$ 个项属于原式推出得到的 $p$ 类项：

\[\begin{align} &f(f(j))=f(2i+1)=2j+1\quad \cdots\quad f(f(j+n-1))=f(2(i+n-1)+1)=2j+2n-1\\ &f(f(j+k))=f(2(i+k)+1)=2(j+k)+1\quad,k\in\{0,\dots,n-1\} \end{align}\]

对于其中的 $f(2i+2)\quad to\quad f(2i+2n-2)$ 这 $n-1$ 个项，则是需要范围限定才能得到生成公式的 $q$ 类项，即有：

\[f(2i+2)=2(j+1)\quad \cdots\quad f(2i+2n-2)=2(j+n-1)\]

我们暂且将上面这个数列称为 $A_{x+1}$。下标范围为 $[2i+1,2(i+n-1)+1]$

[!attention] 二次操作的深层理解 这一个二次生成的过程有一个更深的理解，我们对一个值 $a$ 进行一次操作的时候其实相当于，将函数应用于这个值身上，即 $f(a)$，第二次应用于这个值身上的时候就相当于 $f(f(a))$ 了，也就是我们一开始做的再一次自嵌套的过程。 所以，对于 $f(i)=j$，一定会有 $f(2i+1)=2f(i)+1=2j+1$，这一个再推一次的过程实际上被我们找到的 $f(2n+1)=2f(n)+1$ 所代替了。

对于 $2^n$ 项的重要证明

通过观察，我们发现 $f(2^n)$ 似乎有迹可循，我们不妨用归纳假设法，设 $f(2^n)=3\times2^{n-1}$，则对 $n=1$ 时，有

\[f(2)=3\times2^0=3\quad 成立\]

推广到 $n\ge2$，则有

\[\begin{align} f(2(2^{n})+1)&=2f(2^{n})+1\\ \Rightarrow f(2^{n+1}+1)&=2(3\times2^{n-1})+1\\ &=3\times2^{n}+1 \end{align}\]

考虑 $f(2(2^{n}-1)+1)=f(2^{n+1}-1)$，其结果为 $2f(2^{n}-1)+1$，我们令 $f(2^{n+1}-1)$ 和 $f(2^{n+1}+1)$ 的差为 $d_n$，则有

\[d_n=(3\times2^n+1)-(2f(2^n-1)+1)=2[f(2^n)-f(2^n-1)]\]

另外，注意到 $f(2^{n+1}-1)$ 的结果是奇数，$f(2^n)=3\times2^n$ 的结果是偶数，$f(2^n+1)=3\times2^n+1$ 是奇数。但现在问题是我们并不知道这个 $d_n$ 的值是什么，他有可能是 $2$，也有可能是 $6$…我们需要更多的条件来排除。为解决这个问题，我们证明下面这个引理：

对任意 $n\ge 1$，$f(n+1)-f(n)=1$ 或 $2$ 由于 $f$ 严格递增，两个连续项的差至少为 $1$。假设存在两项间的差大于 $3$，我们假设这两项为 $n$ 和 $n+1$，既有 \(f(n+1)-f(n)\ge 3\) 同时，我们设 $f(n+1)=m’，f(n)=m$，则有 \(f(m')=2(n+1)+1=2n+3\quad f(m)=2n+1\) 但是，别忘了 $m’-m\ge 3$，而 $f$ 又单调递增，所以 $f(m’)$ 到 $f(m)$ 需要能够塞得下至少两个数。显然，这是不可能的。所以假设不成立，两项之间的差小于 $3$。

这也就说明，上面的 $d$ 只有可能是 $2$，所以，我们的归纳是正确的。

$A_{x+1}$ 的补充

对 $A_{x+1}$ 的补充需要结合具体的例子。我们不妨就从 $f(2^2)$ 开始推，并令此时 $A$ 的下标为 $2$，即有 $i=4,j=6,n=2$ $A_2$ 为 ${f(4),f(5)}$，$B_2$ 为 ${f(6),f(7)}$。我们发现这样“初始化”之后的数列，每一个 $A_x$ 的开头下标刚好都是 $2^n$。

对于之后的 $A_n$ 和 $A_{n+1}$，有 $i=2^n,j=3\times2^{n-1},n=n$，经过计算，每一个 $<A_n,B_n>$ 都可以完美的填满 $[2^n,2^{n+1})$ 这片区域，具体计算这里不做赘述。

因此，我们可以将 $A_{x+1}$ 进行扩充，即 $f(2i)=2j$。也就是说，从每一个下标为 $2^n$ 的地方开始，会有 $n$ 个连续的项（即 $A_n$）和 $n$ 个等差为 $2$ 的项（即 $B_n$）。

到此为止，我们总算可以写出 $f(n)$ 的通项公式了。后面的求和这里不做赘述，重要的是思想。