Vollständige Induktion

Die vollständige Induktion ist eine mathematische Beweismethode, nach der eine Aussage für alle natürlichen Zahlen bewiesen wird, die größer oder gleich einem bestimmten Startwert sind. Da es sich um unendlich viele Zahlen handelt, kann eine Herleitung nicht für jede Zahl einzeln erbracht werden. Sie ist ein deduktives Verfahren. 

Der Beweis, dass die Aussage  für alle  ( meist 1 oder 0) gilt,
wird dabei in zwei Etappen durchgeführt:
 Im Induktionsanfang wird die Gültigkeit der Aussage  für eine kleinste Zahl  gezeigt.
 Im Induktionsschritt wird für ein beliebiges  die Gültigkeit der Aussage  aus der Gültigkeit von  geschlussfolgert.

Oder weniger formal formuliert:
 Induktionsanfang: Es wird bewiesen, dass die Aussage für die kleinste Zahl, den Startwert, gilt.
 Induktionsschritt: Folgendes wird bewiesen: Gilt die Aussage für eine beliebige Zahl, so gilt sie auch für deren Nachfolger.
Ausgehend vom Beweis für den Startwert erledigt der Induktionsschritt den Beweis für alle natürlichen Zahlen oberhalb des Startwertes.

Dieses Beweisverfahren ist von grundlegender Bedeutung für die Arithmetik und Mengenlehre und damit für alle Gebiete der Mathematik.

Aussageformen 
Die vollständige Induktion befasst sich mit der Gültigkeit von Aussageformen .

Beispiel (Siehe Gaußsche Summenformel):
 für 

Wenn man Werte für  einsetzt, erhält man Aussagen, die wahr oder falsch sind.

Die Aussagen im obigen Beispiel sind offensichtlich alle wahr. Da man das nicht für alle (unendlich viele) Zahlen nachrechnen kann, bedarf es eines besonderen Beweisverfahrens. Dieses liefert die vollständige Induktion.

Die Aussageform  ist allgemeingültig, wenn sie für alle  wahr ist.

Um die Allgemeingültigkeit der Aussageform  zu beweisen, zeigt man Folgendes:
  (Induktionsanfang) und
 aus der Aussage (der Induktionsannahme)  folgt stets die Aussage , und zwar für alle . (Das ist der Induktionsschritt.)

Veranschaulichung 

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 reißt beim Umfallen den nächsten Stein mit).

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 philosophischen Induktion, die aus Spezialfällen ein allgemeines Gesetz erschließt und kein exaktes Schlussverfahren ist, um ein anerkanntes deduktives Beweisverfahren handelt.

Das Induktionsprinzip steckt latent bereits in der von Euklid überlieferten pythagoreischen Zahlendefinition: „Zahl ist die aus Einheiten zusammengesetzte Menge.“ 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. 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 das Beweisschema der vollständigen Induktion herleitbar ist. 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.

Definition 
Seit Richard Dedekind ist die vollständige Induktion folgendermaßen festgelegt:
 Um zu beweisen, dass eine Aussage für alle natürlichen Zahlen  gilt, genügt es zu zeigen,
 dass sie für  gilt und
 dass aus der Gültigkeit der Aussage für eine Zahl  stets auch ihre Gültigkeit für den Nachfolger  folgt.

Als formale Schlussregel mit Ableitungsoperator  lautet die vollständige Induktion für eine Aussage  und eine natürliche Zahl :
 und 

Diese Schlussregel ist eine kompakte Formulierung des Beweisschemas der vollständigen Induktion, das didaktisch etwas ausführlicher formuliert werden kann:
 Soll die Formel  für alle natürlichen Zahlen  bewiesen werden, dann genügen dazu zwei Beweisschritte:
 der Induktionsanfang: der Beweis von ,
 der Induktionsschritt (auch »Schluss von  auf « genannt): der Beweis der Induktionsbehauptung  aus  und der Induktionsvoraussetzung (auch Induktionsannahme, engl. induction hypothesis) 
 Nach obiger Schlussregel folgt dann die Verallgemeinerung der Formel  auf alle natürlichen Zahlen  (der abschließende Induktionsschluss).

Die für natürliche Zahlen  aus einer Menge  zu beweisende Aussage  tritt hierbei in mindestens 3 Rollen auf:
{|
|-
| (1) || als Induktionsbehauptung || || für ein (einzelnes) beliebiges 
|-
| (2) || als Induktionsvoraussetzung || || für endlich viele kleinere natürliche Zahlen 
|-
|style="width:1.6em"| (3) || als zu beweisende allgemeine Aussage ||style="width:3.2em"| || für alle (und damit für unendlich viele) 
|}

Meist ist  oder .  ist jedoch möglich.

Denn da die Aussage  für  gleichwertig ist zur Aussage  für , lässt sich Dedekinds Induktion auf die vollständige Induktion von 0 aus zurückführen:

Die Axiomatik der natürlichen Zahlen durch Peano 
Peano bewies 1889 mit vollständiger Induktion die grundlegenden Rechenregeln für die Addition und Multiplikation: das Assoziativgesetz, Kommutativgesetz und Distributivgesetz.

