Raisonnement par récurrence - Définition

Justification du principe de récurrence

Le texte de Blaise Pascal cité plus haut, premier texte où le raisonnement par récurrence apparaît de façon tout à fait explicite, donne une justification intuitive très naturelle de celui-ci : le fait qu'il permette de construire une démonstration directe pour n'importe quel entier, justification toujours employée de nos jours. Cependant cette justification ne peut constituer une démonstration de la validité du principe de récurrence. Pour démontrer P(n) pour tout entier n, il faudrait écrire toutes les implications entre P(n) et P(n+1) et cela nécessiterait une infinité d’implications. Comme une démonstration est finie, une telle démonstration ne vaudra donc que pour un entier n fixé à l'avance. L'hypothèse de récurrence permet théoriquement d'écrire « mécaniquement » une démonstration pour un entier arbitrairement grand, mais non pour tous les entiers.

Le principe de récurrence est donc bien une propriété des entiers naturels, admis en tant qu'axiome (Dedekind 1888), ou bien démontré dans le cadre de la théorie des ensembles, plus puissante. Il permet alors de « rassembler » sous la forme d'une seule démonstration finie, cette infinité de démonstrations, une pour chaque entier.

Pour autant l'axiomatisation a-t-elle entièrement capturé l'intuition ? On déduit très directemement des théorèmes d'incomplétude de Gödel (1931) que non. En effet, pour toute axiomatisation raisonnable, par exemple la théorie des ensembles ZFC, chacun de ces deux théorèmes fournit une propriété des entiers démontrable pour n'importe quel entier fixé à l'avance, mais pourtant on ne peut démontrer cette propriété pour tout entier n, par récurrence ou tout autre moyen disponible par l'axiomatisation.

On a pu préférer déduire la propriété de récurrence pour les entiers de celle de bon ordre sur les entiers, et donc axiomatiser cette dernière, par exemple dans l'enseignement secondaire français des années 1970. Cela ne change rien sur le fond aux remarques qui précèdent.

En analyse non standard, on introduit un prédicat primitif, être standard, qui ne vérifie pas le principe de récurrence.

Énoncé formel du principe de récurrence

Formellement le principe de récurrence s'énonce comme un axiome ainsi :

La quantification sur P est une quantification qui porte sur une fonction, on dit qu'il s'agit d'une quantification du second ordre. C'est cet aspect qui fait de l'axiome de récurrence un axiome très différent des autres axiomes qui régissent les entiers naturels.

Comme expliqué plus haut, en théorie des ensembles ce principe n'est plus un axiome mais un théorème (qui peut donc se déduire). Dans ce cas il s'écrit :

où n⁺ est le successeur de n. Pour l'utiliser il suffit de prendre P comme l'ensemble des entiers naturels qui vérifient le prédicat en question.

Autres formes de récurrence, énoncés équivalents

Récurrence d’ordre 2

Il peut arriver que, pour l'hérédité, quand il s'agit de démontrer P(n + 1), on ait besoin de supposer la propriété aux deux rangs précédents, c'est-à-dire non seulement pour n, mais aussi pour n -1. On est amené à utiliser le principe de récurrence suivant :

Soit P(n) une propriété définie sur N, si :

• P(0)
• P(1)
• [P(n) et P(n+1)] ⇒ P(n+2) (pour tout n ∈ N)

alors P(n) pour tout n ∈ N.

Cette propriété est en apparence plus forte que la récurrence simple, puisque l'on a une hypothèse supplémentaire à notre disposition, mais lui est en fait équivalente, puisque cela revient à démontrer [P(n) et P(n+1)] par récurrence simple. On trouvera par exemple dans l'article suite de Fibonacci des exemples d'application de ce principe de récurrence.

On peut bien entendu généraliser à 3, 4 etc. Mais tous ces principes apparaissent comme des cas particuliers du principe de récurrence suivant, parfois appelé récurrence forte.

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

Soit P(n) une propriété définie sur N, si :

• P(0)
• [∀k≤n P(k)] ⇒ P(n+1) (pour tout n ∈ N)

alors P(n) pour tout entier n ∈ N.

Donc pour démontrer la propriété au rang suivant on peut la supposer vraie pour tous les rangs inférieurs.

À nouveau cette propriété est en apparence plus forte que la récurrence simple, mais lui est en fait équivalente, puisque cela revient à démontrer la propriété « ∀k≤n P(k) » par récurrence simple.

Cette récurrence peut également se décaler à partir d'un certain rang, exactement comme la récurrence simple.

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 + 1 = dd'. Alors d et d' possèdent des diviseurs premiers qui sont aussi diviseurs de n + 1.

Bonne fondation

On peut réénoncer ce principe de façon à évacuer toute référence aux entiers : 0 et le successeur qui à n associe n+1, au profit de la seule relation d'ordre. En effet les deux hypothèses de récurrence peuvent se rassembler en une seule :

Soit P(n) une propriété définie sur N, si :

• [∀k<n P(k)] ⇒ P(n) (pour tout n ∈ N)

alors P(n) pour tout entier n ∈ N.

