Die vollständige Induktion ist eine mathematische Beweismethode, mit der eine Aussage für alle natürlichen Zahlen bewiesen wird. Da es sich um unendlich viele Zahlen handelt, kann solch ein Beweis nicht für jede Zahl einzeln erbracht werden. Er wird daher in zwei Etappen durchgeführt: als Induktionsanfang für eine kleinste Zahl (meist 1 oder 0) und als Induktionsschritt, der aus der Aussage für eine variable Zahl die entsprechende Aussage für die nächste Zahl logisch ableitet. Damit ist schon die Gültigkeit der Aussage für alle natürlichen Zahlen gezeigt.
Die Beweismethode beruht auf dem Prinzip der vollständigen Induktion (kurz: Induktionsprinzip), das entweder als Axiom gesetzt oder aus anderen Axiomen hergeleitet werden kann. Trotz ihres Namens handelt es sich bei der vollständigen Induktion um ein deduktives Verfahren.
Die vollständige Induktion lässt sich im Allgemeinen anwenden, wenn man eine Familie von Aussagen beweisen möchte, bei der jede Aussage von einer natürlichen Zahl abhängt bzw. eine „Nummer“ gegeben werden kann und es einen inhaltlichen Zusammenhang zwischen der Nummer und der Aussage gibt. Da solche Situationen über die Arithmetik hinaus in allen Gebieten der Mathematik auftreten, ist die vollständige Induktion von grundlegender Bedeutung für die gesamte Mathematik.
Beschreibung Mit sei eine mathematische Aussage gemeint, die von einer natürlichen Zahl abhängt.
Um zu beweisen, dass eine Aussage für alle natürlichen Zahlen gilt, genügt es, die folgenden beiden Schritte durchzuführen:
1. Induktionsanfang (auch Induktionsverankerung): Zeige, dass oder gilt.Ob der Induktionsanfang bei oder bei startet, hängt davon ab, ob man die Null zu den natürlichen Zahlen zählt oder nicht (respektive, ab welchem Index die Aussage überhaupt gelten soll). 2. Induktionsschritt (auch Induktionsschluss, Schluss von n auf n+1): Nimm an, dass die Aussage für ein beliebiges gilt (Induktionsannahme) und zeige dann, dass daraus folgt (Induktionsbehauptung).
Erläuterungen und Veranschaulichung mini|Vollständige Induktion als Dominoeffekt mit unendlich vielen Steinen Im Gegensatz zum ersten Schritt wird im zweiten Schritt kein konkreter Wert für festgelegt. Die Aussage wird nicht bewiesen, sondern als Induktionsannahme vorausgesetzt. Man zeigt, dass aus der Gültigkeit von die Aussage folgt, das heißt . Die Induktionsannahme wird auch Induktionsvoraussetzung genannt. Die Methode der vollständigen Induktion ist mit dem Dominoeffekt vergleichbar: Wenn der erste Dominostein fällt und durch jeden fallenden Dominostein der nächste umgestoßen wird, wird schließlich jeder Dominostein der unendlich lang gedachten Kette irgendwann umfallen. Die Allgemeingültigkeit einer Aussageform ist für bewiesen, wenn gültig ist (der erste Stein fällt um) und wenn zusätzlich gilt für (jeder Stein stößt beim Umfallen den nächsten Stein mit um).
Beispiele Gaußsche Summenformel
Die Gaußsche Summenformel besagt: Für alle natürlichen Zahlen gilt
.
Der Induktionsanfang ergibt sich unmittelbar:
Im Induktionsschritt ist zu zeigen, dass für aus der Induktionsvoraussetzung
die Induktionsbehauptung
(mit an der Stelle des der Induktionsvoraussetzung) folgt.
Dies gelingt, indem man die linke Seite der Induktionsbehauptung zunächst mithilfe der Induktionsvoraussetzung umformt und dann elementare Termumformungen vornimmt:
Mit dem Induktionsprinzip folgt die Gültigkeit der Gaußschen Summenformel für alle .
Summe ungerader Zahlen (Maurolicus 1575) Die schrittweise Berechnung der Summe der ersten ungeraden Zahlen,
, legt die Vermutung nahe: Die Summe aller ungeraden Zahlen von bis ist gleich dem Quadrat von : .
Sie wurde 1575 von Franciscus Maurolicus mit vollständiger Induktion bewiesen.Maurolycus: Arithemticorum Liber primus, S. 7, Proposition 15a. . Ein Beweis mit moderner Notation liest sich folgendermaßen:
Der Induktionsanfang mit gilt wegen .
Im Induktionsschritt ist zu zeigen, dass aus der Induktionsvoraussetzung
für ein
die Induktionsbehauptung
folgt. Er ergibt sich über folgende Gleichungskette, bei der in der zweiten Umformung die Induktionsvoraussetzung angewandt wird:
Mit dem Induktionsprinzip folgt die Gültigkeit der Aussage für alle .
Bernoullische Ungleichung Nach der bernoullischen Ungleichung gilt für alle reellen Zahlen und alle natürlichen Zahlen die Ungleichung
.
Der Induktionsanfang mit gilt wegen .Für muss gesetzt werden, damit die Bernoulli-Ungleichung ihre Gültigkeit auch für diesen Fall behält.
Den Induktionsschritt gewinnt man über folgende Ableitung, die im zweiten Schritt die Induktionsvoraussetzung verwendet, wobei die Bedingung dafür sorgt, dass der Term nicht negativ wird:
Nach dem Induktionsprinzip gilt die Behauptung für alle .
Färbung spezieller Landkarten mini|Durch Farbvertauschung der rechten Seite erhält man wieder eine zulässige Färbung. Die folgende Aussage ist eine Aussage über einen eher geometrischen Sachverhalt, der sich mithilfe vollständiger Induktion beweisen lässt:
Jede beliebige Anzahl von Geraden zerlegt die Ebene in Teilflächen. Es ist nun stets möglich, die Ebene mit zwei Farben so zu färben, dass keine zwei angrenzenden Teilflächen die gleiche Farbe bekommen („zulässige Einfärbung“).
Der Induktionsbeweis wird über die Anzahl von Geraden geführt. Der Induktionsanfang mit gilt, denn eine einzige Gerade teilt die Ebene in zwei Halbebenen, von denen die eine mit Farbe 1 und die andere mit Farbe 2 gefärbt wird.
Im Induktionsschritt ist zu zeigen, dass wenn sich eine von Geraden durchzogene Ebene mit zwei Farben zulässig einfärben lässt, sie sich auch zulässig mit zwei Farben einfärben lässt, wenn sie von Geraden durchzogen ist. Sei also für eine Ebene mit Geraden eine zulässige Färbung mit zwei Farben möglich. Zieht man in dieser Ebene eine -te Gerade, so wird die Ebene von ihr in zwei Halbebenen geteilt. In der einen Halbebene wird die Färbung bestehen gelassen, in der anderen werden die Farben vertauscht. Dadurch erhält man wieder eine zulässige Färbung mit zwei Farben (siehe Skizze). Also lässt sich auch eine mit Geraden durchzogene Ebene zulässig färben. Mit dem Induktionsprinzip folgt die Gültigkeit der Aussage für alle .
Pferde-Paradox
Das Pferde-Paradox ist ein Standardbeispiel für eine fehlerhafte Anwendung der vollständigen Induktion und illustriert die Bedeutung des Zusammenspiels von Induktionsverankerung und Induktionsschritt. Bei ihm wird die unsinnige Aussage, dass in einer Herde von Pferden alle immer die gleiche Farbe besitzen, anhand einer scheinbar korrekten Induktion bewiesen. Dabei ist der Induktionsschritt selbst korrekt, würde aber die Induktionsverankerung bei einem benötigen, während der (fehlerhafte) Beweis die Induktion bei verankert und somit schon der Schritt von auf scheitert.
Etymologie und Geschichte Die Bezeichnung Induktion leitet sich ab von lat. inductio, wörtlich „Hineinführung“. Der Zusatz vollständig signalisiert, dass es sich hier im Gegensatz zur Induktion im Sinne der Philosophie, die aus Spezialfällen ein allgemeines Gesetz erschließt und kein exaktes Schlussverfahren ist, um ein deduktives Beweisverfahren handelt.
Das Induktionsprinzip steckt latent bereits in der von Euklid überlieferten pythagoreischen Zahlendefinition: „Zahl ist die aus Einheiten zusammengesetzte Menge.“Euklids Elemente VII, Definition 2. Dazu: Wilfried Neumaier: Antike Rhythmustheorien, Kap. 1 Antike mathematische Grundbegriffe, S. 11–12. Euklid führte aber noch keine Induktionsbeweise, sondern begnügte sich mit intuitiven, exemplarischen Induktionen, die sich aber vervollständigen lassen. Auch andere bedeutende Mathematiker der Antike und des Mittelalters hatten noch kein Bedürfnis nach präzisen Induktionsbeweisen. Vereinzelte Ausnahmen im hebräischen und arabischen Sprachraum blieben ohne Nachfolge.
Lange galt ein Beweis von Franciscus Maurolicus von 1575 als älteste explizite vollständige Induktion (unten ausgeführt). Er erörterte aber das allgemeine Beweisverfahren noch nicht. Erst Blaise Pascal thematisierte das Induktionsprinzip mit Induktionsanfang und Induktionsschritt in seinem Traité du triangle arithmétique von 1654.Blaise Pascal: Traité du triangle arithmétique, S. 7, Conséquence douziesme, Le 1. (Induktionsanfang), Le 2. (Induktionsschritt), . Zur Verbreitung von Induktionsbeweisen trug ab 1686 Jakob I Bernoulli wesentlich bei.
Das Beweisverfahren wurde dann 1838 von Augustus De Morgan erstmals als Induktion oder sukzessive Induktion bezeichnet. 1888 prägte schließlich Richard Dedekind in seiner Schrift Was sind und was sollen die Zahlen? den Begriff vollständige Induktion. Über dieses Werk aus der Gründerzeit der Mengenlehre wurde sie zum allgemein bekannten, etablierten Beweisprinzip, auf das seither kein Zweig der Mathematik mehr verzichten kann. Ein Jahr später, 1889, formulierte Giuseppe Peano mit den Peanoschen Axiomen den ersten formalisierten Kalkül für die natürlichen Zahlen mit einem Induktionsaxiom, aus dem sich das Beweisschema der vollständigen Induktion herleiten lässt. Er zeigte mit formaler Strenge, dass aus seinen Zahlaxiomen, zu denen das Induktionsaxiom gehört, die ganze Arithmetik bis hin zu den reellen Zahlen ableitbar ist. Dadurch machte er die fundamentale Bedeutung und die Leistungskraft der Induktion voll bewusst.
Prinzip der vollständigen Induktion Das Beweisverfahren der vollständigen Induktion beruht auf dem Prinzip der vollständigen Induktion:
Ist eine Aussage über natürliche Zahlen, so dass bzw. gilt und für alle die Gültigkeit von die Gültigkeit von nach sich zieht, so gilt die Aussage für jede natürliche Zahl.
Als formale Schlussregel mit dem Ableitungsoperator lautet das Prinzip der vollständigen Induktion:
Logische Stellung des Induktionsprinzips Das Induktionsprinzip kann entweder als Axiom gesetzt oder aus anderen Axiomen hergeleitet werden. Im Rahmen der Arithmetik und Zahlentheorie wird es meist aus dem gleichwertigen fünften Peano-Axiom, dem Induktionsaxiom, hergeleitet. Dieses lautet:
Ist eine Teilmenge der natürlichen Zahlen mit den Eigenschaften: ist ein Element von Mit aus ist stets auch aus , dann ist .
Auch in anderen Konzepten der natürlichen Zahlen sind die Peano-Axiome und damit auch das Prinzip der vollständigen Induktion herleitbar, zum Beispiel bei der Definition der natürlichen Zahlen
als von 1 erzeugte geordnete Halbgruppe, die der zitierten pythagoreischen Zahlendefinition entspricht; als frei von 1 erzeugtes Monoid, das von der Addition der Zahlen ausgeht;Felscher: Naive Mengen und abstrakte Zahlen I, S. 130–132. als Algebra mit Nachfolger-Abbildung, die Dedekinds Zahlendefinition entspricht;Dedekind: Was sind und was sollen die Zahlen?, § 6, Erklärung 71.dargestellt als Dedekind-Tripel in: Felscher: Naive Mengen und abstrakte Zahlen I, S. 147. als kleinste induktive Menge, nämlich als kleinste Menge, die das Unendlichkeitsaxiom erfüllt, wie es in der Mengenlehre üblich ist; als Klasse der endlichen Ordinalzahlen, die nur eine allgemeine Mengenlehre ohne Unendlichkeitsaxiom voraussetzt.
Induktionsvarianten Induktion mit beliebigem Anfang Möchte man zeigen, dass eine Aussage nicht für alle natürlichen Zahlen, sondern nur für natürliche Zahlen größer oder gleich einer Zahl gilt, so besteht ein Induktionsbeweis aus den beiden folgenden Schritten:
Im Induktionsanfang zeigt man, dass die Aussage für gilt. Im Induktionsschritt zeigt man, dass für beliebiges gilt: Ist die Aussage für richtig, so auch für .
Beispiel Induktionsbeweis der Ungleichung für natürliche Zahlen : Induktionsanfang: Für ist die Ungleichung wegen erfüllt. Induktionsschritt: Für ein gelte (Induktionsvoraussetzung). Damit erhält man die Abschätzung
Dabei wurde die Induktionsvoraussetzung im zweiten Schritt verwendet und im vierten und sechsten Schritt die Voraussetzung .