Das Axiom der vollständigen Induktion 
Die vollständige Induktion ist ein Axiom der natürlichen Zahlen. Meist wird sie jedoch 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 Beweisverfahren 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
 als Algebra mit Nachfolger-Abbildung, die Dedekinds Zahlendefinition entspricht
 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

Beispiele

Gaußsche Summenformel 

Die Gaußsche Summenformel lautet:

Sie kann durch vollständige Induktion bewiesen werden.

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 folgendermaßen:
{|
|-
|style="width:11.2em;text-align:right" |  || style="width:14em" |  || (rot markiert die Induktionsvoraussetzung)
|-
| || 
|| (Nach Ausklammern von  ergibt sich …)
|-
|  ||  || (… die Induktionsbehauptung  wie oben angegeben.)
|}

Abschließend der Induktionsschluss:     Damit ist die Aussage  für alle  bewiesen.

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 :
 

Der zu beweisende allgemeine Satz lautet: . Ihn bewies Maurolicus 1575 mit vollständiger Induktion. Ein Beweis mit heute geläufigen Rechenregeln liest sich folgendermaßen:

Der Induktionsanfang  mit  ist wegen  leicht nachgeprüft.

Als Induktionsschritt ist zu zeigen: Wenn , dann . Er ergibt sich über folgende Gleichungskette, bei der in der zweiten Umformung die Induktionsvoraussetzung angewandt wird:

 (Die Induktionsvoraussetzung ist rot markiert.)

Bernoullische Ungleichung 
Die Bernoullische Ungleichung lautet für reelle Zahlen  mit  und natürliche Zahlen

.

Der Induktionsanfang mit  gilt hier wegen  (wobei die Definitionslücke an der Stelle  durch  stetig ergänzt ist).

Den Induktionsschritt gewinnt man über folgende Ableitung, die im zweiten Schritt die Induktionsvoraussetzung verwendet, wobei obige Bedingung für  dafür sorgt, dass der Term nicht negativ wird:

 (Die Induktionsvoraussetzung ist rot markiert.)

Das zweimalige Vorkommen des -Zeichens (in gleicher Richtung) lässt sich vereinfachen zu:

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.

Induktionsvarianten

Induktion mit beliebigem Anfang 
Induktionsbeweis der Ungleichung  für natürliche Zahlen :
 Der Induktionsanfang für  ergibt sich mit .
 Der Induktionsschritt gilt aufgrund folgender Ableitung, die im zweiten Schritt die Induktionsvoraussetzung und im vierten und sechsten Schritt die Voraussetzung  anwendet:

Die endlich vielen Fälle, die solch ein allgemeinerer Induktionsbeweis nicht abdeckt, können einzeln untersucht werden. Im Beispiel ist die Ungleichung für  offenbar falsch.

Starke Induktion

Induktion mit mehreren Vorgängern 
In manchen Induktionsbeweisen kommt man in der Induktionsvoraussetzung mit dem Bezug auf einen einzigen Vorgänger nicht aus, bspw. wenn eine Rekursionsformel mehrere Vorgänger enthält.
Der Induktionsanfang ist dann für mehrere Startwerte durchzuführen.
Ist zur Ableitung einer Formel etwa die Induktionsvoraussetzung für  und  nötig, dann ist ein Induktionsanfang für zwei aufeinander folgende Zahlen, also etwa 0 und 1, erforderlich. Als Induktionsvoraussetzung kann auch die Aussage für alle Zahlen zwischen dem Startwert und  dienen. Ein Beispiel ist der Beweis, dass jede natürliche Zahl  einen Primzahl-Teiler hat:
 Induktionsanfang: 2 ist durch die Primzahl 2 teilbar.
 Induktionsschritt: Die Aussage sei für alle  mit  erfüllt. Ist nun  eine Primzahl, so ist  selbst der gesuchte Teiler, und die Behauptung ist bewiesen. Ist  keine Primzahl, so gibt es zwei Zahlen  mit  und . In diesem Fall besitzt  gemäß Induktionsannahme  einen Primzahl-Teiler, etwa . Dann teilt  auch  und ist Primzahl-Teiler von . Damit ist auch für diesen zweiten Fall die Behauptung bewiesen.

Formale Definition 
Die Aussage  ist für alle  gültig, wenn Folgendes für jedes beliebige  gezeigt wird:
{|
|-
|style="width:16em"| (Induktionsschritt:) ||  .
|}
Das Beweisschema der starken Induktion besteht demgemäß nur aus dem Induktionsschritt.

Induktionsanfänge, wie sie in der gewöhnlichen Induktion vorkommen, also bspw. der Nachweis der Aussage , sind im Induktionsschritt  Es kann überdies vorkommen, dass mehr als eine Anfangsaussage vorab zu zeigen ist (siehe Fibonacci-Folge).

Offensichtlich folgt die (in der Einleitung formulierte) gewöhnliche vollständige Induktion aus der starken Induktion. Man kann aber auch die starke Induktion mit Hilfe der gewöhnlichen vollständigen Induktion beweisen.

 dann gilt
{|
|-
|style="width:1.3em" | || style="width:16em" |  für alle . || (Induktionsschluss gewöhnlich ⇒ stark)
|}
Wir definieren die folgende Aussage  für natürliche Zahlen 
 
