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<p et P(p)) ], 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 :
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<p et P(p)) ],
- 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 — n'a pas de plus petit élément. Par ailleurs :
E = N si et seulement si E = ∅.
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.
![3^{2n+8} - 2^{n+1}\begin{array}[t]{l}= 9\times 3^{2n+6} - 2 \times 2^{n}\ = (7+2)\times 3^{2n+6} - 2 \times 2^{n}\ = 7\times 3^{2n+6} +2\times 3^{2n+6} - 2 \times 2^{n}\ = 7\times 3^{2n+6} +2( 3^{2n+6} -2^{n}) \end{array}](https://static.techno-science.net/illustrations/definitions/393px/7/7dd844c069ddc213c0cba17d5c3376ec_3a20d002578c88115b845ee4076a4ccd.png)