##  [Starke Induktion](/de/node/63487) 

 Definition

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

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

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

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

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

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

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

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

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.