Un schéma de preuve qui établit une propriété pour tous les entiers naturels en prouvant un cas de base (généralement pour 0 ou 1) et une étape inductive montrant : si la propriété vaut pour un n arbitraire alors elle vaut pour n+1.

Principe

Transfert local-vers-global sur N : la règle organisatrice est que vérifier une base et une fermeture par successeur suffit pour propager une propriété à chaque entier naturel par application répétée de l'étape inductive.

Démonstration

Pour prouver une formule P(n) pour tout n∈N, montrer que P(0) est vraie et que pour un n arbitraire P(n) ⇒ P(n+1). Par exemple, prouver par induction que la somme des n premiers entiers vaut n(n+1)/2 en vérifiant la base n=0 et l'étape inductive algébrique.

Mauvaise application

Utiliser l'induction ordinaire lorsque l'étape inductive nécessite des hypothèses sur plusieurs valeurs plus petites (c.-à-d. appliquer seulement P(n)⇒P(n+1) alors que l'hypothèse correcte requiert la connaissance de tous les k≤n), ou omettre d'établir un cas de base valable pour le domaine visé.

Conséquence

Fournit une méthode canonique pour prouver une infinité d'énoncés avec un travail fini ; sous-tend les définitions récursives, les preuves de correction d'algorithmes sur les entiers et offre une base pour les propriétés arithmétiques.

Inversion

L'inverse consiste à montrer que même avec un cas de base et une étape inductive prétendue, la propriété peut échouer si l'étape ou la base est défectueuse ; alternativement, omettre le cas de base ou utiliser une règle de successeur non standard rompt la propagation à tous les naturels.

Limite

S'applique aux domaines bien ordonnés par successeur comme N ; ne s'applique pas directement aux structures dépourvues d'un successeur clair ni aux preuves nécessitant l'induction transfinie ou structurelle sans adaptation appropriée.

Tension sémantique

Tension avec l'induction forte ou structurelle : l'induction ordinaire suppose une implication d'un seul pas de successeur, tandis que les formes fortes ou structurelles autorisent des prémisses sur tous les instants plus petits ou inductent sur la structure plutôt que sur le successeur numérique.

Synthèse

L'induction mathématique est la vérification finie en deux temps (cas de base et étape de successeur) qui propage la vérité sur les nombres naturels, servant d'outil principal pour démontrer identités arithmétiques, correction d'algorithmes entiers et propriétés définies récursivement.