Induction mathématique
L'induction mathématique, également appelée raisonnement par récurrence, est une méthode de démonstration permettant de prouver qu'une propriété est vraie pour une infinité de valeurs entières. Elle est largement utilisée en mathématiques, mais également en informatique théorique, où elle constitue l'un des principaux outils servant à démontrer la validité d'un algorithme, la correction d'un programme ou la complexité d'une procédure récursive. Grâce à cette méthode, il est possible d'établir qu'une propriété est vraie pour tous les nombres naturels sans devoir vérifier individuellement chacun d'entre eux.
En programmation, l'induction mathématique intervient fréquemment dans l'analyse des algorithmes récursifs, les preuves de correction des structures de données, les démonstrations portant sur les arbres binaires, les graphes, les suites numériques ou encore les algorithmes de tri et de recherche. De nombreux ouvrages consacrés à l'algorithmique, notamment ceux de Donald Knuth ou de Thomas H. Cormen, utilisent abondamment cette méthode pour démontrer les propriétés des algorithmes étudiés.
Principe
L'induction mathématique repose sur une idée simple comparable à une rangée de dominos.
Si :
- le premier domino tombe ;
- chaque domino fait tomber le suivant ;
alors tous les dominos tomberont.
En mathématiques, cette idée est traduite par deux étapes fondamentales :
- le cas de base ;
- l'étape d'induction.
Si ces deux conditions sont satisfaites, la propriété est démontrée pour tous les entiers naturels appartenant au domaine considéré.
Le cas de base
La première étape consiste à démontrer que la propriété est vraie pour la première valeur.
Selon le problème étudié, cette valeur est généralement :
| n = 0 |
ou
| n = 1 |
Cette démonstration constitue le point de départ du raisonnement.
Sans ce premier cas, aucune conclusion ne peut être tirée.
L'hypothèse d'induction
La deuxième étape consiste à supposer que la propriété est vraie pour une certaine valeur n.
Cette supposition est appelée :
Hypothèse d'induction
Elle ne constitue pas une preuve.
Elle sert uniquement de point de départ pour démontrer le cas suivant.
L'étape d'induction
À partir de l'hypothèse précédente, on démontre que la propriété est également vraie pour :
| n + 1 |
Si cette démonstration est correcte, la propriété devient vraie pour toutes les valeurs suivantes.
Cette étape est le cour de l'induction mathématique.
Schéma général
Une démonstration par induction suit généralement le plan suivant :
|
Montrer que P(0) est vraie. Supposer P(n) vraie. Montrer que P(n+1) est vraie. Conclusion : P(n) est vraie pour tout entier naturel n. |
Exemple
Démontrons que :
|
1 + 2 + 3 + ... + n = n(n+1)/2 |
Cas de base
Pour :
| n = 1 |
on obtient :
|
1 = 1(1+1)/2 = 1 |
La propriété est vraie.
Hypothèse
On suppose maintenant que :
|
1+2+...+n = n(n+1)/2 |
Étape d'induction
Ajoutons :
| n+1 |
aux deux membres.
On obtient :
|
n(n+1)/2 + (n+1) |
En mettant :
| (n+1) |
en facteur :
|
(n+1) (n/2+1) |
soit :
| (n+1)(n+2)/2 |
qui correspond exactement à la formule pour :
| n+1 |
La propriété est donc démontrée.
Pourquoi est-elle importante ?
En informatique, il est souvent impossible de tester un algorithme avec toutes les valeurs possibles.
L'induction mathématique permet alors de démontrer qu'un programme fonctionne correctement pour toutes les tailles d'entrée.
Par exemple, elle est utilisée pour montrer que :
- un algorithme de tri trie toujours correctement ;
- une recherche récursive finit toujours par trouver un élément lorsqu'il existe ;
- une fonction récursive termine toujours son exécution ;
- une structure de données conserve ses propriétés après chaque modification.
Exemple en programmation
Considérons la fonction récursive suivante :
L'induction permet de démontrer que cette fonction retourne bien :
| n! |
pour tout entier naturel positif.
Le raisonnement est le suivant :
- le cas n = 1 est correct ;
- si la fonction est correcte pour n ? 1 ;
- alors elle est également correcte pour n.
Induction forte
Une variante appelée induction forte est également très utilisée.
Au lieu de supposer uniquement :
| P(n) |
on suppose vraies toutes les propriétés :
|
P(0) P(1) ... P(n) |
Cette méthode est particulièrement utile pour démontrer des propriétés concernant :
- les nombres premiers ;
- les arbres ;
- certains algorithmes récursifs ;
- les structures de données.
Applications
L'induction mathématique intervient dans de nombreux domaines de l'informatique :
- démonstration de la correction des algorithmes ;
- analyse des algorithmes récursifs ;
- preuve des propriétés des arbres binaires ;
- démonstration des algorithmes de tri ;
- calcul des suites numériques ;
- théorie des graphes ;
- programmation dynamique ;
- compilation ;
- preuves formelles.
Elle constitue l'un des outils fondamentaux de l'informatique théorique.
Avantages
L'induction mathématique présente plusieurs avantages :
- elle permet de démontrer une infinité de cas à partir de deux étapes seulement ;
- elle produit des démonstrations rigoureuses ;
- elle est parfaitement adaptée aux structures récursives ;
- elle est largement utilisée dans les ouvrages scientifiques ;
- elle constitue l'un des fondements de l'analyse des algorithmes.
Limites
Malgré sa puissance, cette méthode possède certaines limites :
- elle ne s'applique qu'à des ensembles ordonnés, généralement les entiers naturels ;
- la démonstration de l'étape d'induction peut être difficile ;
- une mauvaise hypothèse conduit à une démonstration incorrecte ;
- certaines propriétés nécessitent une induction forte plutôt qu'une induction simple.
Comparaison avec d'autres méthodes de démonstration
| Méthode | Description |
|---|---|
| Démonstration directe | Établit une propriété en appliquant directement les définitions et les théorèmes connus. |
| Démonstration par l'absurde | Suppose la propriété fausse afin d'obtenir une contradiction logique. |
| Démonstration par contraposée | Démontre l'équivalence logique de la proposition contraire. |
| Induction mathématique | Prouve qu'une propriété est vraie pour tous les entiers naturels en utilisant un cas de base et une étape d'induction. |
| Induction forte | Variante utilisant toutes les valeurs précédentes pour établir la suivante. |
Remarque
L'induction mathématique est omniprésente en informatique, même lorsqu'elle n'est pas explicitement mentionnée. Chaque fois qu'un programme manipule une structure récursive, qu'un algorithme est défini en fonction de cas plus simples ou qu'une propriété doit être démontrée pour toutes les tailles d'entrée, ce type de raisonnement intervient naturellement. La compréhension de cette méthode est donc indispensable pour l'étude de l'algorithmique, de la programmation fonctionnelle, des structures de données et de la complexité des algorithmes. Elle constitue l'un des principaux liens entre les mathématiques et les sciences informatiques.