Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] \| Liste Catégories \| Une page au hasard \| Pages liées

Raisonnement par récurrence

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 ses éléments alors cet ensemble est égal à 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.

Sommaire

1 Récurrence simple

1.1 Démonstrations
1.2 Exemple
1.3 Précautions à prendre

2 Récurrence forte

3 Articles annexes

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

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é.

Démonstrations

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 de 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 = N.

Soit maintenant un entier naturel quelconque tel que $n \geq n_0$ , n appartient à E donc à B donc P(n) est vraie.

Pour démontrer la propriété de récurrence à l'aide des ensembles non vides possédant un plus petit élément, 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.

Exemple

Pour démontrer par récurrence que

pour tout $n \geq 3$ , est un multiple de 7

Il suffit

de vérifier que si n = 3, est bien un multiple de 7 (728 est bien un multiple de 7)
de démontrer que (pour tout $n \geq 3$ ) (si est un multiple de 7 alors 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\times 3^{2n} +2( 3^{2n} -2^{n - 3})$

est donc somme de deux multiples de 7, c'est bien un multiple de 7

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é « est un multiple de 7 » est héréditaire, mais elle est pourtant fausse et 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 .

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.

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

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.

Articles annexes

Catégories: Raisonnement mathématique

This site support the Wikimedia Foundation. This Article originally from Wikipedia. All text is available under the terms of the