习题 12, 附录 0

对于每个整数$n > 0$，令$n = \sum_{k=0}^{\infty} \varepsilon_k 2^k$为$n$的二元展开（$\varepsilon_k$是整数，零，除了指标，$0 \leq \varepsilon_k \leq 1$的有限数）。放

a) 证明公式$A_1(n) = \sum_{k=0}^{\infty} (k+2) \varepsilon_k 2^{k-1}$。推导出公式

随着$n$无限增长（将表示$A_1(n)$的和分解为两个部分、指标$k$，第一个和从0到$\mu(n)$，第一个和从$\mu(n)$到$n_1$）第二，其中 $n_1$ 是数 $k$ 的最大的，从而适当选择 $\varepsilon_k \neq 0$ 和 $\mu(n)$；使用 V、p. 239 的第 6 个参数绑定第一个和，然后估计第二个之间的差值。 和和 $n_1 n/2$。

b) 建立关系

$f$是在$\mathbf{N}$上定义的任意函数（对于给定的$k$，考虑$j < 2^m$的数，使得$\alpha(j) = k$）。

c) 对于$m = 2^r - 1$，证明$\alpha(m - j) + \alpha(j) = r$。从此和 b) 推出

d) 对于 $m = 2^r$ 表明

我们为所有 $n$ 放置了 $\alpha(n+1) - \alpha(n) = 1 - \Delta(n+1)$（使用 $b$），为 $r < 2^k$ 放置了关系 $\alpha(2^k + r) = \alpha(r) + 1$）。证明$\sum_{j=0}^{m-1} \binom{m-1}{j} \Delta(j+1) \leq r^{m-2}$（注，如果$j$是偶数则$\Delta(j+1) = 0$，对于所有$j$则$\Delta(j+1) \leq \log j / \log 2$）。借助 c) 推断出 来自 c) 的结论以及 $A_2(n)$ 的关系不等于任何 (H) 函数，因为 $n$ 趋向于 $+\infty$。