und zeigen ihre Gültigkeit mittels gewöhnlicher vollständiger Induktion.

Induktionsanfang: Da , die leere Und-Verknüpfung ist, gilt  gemäß Anmerkung sofort.

(Gewöhnlicher) Induktionsschritt von  nach :
 Sei  beliebig und es gelte , d. h. es gelte
 .
 Wegen der (Induktionsvoraussetzung gewöhnlich ⇒ stark) folgt daraus
 .
 Zusammengenommen mit  ergibt dies
 .
Damit haben wir  gezeigt, welches  ist, und der gewöhnliche Induktionsschritt ist fertig. Wir schließen (gewöhnlicher Induktionsschluss):
 Für alle  gilt .
Wegen  ergibt sich a fortiori der starke Induktionsschluss:
 Für alle  gilt .  ■
|}

Trotz dieser prinzipiellen Gleichwertigkeit in der Beweisstärke ist der Unterschied in der Ausdrucksstärke wegen der beliebig vielen Startwerte und der Möglichkeit des Rückgriffs auf beliebig viele Vorgänger groß, besonders bei rekursiven Definitionen. Das bedeutet aber keineswegs, dass letztere Definitionen nicht in gewöhnliche Rekursionen überführt werden können.

 Beispiel
 Die Folge  sei definiert durch die Rekursionsformel       .Dann gilt:       .Der Beweis mittels starker Induktion ist trivial.Die Rekursion lässt sich jedoch auch unschwer in eine auf einen einzigen Vorgänger umformen:              .

Induktion mit Vorwärts-Rückwärts-Schritten 
Augustin-Louis Cauchy führte 1821 eine Induktionsvariante vor, bei der der vorwärts gerichtete Induktionsschritt Sprünge macht (nämlich von  nach ) und die entstandenen Lücken nachträglich durch eine rückwärts gerichtete Herleitung von  nach  auf einen Schlag gefüllt werden.

Beispiel: Ungleichung vom arithmetischen und geometrischen Mittel

Weitere Induktionsvarianten 
Es gibt auch Sachlagen, bei denen Aussagen über alle ganzen Zahlen (positive und negative) mit vollständiger Induktion bewiesen werden können. Der Beweis in die positive Richtung geschieht wie gewohnt mit einem beliebigen Induktionsanfang und dem positiven Induktionsschritt von  nach . Danach kann es möglich sein, den Induktionsschritt in die negative Richtung von  nach  auszuführen. Beispielsweise lässt sich bei der Fibonacci-Folge die Rekursionsgleichung in die Gegenrichtung umstülpen.

Die vollständige Induktion ist von natürlichen Zahlen verallgemeinerbar auf Ordinalzahlen. Bei Ordinalzahlen, die größer als die natürlichen Zahlen sind, spricht man dann von transfiniter Induktion.

Die Induktion ist auch übertragbar auf sogenannte fundierte Mengen, die eine der Zahlenordnung vergleichbare Ordnungsstruktur aufweisen; hier spricht man zuweilen von struktureller Induktion.

Rekursive oder induktive Definition 
Die rekursive Definition – auch induktive Definition genannt – ist ein der vollständigen Induktion analoges Verfahren, bei der ein Term durch einen Rekursionsanfang und einen Rekursionsschritt definiert wird.

Beispiel einer rekursiven Funktion
 

Mit Hilfe der vollständigen Induktion kann man beweisen (Gaußsche Summenformel):
 
Die geschlossene Formel erspart die umständliche rekursive Berechnung.

Umgekehrt zeigt das nächste Beispiel, dass eine rekursive Berechnung günstiger sein kann.

Beispiel einer rekursiv definierten Funktion:
{|
|-
|rowspan="3" style="vertical-align:middle"| 
|  || || für   ,
|-
|  ||style="width:2em"| || für    und  ungerade,
|-
|  || || für    und  gerade.
|}
Man kann mit Hilfe der vollständigen Induktion nach  zeigen, dass
      für  ist.

Der Vorteil dieser rekursiven Definition ist, dass man bei der Berechnung hoher Potenzen nicht  Multiplikationen, sondern nur Multiplikationen in der Größenordnung von  hat. Sehr hohe Potenzen werden zum Beispiel bei der RSA-Verschlüsselung von Nachrichten verwendet.

Die rekursive Definition hat wie die Induktion allerlei differenzierte Varianten.

Weblinks 

 Vollständige Induktion mit vielen Beispielen.
 Vollständige Induktion. henked.de
 emath.de (PDF; 837 kB) Umfangreiche Aufgabensammlung zur vollständigen Induktion
 Joachim Mohr: Crashkurs in die vollständige Induktion. kilchb.de
 Christian Spannagel: Vorlesungen zur vollständigen Induktion.
 Beweise mit vollständiger Induktion auf Video anschaulich erklärt:
 .
 .
 .
 .

Einzelnachweise 

Mathematischer Grundbegriff
Beweis (Mathematik)
Wikipedia:Artikel mit Video