Raisonnement par récurrence
Un article de Wikipédia, l'encyclopédie libre.
Le raisonnement par récurrence est un raisonnement utilisant le cinquième axiome de Peano appelé aussi principe de récurrence :
- Si un ensemble d’entiers naturels contient 0 et contient le successeur de chacun de ses éléments alors cet ensemble est égal à
Certains ouvrages rattachent le raisonnement par récurrence à la propriété « tout ensemble non vide d’entiers naturels possède un plus petit élément ».
Mais ces deux propriétés sont équivalentes.
Sommaire |
[modifier] Récurrence simple
Pour démontrer qu’une propriété , dépendant de , est vraie pour tout entier naturel , il suffit de démontrer que
- est vraie
- (pour tout ) (
La première propriété s’appelle l’initialisation, et la seconde l’hérédité.
[modifier] Démonstrations
Selon le point de vue pris, le principe de récurrence peut être considéré comme un axiome, ou bien se déduire d’un axiome précédemment adopté. En voici deux exemples :
[modifier] Équivalence avec le cinquième axiome de Peano
Le principe de récurrence est équivalent au cinquième axiome de Peano.
- Pour démontrer la propriété de récurrence à l’aide du cinquième axiome de Peano, il suffit de travailler sur l’ensemble E réunion des ensembles A : ensemble des entiers naturels inférieurs ou égaux à n0 et B : ensemble des entiers naturels tels que P(n) soit vraie.
- Cet ensemble contient 0. Soit n un entier de E, ou bien n est strictement inférieur à n0 alors son successeur appartient à A donc à E, ou bien alors n appartient à B. La propriété d’hérédité dit que le successeur de n vérifie P, donc appartient à B, donc appartient à E.
- E vérifie les deux conditions du cinquième axiome de Peano donc E = .
- Soit maintenant un entier naturel quelconque tel que , n appartient à E donc à B donc P(n) est vraie.
- Inversement, le cinquième axiome de Peano se déduit du principe de récurrence.
- Soit E une partie de contenant 0 et telle que tout élément de E a son successeur dans E. Alors la propriété est héréditaire et est vérifiée par 0, donc, selon le principe de récurrence, est vérifiée pour tout entier, et E = .
[modifier] Équivalence avec le principe de Fermat
Le principe de Fermat énonce que toute partie non vide de possède un plus petit élément. Le principe de récurrence est équivalent au principe de Fermat.
- Pour démontrer la propriété de récurrence à l’aide du principe de Fermat, il suffit de raisonner sur l’ensemble B' des entiers naturels supérieurs ou égaux à n0 ne vérifiant pas P.
- Si on suppose B' non vide, il possède un plus petit élément N strictement supérieur à n0, puisque n0 vérifie P (initialisation). Ce N possède un prédécesseur N - 1 supérieur ou égal à n0, N - 1 n’est pas élément de B' donc il vérifie P, mais alors son successeur N doit vérifier P (hérédité).
- Il y a contradiction donc on ne peut pas supposer B' non vide. B' est donc vide et pour tout , P(n) est vraie.
- Réciproquement, le principe de Fermat se déduit du principe de récurrence.
- Il s’agit de montrer que, si B est une partie non vide de , alors B possède un plus petit élément, autrement dit que :
- Si B non vide, alors il existe m dans B tel que, pour tout élément p de B, m ≤ p.
- Cherchons plutôt à montrer la contraposée, à savoir :
- Si pour tout m de B, il existe p dans B tel que p < m, alors B est vide.
- Considérons la propriété P(n) définie par :
- P(0) est vraie puisque, si 0 appartenait à B, il existerait p dans B strictement négatif, ce qui est absurde puisque B est une partie de .
- La propriété P est héréditaire. Supposons que P(n) soit vérifiée, et montrons P(n+1). Comme P(n) est vrai, tout élément q inférieur ou égal à n n’appartient pas à B. Donc tout élément q strictement inférieur à n+1 n’appartient pas à B et cela implique que n+1 n’appartient pas à B (si n+1 appartenait à B, il existerait p strictement inférieur à n+1 dans B). Donc P(n+1) est vérifié.
- Il en résulte que P(n) est vrai pour tout n, et donc que, pour tout n, n n’appartient pas à B, et donc que B est vide.
[modifier] Évidence du principe ?
On trouve souvent comme justification du principe de récurrence des textes tels que celui-ci :
- Ce principe est en fait évident : les deux propriétés demandées par le principe de récurrence permettent facilement de démontrer la propriété P pour toute valeur entière. Par exemple, supposons que P vérifie les deux propriétés et qu’on veuille démontrer que P est vraie pour 2. Puisque P est vraie pour 0, elle est vraie pour son successeur 1. Mais puisque P est vraie pour 1, elle est vraie pour son successeur, donc elle est vraie pour 2. Il est clair que ce raisonnement se poursuit sans problème pour tout nombre entier fixé à l’avance. (Le langage CAML, Weis et Leroy – InterEditions 1993).
Cependant, une telle argumentation ne saurait constituer une démonstration du principe de récurrence lui-même, car pour montrer que P(n) est vrai pour TOUT n, il faudrait écrire TOUTES les implications entre P(n) et P(n+1) et cela nécessiterait une infinité d’implications. Or une démonstration se doit d’être finie. Une telle preuve ne vaudrait donc QUE pour un entier n fixé à l'avance.
Nous avons vu que le principe de récurrence est un axiome, ou est équivalent à un axiome, et comme tout axiome, il peut être rejeté. On crée alors un nouveau domaine mathématique. Dans ce domaine, il existe un prédicat P tel que l’on ait simultanément les trois propriétés suivantes :
-
- P(0) est vrai
- Pour tout n, P(n) implique P(n+1)
- il existe n, non P(n)
Quel sens donner à un tel prédicat P ? Est-ce concevable ? Comment définir une propriété vraie pour 0, vraie pour n+1 si elle est vraie pour n, et cependant fausse pour un certain entier ? Voici une possibilité. Les entiers n vérifiant la propriété P seront qualifiés d’accessibles, de limités, ou de standard. Les entiers n ne vérifiant pas la propriété P seront qualifiés d’inaccessibles, d’illimités, ou de non standard. Ainsi, 0 est accessible. Si n est accessible, alors n+1 l’est aussi. Cependant, il existe des entiers qui nous sont inaccessibles. Finalement, la propriété P ainsi définie ne correspond-elle pas à la réalité ? Ce point de vue est à la source de l’analyse non standard, dans laquelle la propriété P décrite ci-dessus est une notion primitive qui s’ajoute aux notions d’ensembles et d’appartenance.
[modifier] Exemples
[modifier] Exemple 1
Montrons que la somme des n premiers entiers 1 + 2 + ... + n est égal à .
- Cette propriété est vraie pour n = 1 puisque .
- Supposons que . Alors :
La propriété est bien héréditaire.
[modifier] Exemple 2
Pour démontrer par récurrence que
- pour tout , 32n − 2n − 3 est un multiple de 7
Il suffit
- de vérifier que si n = 3, 36 − 20 est bien un multiple de 7 (728 est bien un multiple de 7)
- de démontrer que (pour tout ) (si 32n − 2n − 3 est un multiple de 7 alors 32n + 2 − 2n − 2 est un multiple de 7 .
-
- 32n + 2 − 2n − 2 est donc somme de deux multiples de 7, c’est bien un multiple de 7
[modifier] Précautions à prendre
- Souvent négligée parce que trop facile, l’initialisation ne doit pas être oubliée. En reprenant l’exemple précédent, on peut démontrer que la propriété « 32n − 2n − 2 est un multiple de 7 » est héréditaire, mais elle est pourtant fausse car n’est jamais initialisable.
- L’hérédité doit être démontrée pour tout .
- Si on prend, par exemple, la suite , on peut observer que cette suite est croissante à partir de n = 2 car .
- Si on cherche à démontrer que pour tout ,
- l’initialisation est facile à prouver car u1 = 1.
- l’hérédité aussi car, la suite étant croissante, si alors .
- Or pourtant cette inégalité est vraie seulement pour n = 1. L’hérédité n’a en réalité été prouvée que pour n supérieur ou égal à 2 et non pour n supérieur ou égal à 1.
[modifier] Récurrence forte
Il est parfois nécessaire, dans des raisonnements par récurrence, d’utiliser une version plus forte pour l’hérédité :
Pour démontrer qu’une propriété P(n), dépendant de n, est vraie pour tout entier naturel , il suffit de démontrer que
- P(n0) est vraie
- (pour tout ) [((pour tout ) ]
Bref, pour démontrer la propriété au rang suivant il faut la supposer vraie pour tous les rangs inférieurs.
La démonstration de cette propriété est analogue à celle décrite plus haut
Exemple d'utilisation :
Pour démontrer que tout entier naturel supérieur ou égal à 2 possède un diviseur premier.
- On démontre que 2 possède un diviseur premier qui est lui même
- Soit n un entier supérieur ou égal à 2, on suppose que tous les entiers d compris entre 2 et n possèdent un diviseur premier et on cherche à prouver qu’il en est de même de n + 1.
- ou bien n + 1 est premier alors il possède un diviseur premier qui est lui-même
- ou bien n + 1 est composé et il existe deux entiers d et d' compris entre 2 et n tels que n = dd'. Alors d et d' possèdent des diviseurs premiers qui sont aussi diviseurs de n + 1.