Les défis étoilés : les trois réponses manquantes

L’Atelier a semé neuf encadrés « défi ». Cinq sont des fenêtres ouvertes sans question à résoudre (exercices 4, 14, 18, 25, 27) ; celui de l’exercice 11 est traité dans le corrigé, paragraphe « Défi » ; il en reste trois qui posaient une vraie question et attendaient une vraie réponse : ceux des exercices 20, 22 et 31. Les voici.

Défi de l’exercice 20 : la récurrence directe de $n + 1 \leqslant 2^n$

L’exercice avait obtenu l’inégalité par un détour analytique (la suite $\left(x_n\right)$ et sa décroissance). Le défi demandait la démonstration directe par récurrence, puis un jugement comparatif.

La récurrence. Pour tout $n \in \mathbb{N}$, notons $\mathcal{P}(n)$ l’énoncé : « $n + 1 \leqslant 2^n$ ».

Initialisation. Pour $n = 0$ : $0 + 1 = 1$ et $2^0 = 1$, donc $1 \leqslant 1$ : $\mathcal{P}(0)$ est vraie.

Hérédité. Soit $n \in \mathbb{N}$ tel que $\mathcal{P}(n)$ soit vraie, c’est-à-dire $n + 1 \leqslant 2^n$. Alors :

$$(n + 1) + 1 \leqslant 2^n + 1 \leqslant 2^n + 2^n = 2^{n+1},$$

la deuxième inégalité utilisant $1 \leqslant 2^n$, vraie pour tout $n \in \mathbb{N}$ (une puissance entière de $2$ vaut au moins $2^0 = 1$). Donc $\mathcal{P}(n+1)$ est vraie.

Conclusion. Par récurrence :

$$\boxed{\ \forall n \in \mathbb{N}, \quad n + 1 \leqslant 2^{\,n}\ }$$

Laquelle des deux apprend le plus ? La récurrence gagne sur la brièveté : quatre lignes, aucun outil, aucune idée à trouver. Mais elle vérifie sans expliquer. Le détour analytique de l’exercice, lui, disait trois choses que la récurrence tait. Il localise les cas d’égalité : $x_1 = x_0$, donc l’inégalité est une égalité en $n = 0$ et en $n = 1$ ($1 = 1$, puis $2 = 2$) et devient stricte ensuite. Il donne un résultat plus fort : non seulement $n + 1 \leqslant 2^n$, mais le quotient $\frac{n+1}{2^n}$ tend vers zéro, autrement dit $2^n$ ne se contente pas de dépasser $n+1$, il l’écrase (c’est déjà, en germe, la croissance comparée du chapitre F1). Enfin sa méthode, étudier le quotient $\frac{x_{n+1}}{x_n}$, se recycle telle quelle pour comparer $2^n$ à $n^2$, à $n^3$, à n’importe quelle puissance. Verdict honnête : pour démontrer, prenez la récurrence ; pour comprendre, le détour valait le voyage. C’est exactement pour cela que l’exercice vous a fait faire les deux.

Défi de l’exercice 22 : Nicomaque par récurrence, et le jugement

Le corrigé a démontré par télescopage la formule de la somme des cubes. Le défi demandait la rédaction concurrente par récurrence, puis de juger les deux.

La récurrence. Pour tout $n \in \mathbb{N}^*$, notons $\mathcal{P}(n)$ l’énoncé : « $\displaystyle\sum_{k=1}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^{\! 2}$ ».

Initialisation. Pour $n = 1$ : $\displaystyle\sum_{k=1}^{1} k^3 = 1$ et $\left(\frac{1 \times 2}{2}\right)^{\! 2} = 1$ : $\mathcal{P}(1)$ est vraie.

Hérédité. Soit $n \in \mathbb{N}^*$ tel que $\mathcal{P}(n)$ soit vraie. Alors :

$$\sum_{k=1}^{n+1} k^3 = \sum_{k=1}^{n} k^3 + (n+1)^3 = \left(\frac{n(n+1)}{2}\right)^{\! 2} + (n+1)^3.$$

Factorisons par $(n+1)^2$, présent dans les deux termes :

$$\sum_{k=1}^{n+1} k^3 = (n+1)^2\left[\frac{n^2}{4} + (n+1)\right] = (n+1)^2 \times \frac{n^2 + 4n + 4}{4} = \frac{(n+1)^2\,(n+2)^2}{4} = \left(\frac{(n+1)(n+2)}{2}\right)^{\! 2},$$

la troisième égalité utilisant l’identité remarquable $n^2 + 4n + 4 = (n+2)^2$. C’est exactement $\mathcal{P}(n+1)$.

Conclusion. Par récurrence :

$$\boxed{\ \forall n \in \mathbb{N}^*, \quad \sum_{k=1}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^{\! 2}\ }$$

