Eine Variante der Induktion, bei der man zur Beweisführung von P(n+1) annimmt, dass P(k) für alle k ≤ n gilt (die gesamte Menge der kleineren Fälle), anstatt nur P(n) anzunehmen; die induktive Annahme ist damit stärker und kann kumulative Informationen aller vorherigen Instanzen nutzen.

Prinzip

Kumulative Hypothese: Die ordnende Idee ist, dass die Zulassung der vollständigen Menge früherer Wahrheiten als Hypothesen Beweise ermöglicht, bei denen eine Ein-Schritt-Implikation nicht ausreicht, und damit oft Argumente vereinfacht, die von mehreren früheren Fällen abhängen.

Demonstration

Beweise, dass jede ganze Zahl größer als 1 in Primfaktoren zerfällt: Nimm als Induktionsannahme, dass jede Zahl m mit 2 ≤ m ≤ n in Primzahlen zerfällt. Für n+1 ist entweder n+1 prim, oder es besitzt eine Zerlegung in Faktoren ≤ n, die nach der Annahme in Primzahlen zerfallen; dies nutzt alle kleineren Instanzen.

Fehlanwendung

Starke Induktion anzuwenden, wo gewöhnliche Induktion ausreicht, kann die minimale logische Stärke verschleiern, oder anzunehmen, starke Induktion erlaube wohlgründigkeitsfreie Begründungen außerhalb von N; auch ihre Nutzung ohne Prüfung des Basisbereichs (z. B. zu spätes Starten) ist fehlerhaft.

Konsequenz

Bietet ein flexibles Beweismittel, das die gewöhnliche Induktion umfasst und Beweise unterstützt, die auf mehreren vorherigen Werten beruhen, Rekurrenzrelationen und Korrektheitsbeweise bestimmter Algorithmen; es macht die Abhängigkeit von früheren Instanzen deutlich.

Umkehrung

Das Gegenteil ist die Beschränkung auf die Ein-Schritt-Induktion; einige mittels starker Induktion beweisbare Eigenschaften werden unter gewöhnlicher Induktion umständlich oder benötigen zusätzliche Lemmata, was den Unterschied in der Stärke der Hypothesen zeigt.

Abgrenzung

Gilt in wohlgeordneten nachfolgerbasierten Bereichen wie N; ist nicht automatisch auf nicht wohlgegründete Bereiche anwendbar oder auf Beweise, die transfinite Induktion verlangen, ohne die Hypothese an transfinite Vorgänger anzupassen.

Semantische Spannung

Spannung zur Ökonomie der Hypothesen: Starke Induktion ist auf N logisch äquivalent zur gewöhnlichen Induktion, wirkt aber stärker; die semantische Spannung liegt zwischen minimalen Annahmen und der Bequemlichkeit, die gesamte Vorgängermenge als gegeben zu akzeptieren.

Synthese

Starke Induktion erlaubt, alle kleineren Fälle als Hypothesen anzunehmen, um den nächsten Fall zu beweisen; sie vereinfacht Beweise, die kumulative Vorinformation benötigen, und ist auf N in der beweiskraft äquivalent zur gewöhnlichen Induktion.