Séance de cours

Récursivité mathématique : Induction et récursivité

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

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 as diverse as mathematical reasoning, combinatorics, disc ...

Description

Cette séance de cours couvre le principe de l'induction mathématique, où une proposition est prouvée vraie pour tous les entiers positifs en montrant l'étape de base et l'étape inductive. Des exemples sont fournis pour illustrer le concept, ainsi que la validité de linduction mathématique basée sur la propriété bien ordonnée des entiers positifs.

Enseignant·e

Karl Aberer

Co-Founder of LinkAlong Sarl, 2017.Vice-president EPFL for Information Systems, 2012 –2016.Director of the Swiss National Centre for Mobile Information and Communication Systems NCCR MICS (mics.ch), 2005 -2012.Member of the Swiss Research and Technology Council SWTR, consulting the Swiss Federal government, 2004 - 2011.

Source officielle

Concepts associés (32)

Démonstration (logique et mathématiques)

vignette| : un des plus vieux fragments des Éléments d'Euclide qui montre une démonstration mathématique. En mathématiques et en logique, une démonstration est un ensemble structuré d'étapes correctes de raisonnement. Dans une démonstration, chaque étape est soit un axiome (un fait acquis), soit l'application d'une règle qui permet d'affirmer qu'une proposition, la conclusion, est une conséquence logique d'une ou plusieurs autres propositions, les prémisses de la règle.

Ensemble bien ordonné

En mathématiques, un ensemble ordonné (E, ≤) est bien ordonné et la relation ≤ est un bon ordre si la condition suivante est satisfaite : Toute partie non vide de E possède un plus petit élément. Formellement cela donne ∀X⊆E, X≠∅ ⇒ (∃u∈X, ∀v∈X u≤v). Si (E, ≤) est bien ordonné alors ≤ est nécessairement un ordre total, c'est-à-dire que deux éléments quelconques x et y de E sont toujours comparables. En effet, l'ensemble { x, y } possède un plus petit élément, donc on a x ≤ y ou y ≤ x.

Well-ordering principle

In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which precedes if and only if is either or the sum of and some positive integer (other orderings include the ordering ; and ). The phrase "well-ordering principle" is sometimes taken to be synonymous with the "well-ordering theorem".

Raisonnement par disjonction de cas

Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases, and where each type of case is checked to see if the proposition in question holds. This is a method of direct proof. A proof by exhaustion typically contains two stages: A proof that the set of cases is exhaustive; i.e.

Bel ordre

En mathématiques, plus précisément en théorie des ordres, un beau préordre est un préordre ≤ sur un ensemble X tel que pour toute suite (x) d'éléments de X, il existe i et j tels que i < j et x ≤ x, c'est-à-dire que toute suite infinie contient au moins une paire d'éléments qui sont en ordre croissant. Un bel ordre est un ordre partiel qui est beau en tant que préordre. Autrement dit, c'est un ordre partiel bien fondé sans antichaîne infinie.

Afficher plus

Séances de cours associées (46)

Produit cartésien et induction

Présente le produit cartésien et l'induction pour les épreuves utilisant des entiers et des ensembles.

Comprendre les relations d'équivalence et la construction d'entiers

Couvre la construction d'entiers par des relations d'équivalence et leurs propriétés en mathématiques.

Algèbre élémentaire: ensembles numériques

Explore les concepts d'algèbre élémentaire liés aux ensembles numériques et aux nombres premiers, y compris la factorisation et les propriétés uniques.

Espaces de distribution et d'interpolation

Explore les espaces de distribution et d'interpolation, en montrant leur importance dans l'analyse mathématique et les calculs impliqués.

Forte induction: méthode de preuve et application

Explore l'induction forte comme méthode de preuve et démontre son application dans la démonstration d'un théorème sur les entiers positifs.

Afficher plus

Concepts associés (32)

Démonstration (logique et mathématiques)

Ensemble bien ordonné

Well-ordering principle

Raisonnement par disjonction de cas

Bel ordre

Afficher plus