Le jugement. La récurrence exige de connaître la formule avant de commencer : ici l’énoncé la fournissait, et sans lui il aurait fallu la deviner sur les premiers cas ($1$, $9$, $36$, $100$ : les carrés de $1$, $3$, $6$, $10$, les nombres triangulaires). Le télescopage du corrigé, lui, n’a besoin de rien deviner : il construit le résultat en chemin. Avantage télescopage, donc ? Pas si vite. La récurrence a pour elle d’être un gabarit universel : la même trame, mot pour mot, démontre les formules des sommes de $k^2$, de $k^4$, de $k^5$, quand chaque télescopage exige de dénicher une identité sur mesure (celle de la question 2, qui ne tombe pas du ciel). Le télescopage découvre, la récurrence certifie et se transporte : deux outils, deux vertus, et un mathématicien complet garde les deux dans sa trousse.

Défi de l’exercice 31 : jusqu’où reculer le premier contre-exemple ?

L’exercice avait montré que l’affirmation « $\frac{n^{10}}{1{,}5^{\,n}} \geqslant 1$ pour tout $n \geqslant 2$ », vraie jusqu’à $n = 100$, tombe en $n = 118$. Le défi demandait : en augmentant l’exposant, jusqu’où faut-il aller pour que le premier contre-exemple dépasse le million ? Et pour qu’il dépasse ce que votre machine sait calculer ?

La croissance du premier contre-exemple. Notons $n_0(p)$ le premier entier $n \geqslant 2$ tel que $n^p < 1{,}5^{\,n}$. Le calcul (mené en arithmétique entière exacte, en comparant $n^p \times 2^n$ à $3^n$, ce qui évite tout arrondi) donne :

exposant $p$	$10$	$20$	$50$	$100$	$1\,000$
premier contre-exemple $n_0(p)$	$118$	$278$	$829$	$1\,857$	$24\,973$

Le million. La réponse exacte : le plus petit exposant qui repousse le premier contre-exemple au-delà du million est

$$\boxed{\ p = 29\,349, \quad \text{avec } n_0(29\,349) = 1\,000\,017\ }$$

Pour $p = 29\,348$, le contre-exemple arrive en $n_0 = 999\,981$ : à un cheveu sous le million. Ces valeurs ne sortent pas d’un chapeau : le basculement a lieu au premier $n$ où $n \ln 1{,}5$ dépasse $p \ln n$, ce qui donne l’estimation $p \approx \dfrac{10^6 \ln 1{,}5}{\ln 10^6} \approx 29\,348{,}5$, que la vérification exacte confirme.

Au-delà de la machine. Il y a deux murs, et il est instructif de les distinguer.

Le premier est un mur de représentation. Le programme naïf de l’exercice calcule $1{,}5^{\,n}$ en nombres flottants ; or un flottant plafonne aux alentours de $1{,}8 \times 10^{308}$, et $1{,}5^{\,n}$ franchit ce plafond dès $n = 1\,751$. Pour $p = 29\,349$, le programme naïf meurt donc à $n = 1\,751$, à des années-lumière du contre-exemple qu’il cherchait vers le million. Le remède est un changement d’écriture, pas de machine : comparer les logarithmes ($p \ln n$ contre $n \ln 1{,}5$, deux nombres qui restent minuscules), ou travailler en entiers exacts comme ci-dessus. Bien écrit, le même ordinateur atteint le million en quelques secondes.

Le second mur est un mur de temps, et lui ne cède pas. Même en logarithmes, la boucle doit visiter tous les entiers jusqu’à $n_0(p)$, et $n_0(p)$ grandit sans limite avec $p$ : pour $p = 10^9$, le premier contre-exemple se situe vers $n \approx 6 \times 10^{10}$, soit soixante milliards de tours de boucle ; prenez $p$ plus grand encore et vous placez le témoin au-delà de tout budget de calcul, quel qu’il soit. Il n’existe aucun exposant qui supprime le contre-exemple : l’exponentielle finit toujours par écraser la puissance (c’est le théorème des croissances comparées, démontré au chapitre F1). Mais il existe des exposants qui le placent hors de portée de toute machine, présente ou future. C’est la leçon de l’exercice, poussée à sa limite : l’ordinateur réfute quand on lui montre où chercher, et il démontre d’autant moins que l’infini commence toujours après sa dernière itération.

Sources

• Atelier A1, exercices 20, 22 et 31, encadrés « défi » ; corrigé de l’Atelier A1 (télescopage de l’exercice 22, contre-exemple $n = 118$ de l’exercice 31, paragraphe « Défi » de l’exercice 11).
• Les valeurs numériques de cette page ($n_0(p)$ pour $p$ de $10$ à $1\,000$, le seuil $p = 29\,349$ et $n_0 = 1\,000\,017$, le plafond flottant $n = 1\,751$, l’ordre de grandeur $6 \times 10^{10}$ pour $p = 10^9$) ont été recalculées par programme pour cette page, les valeurs charnières étant certifiées en arithmétique entière exacte.