Preuve par récurrence simple

Bonjour,

Dans notre leçon précédente, nous avons ajouté à notre boîte à outils la preuve par contraposée et la preuve par l'absurde. Ces méthodes de raisonnement indirect sont essentielles pour aborder des problèmes où une preuve directe serait fastidieuse, voire impossible.

Aujourd'hui, nous allons étudier une technique de preuve d'une nature différente, mais tout aussi fondamentale, en particulier pour l'informatique : le raisonnement par récurrence. L'objectif est de vous rendre capable d'effectuer une preuve par récurrence simple sur les entiers naturels. Cette méthode est le pilier sur lequel reposent d'innombrables preuves de correction d'algorithmes et d'analyses de complexité, notamment pour les fonctions récursives. C'est un outil que vous utiliserez constamment.

1. Le Principe du Raisonnement par Récurrence

Le raisonnement par récurrence permet de démontrer qu'une propriété $P (n)$ est vraie pour tous les entiers naturels $n$ à partir d'un certain rang $n_{0}$ . L'intuition est souvent illustrée par l'analogie des dominos ou d'une échelle.

Pour vous familiariser avec ce principe, son intuition et sa mise en œuvre sur un premier exemple, je vous propose de visionner la vidéo suivante.

Tous les types de Récurrence expliqués

Cette vidéo de la chaîne Rayann Maths explique de manière très claire l'intuition derrière la récurrence (l'analogie de l'échelle) et déroule une première démonstration complète.

Regardez le début de la vidéo, de 00:00 à 04:23. Concentrez-vous sur : La motivation : pourquoi un exemple ne suffit pas à prouver une propriété générale. L'analogie de l'échelle infinie. Les deux étapes clés : l'initialisation et l'hérédité. La manière dont la démonstration sur l'exemple 8^n-1 est structurée selon ces deux étapes.

La vidéo a formalisé la méthode, qui se décompose en trois parties immuables :

Initialisation (ou Cas de base) : On prouve que la propriété $P (n_{0})$ est vraie pour le premier entier concerné (souvent $n_{0} = 0$ ou $n_{0} = 1$ ). C'est la première marche de l'échelle.
Hérédité (ou Étape de récurrence) : On suppose que la propriété est vraie pour un certain rang $k \geq n_{0}$ quelconque. Cette supposition s'appelle l'hypothèse de récurrence (HR). À partir de cette hypothèse, on démontre que la propriété est alors nécessairement vraie pour le rang suivant, $k + 1$ . On prouve donc l'implication $P (k) \Rightarrow P (k + 1)$ . C'est le fait de savoir passer d'une marche à la suivante.
Conclusion : Si l'initialisation et l'hérédité sont vérifiées, on conclut que la propriété $P (n)$ est vraie pour tout entier $n \geq n_{0}$ .

L'image ci-dessous synthétise ce processus.

Principe du raisonnement par récurrence — Cette illustration résume les trois étapes du raisonnement par récurrence : l'Initialisation qui ancre la preuve, l'Hérédité qui assure la transmission de la propriété, et la Conclusion qui généralise à tous les entiers concernés.

Vous vous demandez peut-être pourquoi cette méthode est valide. Elle repose en fait sur les axiomes qui définissent l'ensemble des entiers naturels (les axiomes de Peano). Le principe de récurrence est lui-même un axiome ou peut être démontré à partir d'un principe équivalent, le "principe du bon ordre" (Well-Ordering Principle), qui affirme que toute partie non vide de $N$ admet un plus petit élément. La preuve se fait alors par l'absurde, en se connectant à notre leçon précédente.

Démonstration du Principe de Récurrence — Cette image présente une preuve par contradiction du principe de récurrence. Elle illustre comment l'existence d'un "plus petit contre-exemple" mène à une contradiction, validant ainsi le principe lui-même.

2. Mise en Pratique : Propriété Arithmétique

Appliquons cette structure à un exemple classique.

Récurrence et Récursivité à l'interface des Mathématiques et de l'Informatique

