Exercice 29

Idée. L'algorithme glouton retient $u_{k}$ chaque fois que la somme reste inférieure ou égale à $S$. S'il refuse une infinité de termes, l'écart à $S$ est majoré par des $u_{k}$ arbitrairement petits ; s'il n'en refuse qu'un nombre fini, l'hypothèse $u_{n} \leqslant R_{n}$ interdit le dernier refus.

On note $R_{n} = \sum_{k=n+1}^{+\infty} u_{k}$. Soit $S \in [0\,,U]$. On définit par récurrence la partie $A$ et les sommes $T_{k} = \sum_{j \in A,\, j < k} u_{j}$ : on pose $T_{0} = 0$ et, pour tout $k \in \mathbb{N}$, $$k \in A \text{ et } T_{k+1} = T_{k} + u_{k} \ \text{ si } T_{k} + u_{k} \leqslant S, \qquad k \notin A \text{ et } T_{k+1} = T_{k} \ \text{ sinon}.$$ Par récurrence, $T_{k} \leqslant S$ pour tout $k$. La suite $(T_{k})$ est croissante et majorée par $S$ : elle converge vers un réel $T \leqslant S$. C'est la suite des sommes partielles de la série à termes positifs $\sum_{k} \varepsilon_{k}u_{k}$, où $\varepsilon_{k} = 1$ si $k \in A$ et $0$ sinon, de sorte que $T = \sum_{k \in A} u_{k}$. Il reste à montrer que $T = S$.

Premier cas : une infinité d'entiers $k$ n'appartiennent pas à $A$. Pour un tel $k$, on a $T_{k} + u_{k} > S$, donc $0 \leqslant S - T \leqslant S - T_{k} < u_{k}$. Comme $u_{k}$ tend vers $0$ (proposition 2), le long de ces entiers en nombre infini, on obtient $S - T \leqslant 0$, d'où $T = S$.

Second cas : seuls un nombre fini d'entiers n'appartiennent pas à $A$. S'il n'y en a aucun, $A = \mathbb{N}$ et $T = U \geqslant S$, donc $T = S$. Sinon, soit $m$ le plus grand entier refusé : $T_{m} + u_{m} > S$, et tous les entiers $k > m$ appartiennent à $A$. Alors $$T = T_{m} + \sum_{k=m+1}^{+\infty} u_{k} = T_{m} + R_{m} \geqslant T_{m} + u_{m} > S,$$ en utilisant l'hypothèse $u_{m} \leqslant R_{m}$. C'est impossible, puisque $T \leqslant S$ : ce sous-cas ne se produit pas. $$\boxed{\text{pour tout } S \in [0\,,U], \text{ il existe } A \subset \mathbb{N} \text{ telle que } S = \sum_{k \in A} u_{k}}$$ L'exemple $u_{n} = \frac{1}{2^{n+1}}$. On a $R_{n} = \sum_{k=n+1}^{+\infty} \frac{1}{2^{k+1}} = \frac{1}{2^{n+1}} = u_{n}$ : l'hypothèse est vérifiée, avec égalité, et $U = 1$. $$\boxed{\text{tout réel } S \in [0\,,1] \text{ s'écrit } S = \sum_{k \in A} \frac{1}{2^{k+1}}, \quad A \subset \mathbb{N}}$$ C'est l'existence du développement en base $2$ : le chiffre d'indice $k + 1$ après la virgule vaut $1$ si $k \in A$ et $0$ sinon. Par exemple, pour $S = \frac{1}{3}$, l'algorithme retient les entiers impairs, et l'on retrouve $\frac{1}{3} = \sum_{j \geqslant 1} \frac{1}{4^{j}}$, soit $0{,}010101\ldots$ en base $2$. Pour $S = \frac{1}{2}$, il retient $0$ puis plus rien : il fournit le développement propre $0{,}1$, et non $0{,}0111\ldots$

Piège. L'hypothèse $u_{n} \leqslant R_{n}$ ne sert que dans le second cas, mais elle est indispensable. Pour $u_{n} = \frac{2}{3^{n+1}}$, on a $U = 1$ et $R_{0} = \frac{1}{3} < u_{0} = \frac{2}{3}$. Une somme $\sum_{k \in A} u_{k}$ vaut au moins $\frac{2}{3}$ si $0 \in A$, et au plus $R_{0} = \frac{1}{3}$ sinon : aucun réel de $\big]\frac{1}{3}\,,\frac{2}{3}\big[$, par exemple $\frac{1}{2}$, n'est atteint. En répétant l'argument, on obtient l'ensemble triadique de Cantor.