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 :
On peut dire la même chose de façon ensembliste :
Le raisonnement par récurrence est intimement lié à la propriété de bon ordre de N, l'ensemble des entiers naturels, qui dit que
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 traditionnellement de...). 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 raisonnement) est dans une première approche l'étude des...) ou informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement...), pour des structures de nature arborescente, on parle de récurrence structurelle.
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
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...) 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. Le théorème du rang lie le rang et la dimension du noyau...) n0 seulement, il suffit de montrer :
ceci en montrant P(n0 + 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...), en montrant la propriété " n < n0 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 :
Montrons que la somme des n premiers entiers 1 + 2 + ... + n est égale à .
La propriété est bien héréditaire.
Pour démontrer par récurrence que
Il suffit
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, le 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 u
Par un nouvel argument par récurrence, on trouve :
On trouve souvent comme justification du principe de récurrence des textes tels que celui-ci :
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 propositions...) 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.).
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 suivante, quel que soit le mode de...), 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 secondaires et 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 :
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 (bigollo signifiant...) 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.
Il est parfois nécessaire, dans des raisonnements par récurrence, d’utiliser une version plus forte pour l’hérédité :
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.
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...) premier.
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 :
(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).
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, d'un événement, etc.) 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 :
c'est dire, par contraposée, que :
c'est à dire que le complémentaire de son ensemble caractéristique — CP = {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 CP 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 = CP, il y a équivalence entre l'énoncé de récurrence sous sa dernière forme et l'énoncé :
qui n'est autre que la contraposée de la propriété de bon ordre.
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].).