Le document suivant, issu de la revue Bibnum, formalise le schéma de récurrence et propose un exemple de preuve de divisibilité très détaillé.

Lisez la section 1.1 "Récurrence" (page 47). Concentrez-vous sur le "schéma de récurrence classique" et suivez attentivement l'Exemple 1 : "Démontrons par récurrence que, pour tout n ∈ N, 4n − 1 est divisible par 3".

Analysons ensemble la structure de cette preuve :

Propriété $P (n)$ : " $4^{n} - 1$ est divisible par 3 ".
Initialisation ( $n = 0$ ) : On vérifie $P (0)$ . $4^{0} - 1 = 1 - 1 = 0$ . Comme $0 = 3 \times 0$ , 0 est divisible par 3. $P (0)$ est vraie.
Hérédité :
- Hypothèse de récurrence (HR) : Supposons que $P (k)$ est vraie pour un entier $k \geq 0$ . Cela signifie qu'il existe un entier $m$ tel que $4^{k} - 1 = 3 m$ .
- Objectif : Montrer que $P (k + 1)$ est vraie, c'est-à-dire que $4^{k + 1} - 1$ est divisible par 3.
- Démonstration : On manipule l'expression de $P (k + 1)$ pour faire apparaître l'expression de $P (k)$ et utiliser l'hypothèse. $4^{k + 1} - 1 = 4 \cdot 4^{k} - 1$ De l'HR, on sait que $4^{k} = 3 m + 1$ . On substitue : $4^{k + 1} - 1 = 4 (3 m + 1) - 1 = 12 m + 4 - 1 = 12 m + 3 = 3 (4 m + 1)$ Cette expression est un multiple de 3. Donc $P (k + 1)$ est vraie.
Conclusion : Par le principe de récurrence, la propriété est vraie pour tout entier naturel $n$ .

3. Application à l'Analyse d'Algorithmes : Formules de Sommation

La preuve de formules de sommation est une application directe et très fréquente en informatique, notamment pour calculer la complexité d'une boucle.

Proof by Induction

Ce document du professeur Jeff Erickson est une référence sur le sujet. Bien qu'en anglais, la clarté de sa démonstration mathématique est universelle. Nous allons nous pencher sur un exemple de sommation.

Lisez la section 5, "Summations" (pages 10-12). Suivez la démonstration pour la somme des puissances de 3. Notez comment il sépare le cas de base (n=0) de l'étape inductive (n>=1) et comment l'étape inductive utilise le résultat pour n-1. Lisez ensuite le résumé des 4 étapes pour "découvrir" une preuve par récurrence à la fin de la section 3 (page 7). C'est une excellente méthode de travail.

La méthode de découverte de preuve proposée par Erickson est particulièrement efficace :

Écrire le squelette (Boilerplate) : Posez la structure (Initialisation, Hérédité avec l'HR, Conclusion) sans réfléchir.
Penser "grand" : Ne vous perdez pas dans les petits nombres. Concentrez-vous sur l'étape d'hérédité. Comment pouvez-vous ramener le problème pour $n$ à un problème pour une ou plusieurs valeurs plus petites que $n$ (typiquement $n - 1$ ) ? C'est le cœur de la réflexion.
Chercher les "trous" : Identifiez les cas où votre raisonnement inductif ne s'applique pas. Ces cas deviendront vos cas de base. (Dans l'exemple des sommes, le raisonnement pour $n$ s'appuie sur $n - 1$ , ce qui ne fonctionne pas pour $n = 0$ car $- 1$ n'est pas un entier naturel. Donc, $n = 0$ doit être un cas de base).
Réécrire : Mettez la preuve au propre, en commençant par les cas de base puis l'étape inductive.

4. De la Théorie à la Pratique : Prouver la Correction d'un Algorithme

Le lien entre récurrence et informatique devient évident lorsque l'on veut prouver formellement qu'un algorithme fait bien ce qu'on attend de lui. Pour une boucle, on utilise un invariant de boucle, une propriété qui est vraie avant la boucle, et qui reste vraie après chaque itération. La preuve qu'une propriété est un invariant de boucle se fait... par récurrence !

