Exercice 19

1. (a) Si l'on suppose seulement $S_{n} \leqslant 2$, on obtient $S_{n+1} = S_{n} + \frac{1}{(n+1)^{2}} \leqslant 2 + \frac{1}{(n+1)^{2}}$, ce qui ne permet pas de conclure $S_{n+1} \leqslant 2$. $$\boxed{\text{L'hypothèse } S_{n} \leqslant 2 \text{ ne laisse aucune marge pour absorber le terme ajouté.}}$$

1. (b) On renforce l'énoncé en se ménageant une marge : montrons par récurrence que, pour tout $n \geqslant 1$, $$P(n) : \quad S_{n} \leqslant 2 - \frac{1}{n}$$ Initialisation. $S_{1} = 1 = 2 - \frac{1}{1}$, donc $P(1)$ est vraie.

Hérédité. Soit $n \geqslant 1$ tel que $P(n)$ soit vraie. Alors $S_{n+1} \leqslant 2 - \frac{1}{n} + \frac{1}{(n+1)^{2}}$, et il suffit de vérifier que ce majorant est inférieur à $2 - \frac{1}{n+1}$ : $$\frac{1}{(n+1)^{2}} \leqslant \frac{1}{n} - \frac{1}{n+1} = \frac{1}{n(n+1)} \quad\Longleftrightarrow\quad n(n+1) \leqslant (n+1)^{2},$$ ce qui est vrai. Ainsi $P(n+1)$ est vraie.

Conclusion. Pour tout $n \geqslant 1$ : $S_{n} \leqslant 2 - \frac{1}{n} < 2$. $$\boxed{S_{n} \leqslant 2 - \frac{1}{n} < 2 \text{ pour tout } n \geqslant 1}$$

À retenir : il est parfois plus facile de démontrer un énoncé plus fort, parce que l'hypothèse de récurrence est elle aussi plus forte. L'idée de la marge $\frac{1}{n}$ vient de la majoration $\frac{1}{k^{2}} \leqslant \frac{1}{k(k-1)} = \frac{1}{k-1} - \frac{1}{k}$, qui rend la somme télescopique (chapitre 3). La suite $(S_{n})$, croissante et majorée, converge (chapitre 7) ; on verra au chapitre 20 que sa limite vaut $\frac{\pi^{2}}{6} \approx 1{,}645$.

2. Les premiers termes sont : $$\boxed{u_{0} = 1,\ u_{1} = 1,\ u_{2} = 3,\ u_{3} = 5,\ u_{4} = 11,\ u_{5} = 21,\ u_{6} = 43}$$ On détermine $\alpha$ et $\beta$ à l'aide des deux premiers termes : $\alpha + \beta = 1$ et $2\alpha - \beta = 1$, d'où $\alpha = \frac{2}{3}$ et $\beta = \frac{1}{3}$. On conjecture donc $$\boxed{u_{n} = \frac{2^{n+1} + (-1)^{n}}{3}}$$ ce que confirment les valeurs $u_{2} = \frac{8 + 1}{3} = 3$ et $u_{3} = \frac{16 - 1}{3} = 5$. ✓

Démontrons-le par récurrence double. La formule est vraie aux rangs $0$ et $1$ par construction. Si elle est vraie aux rangs $n$ et $n + 1$, alors $$u_{n+2} = \frac{2^{n+2} + (-1)^{n+1}}{3} + 2 \times \frac{2^{n+1} + (-1)^{n}}{3} = \frac{2^{n+3} + (-1)^{n}\,(-1 + 2)}{3} = \frac{2^{n+3} + (-1)^{n+2}}{3}.$$ Comme dans l'exemple du cours, $2$ et $-1$ sont les racines de l'équation $r^{2} = r + 2$ associée à la relation de récurrence, ce que le chapitre 7 expliquera.

3. Existence, par récurrence forte. L'entier $1 = 2^{0}$ convient. Soit $n \geqslant 1$ tel que tout entier de $[\![1\,;n]\!]$ s'écrive comme somme de puissances de $2$ distinctes. L'ensemble des entiers $k$ tels que $2^{k} > n + 1$ est une partie non vide de $\mathbb{N}$ (elle contient $n + 1$), donc possède un plus petit élément $k_{0}$, d'après la proposition 4 du cours ; comme $2^{0} \leqslant n + 1$, on a $k_{0} \geqslant 1$, et $m = k_{0} - 1$ vérifie $2^{m} \leqslant n + 1 < 2^{m+1}$.

• Si $n + 1 = 2^{m}$, l'écriture est trouvée.

• Sinon, $r = n + 1 - 2^{m}$ vérifie $1 \leqslant r < 2^{m}$, et en particulier $r \leqslant n$. Par hypothèse, $r$ est une somme de puissances de $2$ distinctes, toutes inférieures à $r < 2^{m}$, donc différentes de $2^{m}$ ; il suffit d'y ajouter $2^{m}$.

Unicité. On utilise la somme géométrique $1 + 2 + \dots + 2^{M-1} = 2^{M} - 1 < 2^{M}$. Supposons qu'un entier admette deux écritures différentes ; en retirant les puissances communes, on obtient deux ensembles d'exposants $S$ et $T$ disjoints, non tous deux vides, de même somme $\sum_{j \in S} 2^{j} = \sum_{j \in T} 2^{j}$. Aucun des deux ne peut être vide, car l'autre aurait une somme nulle. Soit $M$ le plus grand élément de $S \cup T$, par exemple dans $S$. Les éléments de $T$ sont alors des entiers distincts strictement inférieurs à $M$, donc $\sum_{j \in T} 2^{j} \leqslant 2^{M} - 1 < 2^{M} \leqslant \sum_{j \in S} 2^{j}$ : contradiction. $$\boxed{\text{Tout entier } n \geqslant 1 \text{ s'écrit de façon unique comme somme de puissances de } 2 \text{ distinctes.}}$$ C'est l'écriture de $n$ en base $2$, utilisée par tous les ordinateurs. Elle servira à l'exercice 48.