Raisonnement par récurrence - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction

En mathématiques, le raisonnement par récurrence est une forme de raisonnement visant à démontrer une propriété portant sur tous les entiers naturels. Le raisonnement par récurrence consiste à démontrer les points suivants :

  • Une propriété est satisfaite par l'entier 0 ;
  • Si cette propriété est satisfaite par un certain nombre (La notion de nombre en linguistique est traitée à l’article « Nombre...) entier naturel (En mathématiques, un entier naturel est un nombre positif (ou nul) permettant fondamentalement...) n, alors elle doit être satisfaite par son successeur, c'est-à-dire, le nombre entier n+1.

Une fois cela établi, on en conclut que cette propriété est vraie pour tous les nombres entiers naturels.

Présentation

Le raisonnement par récurrence établit une propriété importante liée à la structure des entiers naturels : celle d'être construits à partir de 0 en itérant le passage au successeur. Dans une présentation axiomatique des entiers naturels, il est directement formalisé par un axiome (Un axiome (du grec ancien αξιωμα/axioma,...). Moyennant certaines propriétés des entiers naturels, il est équivalent à d'autres propriétés de ceux-ci, en particulier l'existence d'un minimum à tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou...) ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection...) non vide (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.) (bon ordre), ce qui permet donc une axiomatisation alternative reposant sur cette propriété.

Certaines formes de ce raisonnement se généralisent d'ailleurs naturellement à tous les bons ordres infinis (pas seulement celui sur les entiers naturels), 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...). Le raisonnement par récurrence peut se généraliser enfin aux relations bien fondées. Dans certains contextes, logique mathématique (La logique mathématique, ou logique formelle, est une discipline des mathématiques qui...) ou en informatique (L´informatique - contraction d´information et automatique - est le domaine...), pour des structures de nature arborescente ou ayant trait aux termes du langage formel (Dans de nombreux contextes (scientifique, légal, etc.) l'on désigne par langage formel un mode...) sous-jacent, on parle de récurrence structurelle.

On parle communément de récurrence dans un contexte lié mais différent, celui des définitions par récurrence de suites (ou d'opérations) à argument entier. Si l'unicité de telles suites se démontre bien par récurrence, leur existence, qui est le plus souvent tacitement admise dans le secondaire, voire les premières années universitaires, repose sur un principe différent.

Récurrence simple sur les entiers

Pour démontrer une propriété portant sur tous les entiers naturels, comme par exemple la formule du binôme ( en mathématique, binôme, une expression algébrique ; voir aussi binôme de Newton...) de Newton, on peut utiliser un raisonnement par récurrence. Notons la propriété en question P(n) pour indiquer la dépendance en l'entier n. On peut alors l'obtenir pour tout entier n en démontrant ces deux assertions :

  • P(0) (0 vérifie la propriété) : c'est l'initialisation de la récurrence ;
  • Pour tout entier n, (P(n) ⇒ P(n+1)) : c'est l'hérédité (L’hérédité (du latin hereditas, « ce dont on...).

On dit alors que la propriété P s'en déduit par récurrence pour tout entier n. On précise parfois « récurrence simple », quand il est nécessaire de distinguer ce raisonnement d'autres formes de récurrence (voir la suite).

Le raisonnement par récurrence est une propriété fondamentale (En musique, le mot fondamentale peut renvoyer à plusieurs sens.) des entiers naturels, et c'est le principal des axiomes de Peano (Les axiomes de Peano sont, en mathématiques, un ensemble d'axiomes de second ordre...). Une axiomatique est, en quelque sorte une définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la...) implicite, dans ce cas une définition implicite des entiers naturels. Dans certains contextes, comme en théorie des ensembles (La théorie des ensembles est une branche des mathématiques, créée par le...) on déduit directement la récurrence de la définition, explicite cette fois, de l'ensemble des entiers naturels.

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é P l'ensemble E des entiers naturels la vérifiant, et à un ensemble d'entiers naturels E 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...) de N, si :
  • 0 appartient à E
  • Pour tout entier naturel n, (n appartient à E implique n+1 appartient à E)