Terminaison et Invariant de boucle - Algorithmique

Cette vidéo de Cédric Gerland illustre parfaitement ce lien en montrant comment on utilise la récurrence pour prouver un invariant de boucle dans un algorithme simple de recherche de maximum.

Regardez l'extrait de 04:39 à 07:22. Observez comment la preuve de l'invariant se déroule en deux temps : Initialisation : La propriété est vraie avant d'entrer dans la boucle. Conservation (Hérédité) : Si la propriété est vraie à l'étape i, elle reste vraie à l'étape i+1.

5. Exercice d'Application

Prouvez par récurrence que pour tout entier $n \geq 1$ , la somme des $n$ premiers entiers impairs est égale à $n^{2}$ .

i = 1 \sum n (2 i - 1) = n^{2}

Prenez le temps de bien rédiger la preuve en suivant la structure en trois étapes.

Cliquez ici pour voir la solution.

Démonstration par récurrence :

Soit $P (n)$ la proposition : $\sum_{i = 1}^{n} (2 i - 1) = n^{2}$ .

Initialisation : Nous devons vérifier que $P (1)$ est vraie.
Pour $n = 1$ , le membre de gauche est $\sum_{i = 1}^{1} (2 i - 1) = 2 (1) - 1 = 1$ .
Le membre de droite est $1^{2} = 1$ .
Les deux membres sont égaux, donc $P (1)$ est vraie.
Hérédité : Supposons que $P (k)$ est vraie pour un certain entier $k \geq 1$ . C'est notre hypothèse de récurrence (HR).
HR : $\sum_{i = 1}^{k} (2 i - 1) = k^{2}$ .

Nous devons montrer que $P (k + 1)$ est vraie, c'est-à-dire : $\sum_{i = 1}^{k + 1} (2 i - 1) = (k + 1)^{2}$ .

Partons du membre de gauche de l'égalité pour $P (k + 1)$ et essayons de faire apparaître l'hypothèse de récurrence :
$i = 1 \sum k + 1 (2 i - 1) = (i = 1 \sum k (2 i - 1)) + (2 (k + 1) - 1)$
On reconnaît dans la parenthèse le membre de gauche de notre HR. On peut donc le remplacer par $k^{2}$ :
$i = 1 \sum k + 1 (2 i - 1) = k^{2} + (2 (k + 1) - 1)$
Simplifions l'expression :
$k^{2} + (2 k + 2 - 1) = k^{2} + 2 k + 1$
Nous reconnaissons une identité remarquable :
$k^{2} + 2 k + 1 = (k + 1)^{2}$
Nous avons ainsi montré que $\sum_{i = 1}^{k + 1} (2 i - 1) = (k + 1)^{2}$ , ce qui est exactement la proposition $P (k + 1)$ . L'hérédité est établie.
Conclusion : Puisque $P (1)$ est vraie et que l'hérédité est vérifiée, nous pouvons conclure par le principe de récurrence que $P (n)$ est vraie pour tout entier $n \geq 1$ .

Conclusion

Le raisonnement par récurrence est un outil indispensable. Sa maîtrise est une étape non négociable dans votre préparation.

Points clés à retenir :

Une preuve par récurrence se structure impérativement en trois temps : initialisation, hérédité et conclusion.
L'étape d'hérédité consiste à prouver une implication : on suppose $P (k)$ (l'hypothèse de récurrence) pour en déduire $P (k + 1)$ .
La récurrence est le mécanisme naturel pour prouver des propriétés sur des suites, des sommes, mais aussi et surtout, la correction des algorithmes (via les invariants de boucle) et des fonctions récursives.

Dans la prochaine leçon, nous verrons une variante de ce raisonnement, la récurrence forte, où l'hypothèse de récurrence est plus puissante. Cela nous permettra de prouver des propriétés où le cas $n + 1$ dépend non seulement du cas $n$ , mais potentiellement de tous les cas précédents.

Recommended resources