## [Prinzip der Mathematischen Induktion](/de/node/63485) Definition Ein Beweisschema, das eine Eigenschaft für alle natürlichen Zahlen etabliert, indem ein Basisfall (gewöhnlich für 0 oder 1) gezeigt wird und ein Induktionsschritt, der beweist: wenn die Eigenschaft für ein beliebiges n gilt, dann gilt sie für n+1. ## Prinzip Prinzip Lokal-zu-global-Übertragung auf N: Die ordnende Regel ist, dass die Verifikation einer Basis und die Nachfolgerstabilität ausreichen, um eine Eigenschaft mittels wiederholter Anwendung des Induktionsschritts auf alle natürlichen Zahlen zu übertragen. ## Demonstration Demonstration Um eine Formel P(n) für alle n∈N zu beweisen, zeigt man P(0) und dass für beliebiges n aus P(n) folgt P(n+1). Beispielsweise beweist man per Induktion, dass die Summe der ersten n natürlichen Zahlen n(n+1)/2 ist, indem man den Basisfall n=0 und den algebraischen Induktionsschritt überprüft. ## Fehlanwendung Fehlanwendung Ordentliche Induktion anzuwenden, wenn der Induktionsschritt Annahmen über mehrere kleinere Werte erfordert (d. h. nur P(n)⇒P(n+1) zu verwenden, obwohl man Kenntnisse über alle k≤n bräuchte), oder keinen gültigen Basisfall für das beabsichtigte Gebiet zu etablieren. ## Konsequenz Konsequenz Gibt ein kanonisches Verfahren, unendlich viele Aussagen mit endlichem Aufwand zu beweisen; liegt rekursiven Definitionen, Beweisen der Korrektheit von Algorithmen auf den ganzen Zahlen und der Grundlage arithmetischer Eigenschaften zugrunde. ## Umkehrung Umkehrung Die Umkehr besteht darin zu zeigen, dass selbst bei vorhandenem Basisfall und einem behaupteten Induktionsschritt die Eigenschaft fehlschlagen kann, wenn Schritt oder Basis mangelhaft sind; das Weglassen des Basisfalls oder die Verwendung einer nichtstandardmäßigen Nachfolgerregel bricht die Übertragung auf alle natürlichen Zahlen. ## Abgrenzung Abgrenzung Gilt für wohlgeordnete, nachfolgerbasierte Bereiche wie N; findet keine direkte Anwendung auf Strukturen ohne klaren Nachfolger oder auf Beweise, die transfinite oder strukturelle Induktion erfordern, ohne entsprechende Anpassung. ## Semantische Spannung Semantische Spannung Spannung zur starken oder strukturellen Induktion: Die gewöhnliche Induktion setzt eine Ein-Schritt-Nachfolgerimplikation voraus, während starke/strukturierte Varianten Voraussetzungen über alle kleineren Instanzen zulassen oder auf Struktur statt auf numerischen Nachfolger induzieren. ## Synthese Synthese Mathematische Induktion ist die endliche, zweistufige Verifikation (Basis und Nachfolgeschritt), die Wahrheit über die natürlichen Zahlen propagiert und als primäres Mittel für arithmetische Identitäten, Korrektheitsbeweise für Ganzzahl-Algorithmen und rekursiv definierte Eigenschaften dient.