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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) 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 (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) 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 (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.) 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 contexte d'un évènement inclut les circonstances et conditions qui l'entourent; le contexte d'un mot, d'une phrase ou d'un texte inclut les mots qui l'entourent. Le concept de contexte issu...). Le raisonnement par récurrence peut se généraliser enfin aux relations bien fondées. Dans certains contextes, logique (La logique (du grec logikê, dérivé de logos (λόγος), terme inventé par Xénocrate signifiant à la fois raison, langage, et...) ou informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique de l'information...), 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 ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui s'ajoute à quelque chose de nature identique. La seconde est une unité de mesure du temps. La seconde d'arc est une mesure...) l’hérédité.

On en déduit immédiatement que pour montrer P(n) à partir d'un certain rang ( Mathématiques En algèbre linéaire, le rang d'une famille de vecteurs est la dimension du sous-espace vectoriel engendré par cette famille....) 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 (L'addition est une opération élémentaire, permettant notamment de décrire la réunion de quantités ou l'adjonction de grandeurs extensives de même nature, comme les longueurs, les aires, ou...), 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 (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) 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 (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du sous-ensemble A est aussi élément du sur-ensemble B. Il peut par contre y avoir des...) 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 (Dans une démonstration directe, pour montrer que , on commence par supposer que P est vraie, et on en déduit qu'alors Q doit nécessairement être vraie.) utilisant le calcul des puissances de 2 et de 3 modulo ( En arithmétique modulaire, on parle de nombres congrus modulo n Le terme modulo peut aussi être associé à d'autres formes de congruence En informatique,...) 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 .

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 (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment démontrées à partir de...) 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 (La théorie des ensembles est une branche des mathématiques créée initialement par le mathématicien allemand Georg Cantor à la fin du XIXe siècle.).

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

Récurrence d'ordre 2

Il peut arriver que, pour l'hérédité (L’hérédité (du latin hereditas, « ce dont on hérite ») est la transmission de caractéristiques d'une génération à la...), quand il s'agit de démontrer P(n + 1), on ait besoin (Les besoins se situent au niveau de l'interaction entre l'individu et l'environnement. Il est souvent fait un classement des besoins humains en trois grandes catégories : les besoins primaires, les besoins...) 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 (Leonardo Fibonacci (Pise, v. 1170 - v. 1250) est un mathématicien italien. Fibonacci (de son nom moderne), connu à l'époque sous le nom de Leonardo Pisano (Léonard de Pise), mais aussi de Leonardo Bigollo...) 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 (En mathématiques, un nombre entier d est un diviseur d'un entier n lorsque la division euclidienne de n par d donne un reste égal à zéro. Autrement dit, il existe un entier q tel que n = d × q.) 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 (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction,...) 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 (Les axiomes de Peano sont, en mathématiques, un ensemble d'axiomes de second ordre proposés par Giuseppe Peano pour définir l'arithmétique [1].).