(dans le cas où n = 0, l'hypothèse est vide).

C'est cette forme du raisonnement par récurrence qui se généralise directement aux bons ordres (et aux ordres bien fondés). Dans le cas des entiers l'équivalence démontrée ci-dessus utilise, entre autres, que le seul entier qui n'est pas le successeur d'un autre entier est zéro. C'est cette propriété qui n'est pas nécessairement vraie dans les ensembles bien ordonnés.

Un principe de récurrence alternatif

Dans son livre sur la fonction gamma, le mathématicien Emil Artin propose un principe de récurrence qui s'adapte bien au cas où la propriété se démontre facilement pour les puissances de 2. Son énoncé est le suivant:

Soit P(n) une propriété définie sur N :

• si P(1),
• si pour tout n ∈ N, P(n) ⇒ P(2n),
• et si pour tout n ∈ N, P(n+1) ⇒ P(n),

alors, pour tout entier n ∈ N, P(n).

L'originalité de ce principe repose sur un principe de récurrence à rebours : on ne prouve plus une propriété de n à n+1 mais de n+1 à n en y adjoignant que si la propriété est vraie d'un entier alors elle est vraie pour un entier strictement plus grand. Ce qui donne une preuve de la propriété sur tous les entiers en zigzag. Notons que cette idée peut se généraliser de 2 façons :

D'abord, en remplaçant l'hypothèse :

• si pour tout n ∈ N, P(n) ⇒ P(2n), par :
• si pour tout n ∈ N, P(n) ⇒ P(f(n)), où f est n'importe quelle fonction applicative strictement croissante sur les entiers.

Même mieux en la remplaçant par :

• si pour tout n ∈ N [ P(n) ⇒ ∃p ∈ N, (n

  ], qui s'affranchit de la considération d'une fonction particulière.

D'autre part, avec cette généralisation, la règle d'initialisation :

• si P(1) ( qui par rebours implique P(0) )

peut être remplacée (mais pas dans l'exemple de Artin qui nécessite que la propriété soit vérifiée par un entier non nul) par  :

• s'il existe n ∈ N, P(n).

Ce qui nous donne le principe de récurrence suivant :

Soit P(n) une propriété définie sur N :

• s'il existe n ∈ N, P(n),
• si pour tout n ∈ N [ P(n) ⇒ ∃p ∈ N, (n

  ],

• et si pour tout n ∈ N, P(n+1) ⇒ P(n),

alors, pour tout entier n ∈ N, P(n).

Bon ordre et principe de descente infinie de Fermat

De façon alternative à la récurrence, en particulier à la récurrence forte, on peut utiliser le principe de descente infinie illustré par Pierre Fermat ; c'est une conséquence de la propriété de bon ordre, qui dit que tout sous-ensemble non vide de N a un plus petit élément, équivalente à la propriété de récurrence. On montre en fait que la propriété de récurrence donnée précédemment, qui ne dépend que de l'ordre, est une autre façon de formuler la propriété de bon ordre (sachant que la relation « ≤ » est totale).

Réénonçons tout d'abord cette récurrence de façon ensembliste. Cela revient à dire que pour tout sous-ensemble E de N :

si ([∀k ∈ N] k<n ⇒ k ∈ E) ⇒ n ∈ E (pour tout n ∈ N)

alors E = N.

En reformulant par contraposée l'hypothèse de récurrence ci-dessus, on obtient que, pour tout n ∈ N :

n ∉ E ⇒ (∃k ∈ N) k <n & k∉ E

c'est-à-dire que le complémentaire de E dans les entiers — notons-le E^C — n'a pas de plus petit élément. Par ailleurs :

E = N si et seulement si E^C = ∅.

Sachant que l'ordre sur N est total, il y a donc équivalence entre l'énoncé de récurrence sous sa dernière forme et l'énoncé :

tout sous-ensemble E de N qui n'a pas de plus petit élément est vide.

qui n'est autre que la contraposée de la propriété de bon ordre.

On a donc montré l'équivalence entre la propriété de récurrence simple sur N (via la propriété de récurrence forte) et la propriété de bon ordre sur N. Comme il existe des bons ordres qui ne sont pas isomorphes à l'ordre usuel sur N, on a forcément utilisé au passage une propriété spécifique des entiers, en l'occurrence le fait que tout entier non nul est le successeur d'un autre entier, qui est d'ailleurs une conséquence de la propriété de récurrence. On utilise également des propriétés de compatibilité de l'ordre usuel sur les entiers et de la relation de successeur, y = x +1, essentiellement que l'ordre est obtenu en itérant celle-ci.

On peut remarquer que si l'on se contente de prouver la propriété de récurrence à partir de celle de bon ordre, et non l'équivalence, la preuve est particulièrement simple. Pour une propriété P héréditaire et vérifiée en 0, il suffit de considérer, le minimum de l'ensemble des entiers ne vérifiant pas celle-ci. Il n'existe que si cet ensemble est non vide. Si ce minimum est 0 cela contredit l'initialisation. Si ce minimum est le successeur d'un entier, ce dernier contredit l'hérédité. L'ensemble des entiers ne vérifiant pas P est donc vide : tout entier vérifie P.

De N est bien ordonné, on déduit directement qu'il n'existe pas de suite infinie strictement décroissante sur N, d'où le nom de « descente infinie » (dans le raisonnement par descente infinie, il s'agit justement d'en établir une, dans le cadre d'un raisonnement par l'absurde).

Il est également possible dans un raisonnement d'exploiter directement la propriété de bon ordre, appelée parfois dans ce cadre principe du minimum. Par exemple si on reprend l'un des premiers exemples connus de raisonnement par descente infinie, l'existence pour tout nombre d'un diviseur premier, on peut, en raisonnant par l'absurde, établir une suite infinie de diviseurs successifs stricts (descente infinie), ou choisir directement le plus petit diviseur d'un nombre donné (bon ordre) et montrer qu'il est premier.

Histoire

Généralisations

- Introduction - Présentation - Récurrence simple sur les entiers - Histoire - Justification du principe de récurrence - Autres formes de récurrence, énoncés équivalents - Généralisations