Une variante de l'induction où, pour prouver P(n+1), on suppose que P(k) est vraie pour tout k ≤ n (l'ensemble complet des cas plus petits) plutôt que de supposer seulement P(n) ; l'hypothèse inductive est donc plus forte et peut utiliser l'information cumulative de tous les précédents cas.

Principe

Hypothèse cumulative : l'idée organisatrice est que permettre l'ensemble des vérités antérieures comme hypothèses peut rendre possibles des preuves où une implication en un pas est insuffisante, simplifiant souvent des raisonnements dépendant de plusieurs cas antérieurs.

Démonstration

Prouver que tout entier >1 se factorise en nombres premiers : supposer comme hypothèse d'induction que tout entier m avec 2 ≤ m ≤ n se factorise en premiers ; alors pour n+1 soit il est premier, soit il a une factorisation en facteurs ≤ n qui, par hypothèse, se factorisent en premiers ; ceci utilise tous les cas plus petits.

Mauvaise application

Employer l'induction forte alors que l'induction ordinaire suffit peut masquer la force logique minimale requise, ou supposer que l'induction forte autorise un raisonnement non bien fondé au-delà de N ; l'utiliser sans vérifier l'intervalle de base (par ex. en démarrant trop haut) est aussi fautif.

Conséquence

Fournit un outil de preuve flexible qui englobe l'induction ordinaire et soutient des preuves reposant sur plusieurs valeurs antérieures, des relations de récurrence et certaines preuves de correction d'algorithmes ; clarifie la dépendance aux instances précédentes.

Inversion

L'inverse consiste à se restreindre à l'induction en un seul pas ; certaines propriétés démontrables par induction forte peuvent devenir embarrassantes ou nécessiter des lemmes supplémentaires sous l'induction ordinaire, montrant la différence de force hypothétique.

Limite

S'applique aux domaines bien ordonnés par successeur comme N ; elle ne s'applique pas automatiquement à des domaines non bien fondés ni aux preuves exigeant l'induction transfinie sans adapter l'hypothèse aux prédécesseurs transfinis.

Tension sémantique

Tension avec l'économie des hypothèses : l'induction forte est logiquement équivalente à l'induction ordinaire sur N, mais elle semble plus forte ; la tension sémantique est entre l'hypothèse minimale et la commodité d'admettre l'ensemble complet des vérités précédentes.

Synthèse

L'induction forte permet de supposer tous les cas plus petits comme hypothèses pour prouver le cas suivant, facilitant les preuves qui demandent une information cumulative antérieure tout en étant, sur N, équivalente en puissance à l'induction ordinaire.