Exercise 12, Appendix 0

For every integer $n > 0$ let $n = \sum_{k=0}^{\infty} \varepsilon_k 2^k$ be the dyadic expansion of $n$ ($\varepsilon_k$ is an integer, zero for all but a finite number of indices, $0 \leq \varepsilon_k \leq 1$). Put

a) Prove the formula $A_1(n) = \sum_{k=0}^{\infty} (k+2) \varepsilon_k 2^{k-1}$. Deduce the formula

as $n$ grows indefinitely (decompose the sum which expresses $A_1(n)$ into two parts, the index $k$ varying from 0 to $\mu(n)$ in the first sum, from $\mu(n)$ to $n_1$ in the second, where $n_1$ is the largest of the numbers $k$ such that $\varepsilon_k \neq 0$ and $\mu(n)$ is chosen suitably; bound the first sum using prop. 6 of V, p. 239, and then estimate the difference between the second sum and $n_1 n/2$.

b) Establish the relation

$f$ being an arbitrary function defined on $\mathbf{N}$ (for a given $k$ consider the number of $j < 2^m$ such that $\alpha(j) = k$).

c) For $m = 2^r - 1$ show that $\alpha(m - j) + \alpha(j) = r$. Deduce from this and from b) that

d) For $m = 2^r$ show that

where we have put $\alpha(n+1) - \alpha(n) = 1 - \Delta(n+1)$ for all $n$ (use $b$) and the relation $\alpha(2^k + r) = \alpha(r) + 1$ for $r < 2^k$). Show that $\sum_{j=0}^{m-1} \binom{m-1}{j} \Delta(j+1) \leq r^{m-2}$ (remark that $\Delta(j+1) = 0$ if $j$ is even, and $\Delta(j+1) \leq \log j / \log 2$ for all $j$). Deduce, with the help of c), that Conclude from c) and this relation that $A_2(n)$ is not equivalent to any (H) function as $n$ tends to $+\infty$.