01 · Preuve par récurrence¶
Intuition
Vous voulez montrer qu'une propriété est vraie pour tous les entiers naturels. Il y en a une infinité : les vérifier un par un est impossible.
L'idée de la récurrence est celle de l'échelle. Si vous savez :
- monter sur le premier barreau, et
- que de n'importe quel barreau vous pouvez passer au suivant,
alors vous pouvez atteindre n'importe quel barreau, aussi haut soit-il. Vous n'avez pas eu besoin de vérifier chaque barreau — deux affirmations ont suffi à en couvrir une infinité.
C'est aussi l'image des dominos : on pousse le premier, et on a garanti que chacun fait tomber son voisin.
1. Le principe¶
Principe de récurrence
Soit \(P(n)\) une propriété dépendant d'un entier \(n\), et \(n_0 \in \mathbb{N}\).
Si
- (Initialisation) \(P(n_0)\) est vraie, et
- (Hérédité) pour tout \(n \geqslant n_0\), \(P(n) \implies P(n+1)\),
alors \(P(n)\) est vraie pour tout entier \(n \geqslant n_0\).
Ce qu'il faut comprendre dans l'hérédité. On ne démontre pas \(P(n+1)\). On démontre l'implication \(P(n) \implies P(n+1)\). C'est beaucoup plus faible, et c'est ce qui rend la chose possible : on a le droit de supposer \(P(n)\) vraie — c'est l'hypothèse de récurrence — pour en déduire \(P(n+1)\).
Les deux étapes sont indispensables
Sans initialisation, l'hérédité ne sert à rien. Considérons \(P(n)\) : « \(n = n+1\) ». Elle est parfaitement héréditaire : si \(n = n+1\), alors en ajoutant 1 des deux côtés, \(n+1 = n+2\). Mais elle n'est vraie pour aucun entier, car \(P(0)\) est fausse. L'échelle est solide, mais personne ne monte dessus.
Sans hérédité, l'initialisation ne dit rien au-delà du premier cas.
2. La rédaction¶
Une récurrence bien rédigée suit toujours le même moule. Respectez-le : les correcteurs y cherchent des points précis.
Soit \(P(n)\) la propriété : « … ». (énoncer la propriété explicitement, avec \(n\) dedans)
Initialisation. Pour \(n = n_0\) : … Donc \(P(n_0)\) est vraie.
Hérédité. Soit \(n \geqslant n_0\). Supposons \(P(n)\) vraie, c'est-à-dire « … ». Montrons \(P(n+1)\), c'est-à-dire « … ». (calcul, en faisant apparaître l'hypothèse de récurrence) Donc \(P(n+1)\) est vraie.
Conclusion. Par principe de récurrence, \(P(n)\) est vraie pour tout \(n \geqslant n_0\). \(\blacksquare\)
Les quatre fautes de rédaction qui coûtent des points
- Ne pas énoncer \(P(n)\). Le correcteur doit savoir ce que vous démontrez.
- Écrire « supposons \(P(n)\) vraie pour tout \(n\) ». Non : on suppose \(P(n)\) vraie pour un \(n\) fixé. Supposer pour tout \(n\), c'est supposer ce qu'on veut démontrer.
- Ne pas écrire ce qu'est \(P(n+1)\) avant de le démontrer. Sans cible explicite, on ne sait pas où l'on va.
- Ne pas signaler où l'hypothèse de récurrence est utilisée. Si elle ne sert nulle part, c'est que la récurrence était inutile — ou que la preuve est fausse.
3. Récurrence sur une somme — le cas type¶
Proposition. Pour tout \(n \in \mathbb{N}^*\) :
Démonstration.
Soit \(P(n)\) : « \(\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}\) ».
Initialisation. Pour \(n=1\) : le membre de gauche vaut \(1\), le membre de droite \(\frac{1 \times 2}{2} = 1\). Donc \(P(1)\) est vraie.
Hérédité. Soit \(n \geqslant 1\). Supposons \(P(n)\), c'est-à-dire \(\sum_{k=1}^{n} k = \frac{n(n+1)}{2}\). Montrons que \(\sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2}\).
On isole le dernier terme :
On factorise par \((n+1)\) :
C'est bien \(P(n+1)\).
Conclusion. Par récurrence, la formule est vraie pour tout \(n \geqslant 1\). \(\blacksquare\)
La technique universelle pour les sommes
Isoler le dernier terme pour faire apparaître la somme jusqu'à \(n\), puis appliquer l'hypothèse de récurrence, puis factoriser pour retrouver la forme attendue en \(n+1\).
Un réflexe utile : écrivez d'abord la cible \(\frac{(n+1)(n+2)}{2}\) sur le côté de votre feuille. Vous saurez vers quoi manœuvrer.
4. Récurrence sur une inégalité¶
Proposition (inégalité de Bernoulli). Pour tout réel \(x \geqslant -1\) et tout \(n \in \mathbb{N}\) :
Démonstration.
Soit \(P(n)\) : « \((1+x)^n \geqslant 1+nx\) » (à \(x \geqslant -1\) fixé).
Initialisation. \(n=0\) : \((1+x)^0 = 1\) et \(1 + 0 \cdot x = 1\). L'inégalité \(1 \geqslant 1\) est vraie.
Hérédité. Supposons \((1+x)^n \geqslant 1+nx\). Comme \(x \geqslant -1\), on a \(1 + x \geqslant 0\) : on peut multiplier l'inégalité par \(1+x\) sans en changer le sens.
Développons le membre de droite :
Par transitivité, \((1+x)^{n+1} \geqslant 1+(n+1)x\). \(\blacksquare\)
Le point délicat des récurrences sur les inégalités
La multiplication par \((1+x)\) n'est licite que parce que \(1+x \geqslant 0\). C'est exactement là que sert l'hypothèse \(x \geqslant -1\), et un correcteur vérifie ce point précis. Une récurrence sur une inégalité échoue presque toujours à cet endroit : on multiplie ou on divise par une quantité dont on n'a pas justifié le signe.
5. Récurrence sur la divisibilité¶
Proposition. Pour tout \(n \in \mathbb{N}\), \(7^n - 1\) est divisible par 6.
Démonstration.
Soit \(P(n)\) : « il existe \(k \in \mathbb{Z}\) tel que \(7^n - 1 = 6k\) ».
Initialisation. \(7^0 - 1 = 0 = 6 \times 0\). ✓
Hérédité. Supposons \(7^n - 1 = 6k\) pour un certain entier \(k\), c'est-à-dire \(7^n = 6k+1\). Alors
Comme \(7k+1 \in \mathbb{Z}\), \(P(n+1)\) est vraie. \(\blacksquare\)
Le réflexe divisibilité
Traduire « \(a\) divise \(b\) » par « \(b = ak\) avec \(k\) entier », poser cette écriture, puis manipuler algébriquement. C'est ce qui transforme un énoncé arithmétique en un calcul littéral, et c'est la méthode standard qu'on retrouvera au chapitre 11.
6. Variantes du principe¶
6.1 Récurrence forte¶
Parfois, \(P(n+1)\) ne se déduit pas de \(P(n)\) seule, mais de tous les cas précédents.
Principe de récurrence forte
Si \(P(n_0)\) est vraie et si, pour tout \(n \geqslant n_0\),
alors \(P(n)\) est vraie pour tout \(n \geqslant n_0\).
Quand l'utiliser : suites définies par \(u_{n+1} = f(u_n, u_{n-1})\), propriétés de décomposition (tout entier \(\geqslant 2\) admet un diviseur premier), analyse d'algorithmes récursifs qui découpent en deux moitiés.
6.2 Récurrence double¶
Cas particulier de la récurrence forte, adapté aux suites du type \(u_{n+2} = a u_{n+1} + b u_n\) : on initialise sur deux rangs consécutifs (\(n_0\) et \(n_0+1\)), et l'hérédité suppose \(P(n)\) et \(P(n+1)\) pour obtenir \(P(n+2)\).
Deux initialisations, pas une
C'est l'erreur classique sur les suites de Fibonacci et assimilées. Avec une seule initialisation, l'hérédité ne peut jamais démarrer : elle a besoin de deux rangs.
6.3 Récurrence descendante et récurrence finie¶
On peut aussi démontrer une propriété pour \(n\) allant de \(n_0\) à \(N\) (récurrence finie), ou raisonner vers le bas. Ces variantes sont plus rares au niveau du S1.
Exemples traités¶
Exemple 1 — Somme des carrés
Montrer que pour tout \(n \geqslant 1\) : \(\displaystyle\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\).
Soit \(P(n)\) cette égalité.
Initialisation. \(n=1\) : gauche \(=1\), droite \(=\frac{1\times2\times3}{6}=1\) ✓
Hérédité. Supposons \(P(n)\).
Il reste à factoriser \(2n^2+7n+6\). Racine évidente ? Testons \(n=-2\) : \(8-14+6 = 0\) ✓. Donc \(-2\) est racine, et le produit des racines vaut \(\frac{6}{2}=3\), d'où l'autre racine \(= -\frac32\). Ainsi
Finalement
C'est bien \(P(n+1)\). \(\blacksquare\)
Exemple 2 — Une suite définie par récurrence
Soit \((u_n)\) définie par \(u_0 = 2\) et \(u_{n+1} = 3u_n - 2\). Montrer que \(u_n = 3^n + 1\) pour tout \(n\).
Initialisation. \(u_0 = 2\) et \(3^0+1 = 2\) ✓
Hérédité. Supposons \(u_n = 3^n+1\). Alors
C'est \(P(n+1)\). \(\blacksquare\)
Comment on trouve la formule
On cherche le point fixe : \(\ell = 3\ell - 2\) donne \(\ell = 1\). Puis on pose \(v_n = u_n - 1\), qui vérifie \(v_{n+1} = 3v_n\) : c'est une suite géométrique de raison 3 et de premier terme \(v_0 = 1\), donc \(v_n = 3^n\), donc \(u_n = 3^n+1\).
La récurrence vérifie la formule ; elle ne la trouve pas. C'est une distinction importante : une preuve par récurrence suppose qu'on connaît déjà le résultat.
Exemple 3 — Récurrence forte
Montrer que tout entier \(n \geqslant 2\) admet un diviseur premier.
Soit \(P(n)\) : « \(n\) admet un diviseur premier ».
Initialisation. \(n=2\) : \(2\) est premier et se divise lui-même ✓
Hérédité forte. Soit \(n \geqslant 2\) et supposons \(P(m)\) vraie pour tout \(m\) avec \(2 \leqslant m \leqslant n\). Considérons \(n+1\).
- Cas 1 : \(n+1\) est premier. Alors il est son propre diviseur premier ✓
- Cas 2 : \(n+1\) n'est pas premier. Alors il s'écrit \(n+1 = ab\) avec \(2 \leqslant a \leqslant n\). Par hypothèse de récurrence forte, \(a\) admet un diviseur premier \(p\). Comme \(p \mid a\) et \(a \mid n+1\), on a \(p \mid n+1\) ✓
\(\blacksquare\)
Pourquoi la récurrence simple ne marche pas ici
\(P(n)\) ne dit rien sur \(n+1\) : connaître un diviseur premier de \(n\) n'aide en rien pour \(n+1\). Il faut pouvoir invoquer \(P(a)\) pour un \(a\) arbitrairement plus petit — c'est exactement ce que la récurrence forte autorise.
Exemple 4 — Une récurrence fausse, à débusquer
« Théorème » : dans tout ensemble de \(n\) chevaux, tous les chevaux ont la même couleur.
Initialisation. \(n=1\) : un seul cheval, il a bien sa propre couleur ✓
« Hérédité ». Soit un ensemble de \(n+1\) chevaux \(\{c_1, \dots, c_{n+1}\}\). Les \(n\) premiers ont la même couleur par hypothèse de récurrence ; les \(n\) derniers aussi. Comme les deux groupes se chevauchent, tous ont la même couleur.
Où est l'erreur ?
Réponse
Le passage de \(n=1\) à \(n=2\). Pour \(n+1 = 2\), les deux groupes sont \(\{c_1\}\) et \(\{c_2\}\) : ils ne se chevauchent pas. L'argument « comme les deux groupes se chevauchent » suppose implicitement \(n \geqslant 2\).
L'hérédité est donc valide pour \(n \geqslant 2\), mais l'initialisation est faite en \(n=1\) : la chaîne est rompue au premier maillon.
La morale : vérifiez toujours que l'hérédité fonctionne effectivement au rang d'initialisation, et pas seulement « en général ».
Erreurs fréquentes¶
| Erreur | Conséquence |
|---|---|
| Oublier l'initialisation | La preuve ne démontre rien |
| « Supposons \(P(n)\) vraie pour tout \(n\) » | Cercle vicieux : on suppose la conclusion |
| Ne pas utiliser l'hypothèse de récurrence | La récurrence est inutile, ou la preuve est fausse |
| Multiplier une inégalité sans justifier le signe | Le sens peut se retourner |
| Une seule initialisation pour une récurrence double | L'hérédité ne peut pas démarrer |
| Hérédité valide seulement à partir de \(n_0+1\) | Chaîne rompue (cf. les chevaux) |
Exercices¶
★ Exercice 1. Démontrer par récurrence que pour tout \(n \geqslant 1\) :
★ Exercice 2. Soit \((u_n)\) définie par \(u_0 = 1\) et \(u_{n+1} = 2u_n + 3\). Démontrer que \(u_n = 2^{n+2} - 3\) pour tout \(n \in \mathbb{N}\).
★★ Exercice 3. Démontrer que pour tout \(n \in \mathbb{N}\), \(4^n - 1\) est divisible par 3.
★★ Exercice 4. Démontrer que pour tout \(n \geqslant 1\) :
En déduire une relation remarquable entre \(\sum k^3\) et \(\sum k\).
★★ Exercice 5. Démontrer que pour tout \(n \geqslant 5\) : \(2^n > n^2\).
Attention à l'initialisation : à quel rang commence-t-on, et pourquoi pas avant ?
★★★ Exercice 6. Soit \((F_n)\) la suite de Fibonacci : \(F_0 = 0\), \(F_1 = 1\), et \(F_{n+2} = F_{n+1}+F_n\).
a) Démontrer par récurrence double que \(F_1 + F_2 + \dots + F_n = F_{n+2} - 1\). b) Démontrer que \(F_{n+1}F_{n-1} - F_n^2 = (-1)^n\) pour \(n \geqslant 1\) (identité de Cassini).
★★★ Exercice 7. Démontrer que pour tout \(n \geqslant 1\) :
En déduire que la suite des sommes partielles est majorée par 2.
★★★ Exercice 8 — lien informatique. On considère l'algorithme suivant, qui calcule \(x^n\) par exponentiation rapide :
def puissance(x, n):
if n == 0:
return 1
if n % 2 == 0:
y = puissance(x, n // 2)
return y * y
return x * puissance(x, n - 1)
a) Démontrer par récurrence forte que puissance(x, n) renvoie bien \(x^n\) pour
tout \(n \in \mathbb{N}\).
b) Soit \(C(n)\) le nombre de multiplications effectuées. Montrer par récurrence
forte que \(C(n) \leqslant 2\log_2(n+1)\) pour tout \(n \geqslant 1\).
Indication : traitez séparément \(n\) pair et \(n\) impair.
★★★★ Exercice 9. Soit \(n \in \mathbb{N}^*\). On dispose d'un échiquier \(2^n \times 2^n\) dont une case a été retirée. Démontrer qu'on peut le paver entièrement avec des triminos en forme de L (trois cases formant un coin).
Indication : récurrence sur \(n\), en découpant le carré en quatre quadrants.
★★★★ Exercice 10. Trouver l'erreur dans la « démonstration » suivante.
« Théorème ». Pour tout \(n \geqslant 1\) : \(\displaystyle\sum_{k=1}^{n} k = \frac{n^2+n+2}{2}\).
Hérédité. Supposons la formule vraie au rang \(n\). Alors \(\displaystyle\sum_{k=1}^{n+1} k = \frac{n^2+n+2}{2} + (n+1) = \frac{n^2+3n+4}{2} = \frac{(n+1)^2+(n+1)+2}{2}\), ce qui est la formule au rang \(n+1\). La formule est donc vraie pour tout \(n\).
★★★★ Exercice 11. Soit \(P(n)\) une propriété. On suppose :
- \(P(1)\) est vraie ;
- pour tout \(n \geqslant 1\), \(P(n) \implies P(2n)\) ;
- pour tout \(n \geqslant 2\), \(P(n) \implies P(n-1)\).
Démontrer que \(P(n)\) est vraie pour tout \(n \geqslant 1\).
C'est le schéma de la « récurrence de Cauchy », utilisé pour démontrer l'inégalité arithmético-géométrique.
Corrigés¶
Corrigé — Exercice 1
Soit \(P(n)\) : « \(\sum_{k=1}^{n}(2k-1) = n^2\) ».
Initialisation. \(n=1\) : gauche \(= 2\times1-1 = 1\), droite \(=1\) ✓
Hérédité. Supposons \(P(n)\). Alors
C'est \(P(n+1)\). \(\blacksquare\)
Interprétation : la somme des \(n\) premiers impairs vaut \(n^2\). Visuellement, on construit un carré de côté \(n+1\) à partir d'un carré de côté \(n\) en ajoutant une équerre de \(2n+1\) cases.
Corrigé — Exercice 2
Soit \(P(n)\) : « \(u_n = 2^{n+2}-3\) ».
Initialisation. \(u_0 = 1\) et \(2^2 - 3 = 1\) ✓
Hérédité. Supposons \(u_n = 2^{n+2}-3\). Alors
✓ \(\blacksquare\)
Corrigé — Exercice 3
Soit \(P(n)\) : « \(\exists k \in \mathbb{Z},\ 4^n-1 = 3k\) ».
Initialisation. \(4^0-1 = 0 = 3\times0\) ✓
Hérédité. Supposons \(4^n = 3k+1\). Alors
avec \(4k+1 \in \mathbb{Z}\) ✓ \(\blacksquare\)
Généralisation
Le même calcul montre que \(a^n - 1\) est divisible par \(a-1\) pour tout entier \(a \geqslant 2\). C'est aussi une conséquence directe de la factorisation \(a^n - b^n = (a-b)(\dots)\) vue au chapitre Prérequis 02 — la récurrence n'était pas indispensable, mais elle est plus courte à rédiger.
Corrigé — Exercice 4
Soit \(P(n)\) : « \(\sum_{k=1}^{n}k^3 = \left(\frac{n(n+1)}{2}\right)^2\) ».
Initialisation. \(n=1\) : gauche \(=1\), droite \(=1^2=1\) ✓
Hérédité. Supposons \(P(n)\).
✓ \(\blacksquare\)
Relation remarquable. Comme \(\sum_{k=1}^n k = \frac{n(n+1)}{2}\), on a
La somme des cubes est le carré de la somme. Pour \(n=3\) : \(1+8+27 = 36 = 6^2 = (1+2+3)^2\) ✓
Corrigé — Exercice 5
Soit \(P(n)\) : « \(2^n > n^2\) ».
Initialisation. \(n=5\) : \(32 > 25\) ✓
Pourquoi pas avant ? \(n=2\) : \(4 = 4\), faux (inégalité stricte). \(n=3\) : \(8 < 9\), faux. \(n=4\) : \(16 = 16\), faux. La propriété n'est effectivement vraie qu'à partir de \(n=5\).
Hérédité. Soit \(n \geqslant 5\) et supposons \(2^n > n^2\). Alors
Il suffit donc de montrer \(2n^2 \geqslant (n+1)^2\) pour \(n \geqslant 5\).
Pour \(n \geqslant 5\), \((n-1)^2 \geqslant 16 > 2\), donc \(2n^2 > (n+1)^2\).
Par transitivité : \(2^{n+1} > 2n^2 > (n+1)^2\) ✓ \(\blacksquare\)
Le schéma des récurrences sur inégalités
On majore ou minore en deux temps : d'abord on applique l'hypothèse de récurrence, ensuite on démontre une inégalité auxiliaire purement algébrique. Cette seconde étape est souvent le vrai travail.
Corrigé — Exercice 6
a) Soit \(P(n)\) : « \(\sum_{k=1}^{n}F_k = F_{n+2}-1\) ».
Une récurrence simple suffit ici.
Initialisation. \(n=1\) : gauche \(=F_1 = 1\) ; droite \(= F_3 - 1\). Or \(F_2 = 1\), \(F_3 = F_2+F_1 = 2\), donc droite \(= 1\) ✓
Hérédité. Supposons \(P(n)\).
en utilisant la relation de Fibonacci. ✓ \(\blacksquare\)
b) Soit \(P(n)\) : « \(F_{n+1}F_{n-1} - F_n^2 = (-1)^n\) », \(n \geqslant 1\).
Initialisation. \(n=1\) : \(F_2F_0 - F_1^2 = 1\times0 - 1 = -1 = (-1)^1\) ✓
Hérédité. Supposons \(P(n)\). On veut \(F_{n+2}F_n - F_{n+1}^2 = (-1)^{n+1}\).
En remplaçant \(F_{n+2} = F_{n+1}+F_n\) :
En remplaçant maintenant \(F_n = F_{n+1} - F_{n-1}\) dans le premier terme :
✓ \(\blacksquare\)
Identité de Cassini
Elle admet une lecture matricielle élégante. En posant \(\mathbf{A} = \begin{pmatrix}1&1\\1&0\end{pmatrix}\), on montre que \(\mathbf{A}^n = \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}\), et Cassini n'est alors que \(\det(\mathbf{A}^n) = (\det \mathbf{A})^n = (-1)^n\). On y reviendra au chapitre 07 sur le déterminant.
Corrigé — Exercice 7
Soit \(P(n)\) : « \(\sum_{k=1}^{n}\frac{1}{k^2} \leqslant 2 - \frac1n\) ».
Initialisation. \(n=1\) : gauche \(=1\), droite \(=2-1=1\). On a bien \(1 \leqslant 1\) ✓
Hérédité. Supposons \(P(n)\). Alors
Il suffit de montrer que \(-\frac1n + \frac{1}{(n+1)^2} \leqslant -\frac{1}{n+1}\), c'est-à-dire
Ce qui est vrai car \(n(n+1) \leqslant (n+1)^2\) (puisque \(n \leqslant n+1\)), et les deux quantités sont positives — l'inverse renverse l'inégalité. ✓ \(\blacksquare\)
Conclusion. Pour tout \(n\), \(\sum_{k=1}^n \frac{1}{k^2} \leqslant 2 - \frac1n < 2\). La suite des sommes partielles est croissante et majorée par 2, donc convergente.
La vraie valeur
Cette série converge vers \(\frac{\pi^2}{6} \approx 1{,}6449\) — c'est le problème de Bâle, résolu par Euler en 1735. La majoration par 2 obtenue ici est correcte mais grossière ; elle suffit à établir la convergence, ce qui est déjà l'essentiel.
Corrigé — Exercice 8
a) Soit \(P(n)\) : « puissance(x, n) renvoie \(x^n\) ».
Initialisation. \(n=0\) : la fonction renvoie 1, et \(x^0 = 1\) ✓
Hérédité forte. Soit \(n \geqslant 1\) et supposons \(P(m)\) vraie pour tout \(0 \leqslant m < n\).
- Si \(n\) est pair, \(n = 2q\) avec \(1 \leqslant q < n\). L'appel
puissance(x, n//2)renvoie \(x^q\) par hypothèse de récurrence forte, et la fonction renvoie \(x^q \times x^q = x^{2q} = x^n\) ✓ - Si \(n\) est impair, l'appel
puissance(x, n-1)renvoie \(x^{n-1}\) par hypothèse (\(n-1 < n\)), et la fonction renvoie \(x \cdot x^{n-1} = x^n\) ✓
\(\blacksquare\)
Pourquoi la récurrence forte est indispensable ici
Le cas pair fait appel au rang \(n/2\), qui peut être très éloigné de \(n-1\). Une récurrence simple, qui ne dispose que de \(P(n-1)\), ne permettrait pas de conclure.
b) Soit \(C(n)\) le nombre de multiplications. On a \(C(0) = 0\), et
Montrons \(P(n)\) : « \(C(n) \leqslant 2\log_2(n+1)\) » par récurrence forte, pour \(n \geqslant 1\).
Initialisation. \(n=1\) : impair, \(C(1) = C(0)+1 = 1\). Et \(2\log_2 2 = 2 \geqslant 1\) ✓
Hérédité forte. Soit \(n \geqslant 2\), hypothèse vraie en dessous.
- \(n\) pair, \(n = 2q\) : \(\displaystyle C(n) = C(q)+1 \leqslant 2\log_2(q+1) + 1\)
Or \(q+1 = \frac n2 + 1 \leqslant n+1\) pour \(n \geqslant 2\), et plus précisément \(q + 1 \leqslant \frac{n+1}{\sqrt2}\) dès que \(\frac n2 + 1 \leqslant \frac{n+1}{\sqrt2}\), ce qui est vrai pour \(n \geqslant 6\) ; les cas \(n = 2, 4\) se vérifient directement (\(C(2) = 2 \leqslant 2\log_2 3 \approx 3{,}17\) ✓, \(C(4) = 3 \leqslant 2\log_2 5 \approx 4{,}64\) ✓). Dans le cas général : \(\displaystyle 2\log_2(q+1)+1 \leqslant 2\left(\log_2(n+1) - \tfrac12\right)+1 = 2\log_2(n+1)\)
- \(n\) impair, \(n \geqslant 3\) : \(C(n) = C(n-1)+1\) avec \(n-1\) pair, donc \(C(n-1) = C\left(\frac{n-1}{2}\right)+1\) et \(C(n) = C\left(\frac{n-1}{2}\right)+2\). Comme \(\frac{n-1}{2}+1 = \frac{n+1}{2}\) : \(\displaystyle C(n) \leqslant 2\log_2\!\left(\frac{n+1}{2}\right) + 2 = 2\log_2(n+1) - 2 + 2 = 2\log_2(n+1)\)
\(\blacksquare\)
Interprétation. Calculer \(x^{1000}\) demande au plus \(2\log_2(1001) \approx 20\) multiplications, contre 999 pour la méthode naïve. C'est l'algorithme qui rend l'exponentiation modulaire — donc RSA — praticable ; on le retrouvera au chapitre 13.
Corrigé — Exercice 9
Soit \(P(n)\) : « tout échiquier \(2^n \times 2^n\) privé d'une case quelconque est pavable par des triminos en L ».
Initialisation. \(n=1\) : un carré \(2\times2\) privé d'une case laisse exactement trois cases en forme de L. Un seul trimino suffit ✓
Hérédité. Soit un échiquier \(2^{n+1}\times 2^{n+1}\) privé d'une case.
Découpons-le en quatre quadrants de taille \(2^n \times 2^n\). La case manquante se trouve dans exactement un de ces quadrants — appelons-le \(Q_1\). Par hypothèse de récurrence, \(Q_1\) est pavable.
Pour les trois autres quadrants, on place un trimino au centre de l'échiquier, occupant une case dans chacun d'eux — celle qui touche le centre. Chacun des trois quadrants est alors un carré \(2^n\times2^n\) privé d'une case, donc pavable par hypothèse de récurrence.
L'échiquier entier est pavé. ✓ \(\blacksquare\)
Pourquoi cette preuve est belle
Elle est constructive : elle ne dit pas seulement que le pavage existe, elle donne l'algorithme récursif qui le produit, en \(O(4^n)\) opérations — soit un temps linéaire en le nombre de cases.
Vérification de cohérence : un échiquier \(2^n\times2^n\) privé d'une case a \(4^n - 1\) cases, et \(4^n - 1\) est divisible par 3 (exercice 3 avec \(a=4\)). Le nombre de triminos est donc entier, ce qui était nécessaire.
Corrigé — Exercice 10
L'hérédité est correcte. Vérifions-la :
et
Les deux coïncident : l'implication \(P(n) \implies P(n+1)\) est bien démontrée.
L'erreur est l'absence d'initialisation. Testons \(n=1\) : la formule donnerait \(\frac{1+1+2}{2} = 2\), alors que \(\sum_{k=1}^{1}k = 1\). \(P(1)\) est fausse.
Et comme \(P(1)\) est fausse, \(P(2)\) l'est aussi, et ainsi de suite : la propriété est fausse pour tout \(n\), alors même qu'elle est parfaitement héréditaire.
La leçon
Une propriété héréditaire n'est pas une propriété vraie. C'est une propriété qui le serait si elle démarrait. La formule fautive est d'ailleurs la vraie formule décalée d'une constante : \(\frac{n^2+n}{2}+1\). L'hérédité ne voit pas les constantes additives — seule l'initialisation les détecte.
Corrigé — Exercice 11
Soit \(n \geqslant 1\) quelconque. Montrons \(P(n)\).
Étape 1 — atteindre une puissance de 2 au-dessus de \(n\). En partant de \(P(1)\) et en appliquant \(m\) fois la règle de doublement, on obtient \(P(2^m)\) pour tout \(m \in \mathbb{N}\) — c'est une récurrence simple immédiate sur \(m\).
Étape 2 — redescendre. Choisissons \(m\) assez grand pour que \(2^m \geqslant n\) (possible car \(2^m \to +\infty\)). On dispose de \(P(2^m)\).
En appliquant la règle de descente \(2^m - n\) fois, on obtient successivement \(P(2^m - 1)\), \(P(2^m-2)\), …, \(P(n)\). Formellement, c'est une récurrence finie descendante : la propriété « \(P(2^m - j)\) » se propage de \(j\) à \(j+1\) tant que \(2^m - j \geqslant 2\).
Donc \(P(n)\) est vraie. Comme \(n\) était quelconque, \(P\) est vraie partout. \(\blacksquare\)
Où ce schéma sert
C'est la structure de la démonstration originale de Cauchy pour l'inégalité arithmético-géométrique \(\displaystyle \frac{a_1+\dots+a_n}{n} \geqslant \sqrt[n]{a_1\cdots a_n}\)
L'inégalité est facile à établir pour \(n = 2\), puis à doubler (de \(n\) à \(2n\)), et enfin à redescendre. On l'appelle pour cette raison la récurrence de Cauchy ou récurrence en avant-arrière.
Chapitre suivant : Ensembles.