Raisonnement par récurrence

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

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 à $\mathbb N$

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.

[modifier] Récurrence simple

Pour démontrer qu’une propriété $\ P(n)$ , dépendant de $\ n$ , est vraie pour tout entier naturel $n \geq n_0$ , il suffit de démontrer que

$\ P(n_0)$ est vraie
(pour tout $n \geq n_0$ ) ( $P(n) \Rightarrow P(n+1))$

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 à n₀ 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 à n₀ alors son successeur appartient à A donc à E, ou bien $n \geq n_0$ 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 = $\mathbb N$ .

Soit maintenant un entier naturel quelconque tel que $n \geq n_0$ , 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 $\mathbb N$ contenant 0 et telle que tout élément de E a son successeur dans E. Alors la propriété $P(n) : n \in E$ 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 = $\mathbb N$ .

[modifier] Équivalence avec le principe de Fermat

Le principe de Fermat énonce que toute partie non vide de $\mathbb N$ 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 à n₀ ne vérifiant pas P.

Si on suppose B' non vide, il possède un plus petit élément N strictement supérieur à n₀, puisque n₀ vérifie P (initialisation). Ce N possède un prédécesseur N - 1 supérieur ou égal à n₀, 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 $n \geq n_0$ , 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 $\mathbb N$ , 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 :

pour tout q ≤ n, q n’appartient pas à B

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 $\mathbb N$ .

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 à ${n(n+1) \over 2}$ .

Cette propriété est vraie pour n = 1 puisque $1 = {1 \times 2 \over 2}$ .
Supposons que $1 + 2 + ... + n = {n(n+1)\over 2}$ . Alors :

$1 + 2 + ... + n + (n+1) = {n(n+1)\over 2} + (n+1)$

$= {n(n+1) + 2(n+1) \over 2}$

$= {(n+1)(n+2) \over 2}$

La propriété est bien héréditaire.

[modifier] Exemple 2

Pour démontrer par récurrence que

pour tout $n \geq 3$ ,

3 2 n - 2 n - 3

est un multiple de 7

Il suffit

de vérifier que si n = 3, $36 - 2 0$ est bien un multiple de 7 (728 est bien un multiple de 7)
de démontrer que (pour tout $n \geq 3$ ) (si $3 2 n - 2 n - 3$ est un multiple de 7 alors $3 2 n + 2 - 2 n - 2$ est un multiple de 7 .

$3^{2n+2} - 2^{n - 2} = 9\times 3^{2n} - 2 \times 2^{n - 3}$

$3^{2n+2} - 2^{n - 2} = (7+2)\times 3^{2n} - 2 \times 2^{n - 3}$

$3^{2n+2} - 2^{n - 2} = 7\times 3^{2n} +2\times 3^{2n} - 2 \times 2^{n - 3}$

$3^{2n+2} - 2^{n - 2} = 7\times 3^{2n} +2( 3^{2n} -2^{n - 3})$

3 2 n + 2 - 2 n - 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é « $3 2 n - 2 n - 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 $n \geq n_0$ .

Si on prend, par exemple, la suite $u_n = \frac{n^2 - n + 1}{n^2}$ , on peut observer que cette suite est croissante à partir de n = 2 car $u_{n+1} - u_n = \frac{n^2 - n - 1}{n^2(n+1)^2} > 0$ .

Si on cherche à démontrer que $u_n \geq 1$ pour tout $n \geq 1$ ,

l’initialisation est facile à prouver car

u 1 = 1

l’hérédité aussi car, la suite étant croissante, si $u_n \geq 1$ alors $u_{n+1} \geq 1$ .

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 $n \geq n_0$ , il suffit de démontrer que

$P (n 0)$ est vraie
(pour tout $n \geq n_0$ ) [((pour tout $n_0 \leq k \leq n)P(k)$ ) $\Rightarrow P(n+1)$ ]

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.

[modifier] Articles annexes

Récupérée de « http://fr.wikipedia.org../../../r/a/i/Raisonnement_par_r%C3%A9currence.html »

Catégorie : Méthode de démonstration