Alors E = N.

Bien sûr, l'initialisation peut commencer à un entier k arbitraire et dans ce cas la propriété n'est démontrée vraie qu'à partir du rang ( Mathématiques En algèbre linéaire, le rang d'une famille de vecteurs est la dimension du...) k :

Si :
  • P(k) ;
  • Pour tout entier n supérieur ou égal à k, [P(n) implique P(n+1)] ;
Alors pour tout entier n supérieur ou égal à k, P(n).

Cette récurrence à partir de k est une conséquence immédiate de la récurrence à partir de 0 : il suffit de démontrer « n < k ou P(n) », ou encore « P(n+k) » si l'on dispose de l'addition (L'addition est une opération élémentaire, permettant notamment de décrire la...), par récurrence sur n ; chacune de ces propriétés est bien vraie pour tout entier n si et seulement si la propriété P est vraie pour tout entier supérieur ou égal à k.

De façon analogue on aura d'autres raisonnements par récurrence, sans avoir besoin (Les besoins se situent au niveau de l'interaction entre l'individu et l'environnement. Il est...) de poser à chaque fois un nouveau principe, par exemple, une récurrence sur les entiers pairs (prendre P(2n)), etc.

Exemple 1 : la somme des n premiers entiers impairs

Les entiers impairs sont les entiers de la forme 2n+1 (le premier, obtenu pour n=0, est 1). On déduit d'une identité remarquable (En mathématiques, on appelle identités remarquables ou encore égalités...) bien connue que 2n+1 ajouté au carré (Un carré est un polygone régulier à quatre côtés. Cela signifie que ses...) de n donne le carré du nombre suivant :

n2+2n+1 = (n+1)2

On va donc montrer par récurrence que la somme des n premiers entiers impairs est égale au carré de n :

1+3+ … + (2n-1) = n2.

Bien que l'écriture précédente puisse laisser entendre que 2n -1 > 3, on ne le supposera pas. La somme est vide donc nulle si n = 0, réduite à 1 si n=1, égale à 1+3 si n=2 etc.

  • initialisation : le cas n=0 est celui où la somme est vide, elle est donc bien égale à 02
  • hérédité : pour un entier n arbitraire, on suppose que 1+3+ … + (2n-1) = n2. Puisque l'entier impair qui suit 2n-1 est 2n+1, on en déduit que :
1+3+ … + (2n-1) + (2n+1) = n2+2n+1= (n+1)2,
c'est-à-dire que la propriété est héréditaire.

Exemple 2 : Identité du binôme de Newton

Précautions à prendre

  • L’initialisation ne doit pas être oubliée. Voici un exemple un peu ad hoc mais qui illustre bien ceci. On montre facilement que les propriétés « 32n+6 - 2n est un multiple de 7 » et « 32n+4 - 2n est un multiple de 7 » sont toutes deux héréditaires. Cependant la première est vraie pour tout entier naturel n, alors que la seconde ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui...) ne l'est pas car elle n’est jamais initialisable : en effet, en n=0 on a 34 - 1 = 80, qui n'est pas divisible par 7. Pour la première proposition :
  • on vérifie que si n = 0, 36 - 20 est bien un multiple de 7 (728 est bien un multiple de 7) ;
  • on montre que si 32n+6 - 2n est un multiple de 7, alors 32n+8 - 2n+1 est un multiple de 7 :
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} .
32n+6 - 2n est donc somme de deux multiples de 7, c’est bien un multiple de 7.
L'hérédité de la seconde propriété est strictement analogue. On montre pourtant, en utilisant les congruences modulo ( En arithmétique modulaire, on parle de nombres congrus modulo n Le terme modulo peut aussi...) 7, qu'elle n'est vraie pour aucun entier (congruences que l'on pourrait d'ailleurs utiliser également pour démontrer la première propriété).
  • 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é démontrée directement (initialisation).
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 u1 = 1.
l’hérédité aussi car, la suite étant croissante, si u_n \geq 1 alors u_{n+1} \geq 1.
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.
Page générée en 5.297 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique