Raisonnement par récurrence - Définition

Le raisonnement par récurrence est une forme de raisonement mathématique dont l'objet est de démontrer une propriété de tous les entiers naturels, ou plus généralement d'une infinité d'entiers naturels. Il énonce que, pour qu'une propriété soit vérifiée par tout entier, il suffit :

• qu'elle soit vérifiée en 0 ;
• qu'elle " passe au suivant " : si elle est vérifiée pour un entier alors elle l'est pour l'entier qui suit.

On peut dire la même chose de façon ensembliste :

Si un ensemble d’entiers naturels contient 0 et contient le successeur de chacun de ses éléments alors cet ensemble contient tous les entiers naturels.

Le raisonnement par récurrence est intimement lié à la propriété de bon ordre de N, l'ensemble des entiers naturels, qui dit que

tout ensemble non vide d’entiers naturels possède un plus petit élément.

Certaines formes de ce raisonnement se généralisent d'ailleurs naturellement aux bons ordres infinis, on parle alors de récurrence transfinie, de récurrence ordinale (tout bon ordre est isomorphe à un ordinal) ; le terme d’induction est aussi souvent utilisé dans ce contexte. Le raisonnement par récurrence peut se généraliser enfin aux relations bien fondées. Dans certains contextes, logique ou informatique, pour des structures de nature arborescente, on parle de récurrence structurelle.

Récurrence simple

Pour démontrer qu’une propriété P(n), définie sur les entiers naturels, est vraie pour tous ceux-ci, il suffit de démontrer que

• P(0)
• (pour tout entier n) (

La première propriété s’appelle l’initialisation, et la seconde l’hérédité.

On en déduit immédiatement que pour montrer P(n) à partir d'un certain rang n₀ seulement, il suffit de montrer :

• P(n₀)
• (pour tout entier ) (

ceci en montrant P(n₀ + p) par récurrence sur p, ou encore, si on ne souhaite pas faire référence à l'addition, en montrant la propriété " n < n₀ ou P(n) " par récurrence sur n.

La récurrence peut aussi s'exprimer de façon ensembliste : il s'agit juste d'une variation sur la définition d'un ensemble en compréhension. On associe à une propriété l'ensemble des entiers naturels la vérifiant, et à un ensemble d'entiers naturels la propriété d'appartenance associée. La récurrence se réénonce alors de façon équivalente ainsi :

Soit E un sous-ensemble de N, si :

• 0 ∈ E
• n ∈ E ⇒ n+1 ∈ E (pour tout n ∈ N)

Alors E = N.

Exemples

Exemple 1

Montrons que la somme des n premiers entiers 1 + 2 + ... + n est égale à .

• Cette propriété est vraie pour n = 1 puisque .
• Soit . Supposons que . Alors :

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

Exemple 2

Pour démontrer par récurrence que

pour tout , 3²ⁿ − 2^{n − 3} est un multiple de 7

Il suffit

• de vérifier que si n = 3, 3⁶ − 2⁰ est bien un multiple de 7 (728 est bien un multiple de 7) ;
• de démontrer que (pour tout ) si 3²ⁿ − 2^{n − 3} est un multiple de 7, alors 3^{2n + 2} − 2^{n − 2} est un multiple de 7.

.

.

.

.

3^{2n + 2} − 2^{n − 2} est donc somme de deux multiples de 7, c’est bien un multiple de 7

En premier cycle universitaire, l'étudiant en mathématiques rencontre une démonstration directe utilisant le calcul des puissances de 2 et de 3 modulo 7. L'avantage du calcul ci-dessus est non seulement de ne pas être plus couteux, mais aussi de fournir une méthode itérative pour trouver le quotient un de 3²ⁿ − 2^{n − 3} par 7. En effet, la suite u vérifie la relation de récurrence :

u_{n + 1} = 3²ⁿ + 2u_n et u₃ = 104.

Par un nouvel argument par récurrence, on trouve :

.

Précautions à prendre

• 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} 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 entier n plus grand ou égal au dernier n₀ pour lequel la propriété a été demontré directement (initialisation).

Si on prend, par exemple, la suite , on peut observer que cette suite est croissante à partir de n = 2 car 0" >.

Si on cherche à démontrer que pour tout ,

l’initialisation est facile à prouver car u₁ = 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.

É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. L'hypothèse de récurrence permet théoriquement d'écrire " mécaniquement " une preuve pour un entier arbitrairement grand, aucun effort d'imagination n'est nécessaire. Mais sans le principe de récurrence on ne pourra jamais écrire ces preuves que pour un nombre fini d'entiers. Le principe de récurrence permet justement de " rassembler " sous la forme d'une seule démonstration (finie), cette infinité de démonstrations, une pour chaque entier.

Le principe de récurrence n'est donc pas de nature purement logique, mais fondamentalement lié à la nature de l'ensemble des entiers naturels, dont d'ailleurs il fournit quasiment une définition en théorie des ensembles.

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é aus 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, puis que 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.

Bref, 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).

Le 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. Il s'agit d'utiliser directement la propriété de bon ordre — tout sous-ensemble non vide de N a un plus petit élément — qui là encore est équivalente à la propriété de récurrence. On montre en fait que la dernière propriété de récurrence donnée au pargraphe précédent, qui ne dépend que de l'ordre, est une autre façon de formuler la propriété de bon ordre.

En effet, dire d'une propriété P que, pour tout n ∈ N :

[∀k<n P(k)] ⇒ P(n)

c'est dire, par contraposée, que :

non P(n) ⇒ ∃k<n non P(k)

c'est à dire que le complémentaire de son ensemble caractéristique — C_P = {n ∈ N | non P(n)} — n'a pas de plus petit élément.

Par ailleurs dire de P qu'elle est vraie pour tout n ∈ N équivaut à dire de l'ensemble C_P qui lui est associé ci-dessus qu'il est vide. Comme on peut associer à tout sous-ensemble A de N, une propriété P(n), à savoir n ∉ A, telle que A = C_P, il y a équivalence entre l'énoncé de récurrence sous sa dernière forme et l'énoncé :

tout sous-ensemble A 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.

Axiomatisation

ébauche

voir axiomes de Peano.