Exercice 12, Annexe 0

Pour tout entier $n > 0$, soit $n = \sum_{k=0}^\infty \varepsilon_k 2^k$ le développement dyadique de $n$ ($\varepsilon_k$ entier nul sauf pour un nombre fini d’indices, $0 \leq \varepsilon_k \leq 1$). On pose

a) Démontrer la formule $A_1(n) = \sum_{k=0}^\infty (k+2)\varepsilon_k 2^{k-1}$. En déduire la formule lorsque $n$ croît indéfiniment (décomposer la somme qui exprime $A_1(n)$ en deux parties, l’indice $k$ variant de $0$ à $\mu(n)$ dans la première somme, de $\mu(n)$ à $n_1$ dans la seconde, où $n_1$ est le plus grand des nombres $k$ tels que $\varepsilon_k \neq 0$, et $\mu(n)$ un nombre convenablement choisi; on majorera la première somme en utilisant la prop. 6 de V, p. 29, et on majorera ensuite la différence entre la deuxième somme et $n_1 n/2$).

b) Démontrer la relation

$f$ étant une fonction quelconque définie dans $\mathbf{N}$ (considérer pour un $k$ donné le nombre des $j < 2^m$ tels que $\alpha(j) = k$).

c) Pour $m = 2^r - 1$, démontrer la relation $\alpha(m-j) + \alpha(j) = r$. Déduire de cette relation et de b) qu’on a

d) Pour $m = 2^r$, montrer qu’on a

où on a posé $\alpha(n+1) - \alpha(n) = 1 - \Delta(n+1)$ pour tout $n$ (utiliser $b$) et la relation $\alpha(2^k + r) = \alpha(r) + 1$ pour $r < 2^k$. Montrer que $\sum_{j=0}^{m-1} \binom{m-1}{j} \Delta(j+1) \leq r2^{m-2}$ (remarquer que $\Delta(j+1) = 0$ si $j$ est pair, et $\Delta(j+1) \leq \log j / \log 2$ pour tout $j$). En déduire à l’aide de $c$, qu’on a Conclure de $c$ et de cette relation que $A_2(n)$ n’est équivalente à aucune fonction (H) lorsque $n$ tend vers $+\infty$.