Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Raisonnement par récurrence
Résumé
vignette|Le raisonnement par récurrence est comme une suite de dominos. Si la propriété est vraie au rang n0 (i. e. le premier domino de numéro 0 tombe) et si sa véracité au rang n implique celle au rang n + 1 (i. e. la chute du domino numéro n fait tomber le domino numéro n + 1) alors la propriété est vraie pour tout entier (i. e. tous les dominos tombent).
En mathématiques, le raisonnement par récurrence (ou par induction, ou induction complète) 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 :
la propriété est satisfaite par un entier n0 (généralement 0 ou 1) ;
chaque fois que cette propriété est satisfaite par un certain nombre entier naturel n ≥ n0, elle est également satisfaite par son successeur, c'est-à-dire par le nombre entier n + 1.
Une fois cela établi, on en conclut que cette propriété est vraie pour tous les nombres entiers naturels supérieurs ou égaux à n0.
Le raisonnement par récurrence établit une propriété importante des entiers naturels : celle d'être construits à partir d'un entier n0 en itérant le passage au successeur. Dans une présentation axiomatique des entiers naturels, il est directement formalisé par un axiome. 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 ensemble non vide (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, ou 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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique
Cours associés (31)
COM-401: Cryptography and security
This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
MATH-502: Distribution and interpolation spaces
The goal of this course is to give an introduction to the theory of distributions and cover the fundamental results of Sobolev spaces including fractional spaces that appear in the interpolation theor
Séances de cours associées (185)
Rôle de la chaîne: Lipschitz Sit
Couvre le rôle de chaîne de Theoreus pour les fonctions Lipschitz et ses applications pratiques.
Induction structurelle
Introduit l'induction structurelle, une méthode pour prouver les propriétés des éléments dans des ensembles définis récursivement.
Induction structurelle
Introduit l'induction structurelle, une méthode pour prouver les propriétés des éléments dans des ensembles définis récursivement.
Publications associées (53)
The impact of different methods of increasing the intensity of compassion in engineering ethics cases
Roland John Tormey, Nihat Kotluk
Despite the growing interest in emotions in engineering education, empirical research on incorporating them into engineering ethics education is limited. Therefore, we designed this experimental study to assess how different methods for integrating compass ...
2024An automated do-it-yourself system for dynamic stem cell and organoid culture in standard multi-well plates
Matthias Lütolf, Sebastian Maerkl, Hao-An Hsiung, Zoe Newell Swank, Stefano Davide Vianello, Julia Tischler
We present a low-cost, do-it-yourself system for complexmammalian cell culture under dynamically changing medium formulations by integrating conventional multi-well tissue culture plates with simple microfluidic control and system automation. We demonstrat ...
2022Personnes associées (13)
Concepts associés (32)
Entier naturel
En mathématiques, un entier naturel est un nombre permettant fondamentalement de compter des objets considérés comme des unités équivalentes : un jeton, deux jetons... une carte, deux cartes, trois cartes... Un tel nombre entier peut s'écrire avec une suite finie de chiffres en notation décimale positionnelle (sans signe et sans virgule). L’étude des entiers naturels est l’objet de l’arithmétique, branche des mathématiques, constituée dès l'Antiquité grecque.
Axiomes de Peano
vignette|Giuseppe Peano En mathématiques, les axiomes de Peano sont des axiomes pour l'arithmétique proposés initialement à la fin du par Giuseppe Peano, et qui connaissent aujourd'hui plusieurs présentations qui ne sont pas équivalentes, suivant la théorie sous-jacente, théorie des ensembles, logique du second ordre ou d'ordre supérieur, ou logique du premier ordre. Richard Dedekind avait proposé une formalisation assez proche, sous une forme non axiomatique.
Logique mathématique
La logique mathématique ou métamathématique est une discipline des mathématiques introduite à la fin du , qui s'est donné comme objet l'étude des mathématiques en tant que langage. Les objets fondamentaux de la logique mathématique sont les formules représentant les énoncés mathématiques, les dérivations ou démonstrations formelles représentant les raisonnements mathématiques et les sémantiques ou modèles ou interprétations dans des structures qui donnent un « sens » mathématique générique aux formules (et parfois même aux démonstrations) comme certains invariants : par exemple l'interprétation des formules du calcul des prédicats permet de leur affecter une valeur de vérité'.