Induktion oder vollständige Induktion oder Schluss von n auf n+1 ist eine Beweismethode, die üblicherweise eine Aussage für alle natürlichen Zahlen beweist. Sie funktioniert aber auch für allgemeinere Fälle (siehe unten).

Der Name dieses Beweisverfahrens leitet sich von lat. inductio = Hereinführung ab, in der Logik meint man damit den Schluss von speziellen Sachverhalten auf allgemeine Regeln, siehe Induktion (Logik). Das Verfahren der vollständigen Induktion ist jedoch kein induktives, sondern ein deduktives Prinzip.

Definition

Das Beweisverfahren der vollständigen Induktion beruht auf den Peano-Axiomen für die natürlichen Zahlen N. Eines dieser Axiome (das Induktionsaxiom) besagt:

Ist X eine Teilmenge von N mit der Eigenschaft, dass 0 (bzw. 1) in X liegt, und für jedes Element x von X liegt auch x+1 in X, dann ist X gleich N.

(Ob man bei 0 oder 1 beginnt, hängt davon ab, ob 0 in N liegt, das wird von verschiedenen Mathematikern verschieden definiert.)

Um zu beweisen, dass eine bestimmte logische Formel p für jede natürliche Zahl gilt, setzt man X als die Menge aller natürlichen Zahlen n, für die p(n) gilt, und wendet auf diese Menge das Induktionsaxiom an. Man zeigt also p(0), und damit 0 in X, sowie p(n) => p(n+1), und damit n in X => n+1 in X. Damit gilt X = N, und p gilt für alle natürlichen Zahlen.

Motivation

Hat man eine Aussage, die für alle natürlichen Zahlen gelten soll, und es ist nicht möglich, oder man hat noch keine Idee, die Aussage mit einer für alle Zahlen gültigen Rechnung zu beweisen, dann hat man ein Problem: Da die Anzahl der natürlichen Zahlen unendlich ist, kann man die Wahrheit der Aussage nicht für alle Zahlen einzeln beweisen.

Beispiel:

Zu zeigen ist, dass 1 + 2 + ... + n = n(n + 1)/2.

Für einzelne Zahlen ist die Formel leicht nachzurechnen:

n=1:

1 = 1

1·(1+1)/2 = 1

n=2:

1 + 2 = 3

2·(2+1)/2 = 3

usw.

Der Überlieferung nach sollte der kleine Gauß in der Schule die Zahlen von 1 bis 100 addieren, und überraschte den Lehrer mit einem richtigen, schnellen Ergebnis:

Er bildete 50 Zahlenpaare, die jeweils die Summe 101 haben: 100+1, 99+2, 98+3, ..., 51+50 und errechnete 50 * 101 = 5050 als Summe. Diese Summenermittlung kann man als gültigen Beweis für die spezielle Summenformel mit n=100 ansehen. (Denn man kann die Zahlenpaare wirklich auszählen.)

Statt 100 kann hier nun aber allgemein n genommen werden. Die Summe der Zahlenpaare wird zu n+1 und die Anzahl der Zahlenpaare von 50 allgemein zu n/2.

Diese Betrachtung gilt sogar, wenn n ungerade ist. Dann bleibt die mittlere Zahl der Zahlenreihe ohne Partner. Diese mittlere Zahl, die ohne Partner bleibt, ist (n+1)/2. Es können zunächst nur (n-1)/2 Zahlenpaare addiert werden, die alle die Summe n+1 haben. Am Schluss wird jedoch die übriggebliebene mittlere Zahl addiert und es ergibt sich als Summe

((n-1)/2)*(n+1) + (n+1)/2.

Hier wird (n+1) als Faktor nach hinten ausgeklammert und man erhält

((n-1)/2 + 1/2)*(n+1)= (n/2)*(n+1)

Die allgemeine Summenformel lautet daher, egal ob die Zahl der Summanden gerade oder ungerade ist:

1 + 2 + 3 + ... + n = (n/2)*(n+1)

Vollständige Induktion ist dabei scheinbar nicht im Spiel. An den Stellen jedoch, an denen auf die Summe und die Anzahl der Paare geschlossen wird, wird ein induktiver Schluss durchgeführt, denn man kann nicht für jedes n die Anzahl der Paare tatsächlich auszählen. Dieser Schluss ist aber kein Beweis, denn wie im Artikel Induktion (Logik) erläutert, können induktive Schlüsse fehlerhaft sein.

Diese Gauß zugeschriebene Begründung der Summenformel ist erst dann ein mathematischer Beweis, wenn sichergestellt ist, dass die beschriebene Umordnung der Zahlen und Addition der Paare für jede natürliche Zahl n möglich ist und das angegebene Ergebnis liefert - und das geht sehr gut mit vollständiger Induktion.

Die Idee

Wenn wir wissen, dass eine bestimmte Aussage sowohl

für n=1 gilt,

und,

wenn für ein beliebiges n, dann auch für n+1 gilt,

dann ist klar, dass sie für alle n gilt.

Damit scheint das Problem auf den ersten Blick nur anders formuliert, indem wir die nächste Zahl eben als die vorherige Zahl plus 1 bezeichnen; es sind immer noch unendlich viele Zahlen. Allerdings haben wir tatsächlich etwas gewonnen: indem wir "der Reihe nach" beweisen, können wir beim Beweis für n+1 bereits davon ausgehen, dass die Aussage für 1 bis n bereits gilt. Das heißt, wir können die Formel, die wir beweisen wollen, bereits im Beweis als Voraussetzung für Zahlen unterhalb der aktuellen Zahl (also unterhalb n+1) verwenden.

Angewandt auf obiges Beispiel sieht das so aus:

Wir wollen eine Formel finden die die Summe aller ungeraden Zahlen von 1 bis n vereinfacht und, was wichtiger ist, wir wollen diese Formel beweisen:

1 = 1 ; 1 + 3 = 4 ; 1 + 3 + 5 = 9 ; 1 + 3 + 5 + 7 = 16

Vermutung: Die Summe aller ungeraden Zahlen von 1 bis n ergibt eine Quadratzahl. Genauer gesagt:

Das ist zu zeigen. Wenn die Formel stimmt, dann müssen verschiedene Dinge zutreffen:

• n² + (2(n + 1) - 1) = (n + 1)² /* Die Perle */

Das letzte ist die Perle, die jetzt bewiesen werden muss. Nur die Perle hinzuschreiben, reicht als Beweis nicht aus.

• n² + (2(n + 1) - 1) = (n + 1)²

• n² + 2n + 2 - 1 = n² + 2n + 1

• n² + 2n + 1 = n² + 2n + 1

Damit ist die vollständige Induktion für abgeschlossen und bewiesen.

Angenommen, wir haben die Formel bereits bis zur Zahl n bewiesen. Wir wollen nun die Formel für 1 + 2 + 3 + ... + n + (n+1) beweisen.

Die ersten n Summanden bilden ebenfalls eine solche Summe, und zwar für n, was kleiner ist als n+1. Also dürfen wir - nach der Voraussetzung, dass wir die Formel für n bereits bewiesen haben - selbige hier anwenden, womit wir erhalten:

1 + 2 + 3 + ... + n + (n+1) = n(n+1)/2 + (n+1)

In diesem Ausdruck wird (n+1) ausgeklammert:

(n+1)*((n/2)+1)

und dies weiter umgeformt zu

(n+1)*((n+2)/2)

Das heißt, wir haben mit der gemachten Voraussetzung, dass die zu beweisende Formel für n richtig ist, durch Anwendung von richtigen Rechenschritten bewiesen, dass die Formel dann auch für n+1 gilt, denn die erhaltene Formel entspricht der Ausgangsformel, bei der n nur durch n+1 ersetzt ist.

Zu beachten ist, dass hier ein allgemeines n verwendet wurde. Damit ist der Schritt von n zu n+1 hier unabhängig vom konkreten Wert von n allgemein bewiesen.

Der Witz am Induktionsbeweis ist nun, dass wir diese Schritte nicht mehr einzeln durchführen müssen: Wir haben ja bereits bewiesen, dass der Schritt für jedes einzelne n allgemein gilt. Und es ist sofort klar, dass wir jede Zahl erreichen können, indem wir den Schritt nur oft genug anwenden (wenn man lange genug zählt, dann kann man bis zu jeder Zahl zählen). Das heißt, es muss nur gezeigt werden, dass die zu beweisende Aussage für die unterste Zahl gilt (im Beispiel 1, sehr oft jedoch 0), und dass sie, wenn sie bis zu einer Zahl gilt, das dann auch für die nächste Zahl tut.

Bezeichnungen

Den Beweis der Aussage für die erste Zahl nennt man Induktionsanfang, den Beweis für n+1 unter der Annahme (Induktionsannahme, Induktionsvoraussetzung), dass sie bis n gilt, nennt man Induktionsschritt.

Hat man diese beiden Beweisschritte durchgeführt, dann ist die Aussage für alle natürlichen Zahlen bewiesen. In Kurzform:

Wir wählen eine beliebige aber feste natürliche Zahl N und zeigen, dass die Aussage für N wahr ist:

  Die Aussage ist wahr für n = 0  (Induktionsanfang)
           und deshalb für n = 1  (Induktionsschritt)
           und deshalb für n = 2  (Induktionsschritt)
             ...
           und deshalb für n = N  (Induktionsschritt)

Nach endlich vielen Induktionsschritten gelangt man schließlich zur Aussage für N.

Diese Methode ist vergleichbar mit einem Dominoeffekt: Wenn der erste Dominostein fällt und durch jeden fallenden Dominostein ein weiterer umgestoßen wird, so fallen schließlich alle Dominosteine.

Tipps zur Anwendung

Es kann sich beim Beweis von Summenformeln mitunter als sehr mühsam erweisen, beim Induktionsschritt von n zu n+1 durch Umformungen die Struktur der Ausgangsformel neu zu konstruieren. Dies ist jedoch zur Beweisführung unerlässlich. Da ist es dann manchmal hilfreich, das Pferd von hinten aufzuzäumen. Beispielsweise ist das Ausmultiplizieren und Zusammenfassen von Gliedern oftmals leichter zu bewerkstelligen als das phantasievolle Aufspalten und Umordnen von Gliedern, um etwas ausklammern zu können. Um diesen Umstand zu nutzen, setzt man in die zu beweisende Formel n+1 für n ein und versucht, durch äquivalente Umformungen die Ausgangsformel für n zu isolieren. Da die Formel für n laut Voraussetzung gilt, ist der Beweis geführt, sobald das, was bei den äquivalenten Umformungen außer der isolierten Formel z. B. als Summand oder als zusätzlicher Faktor entsteht, dem entspricht, was beim Induktionsschritt hinzugefügt wird.

Dies ist nicht damit zu verwechseln, dass die zu beweisende Aussage als Voraussetzung verwendet wird (dies wäre ein wertloser Zirkelschluss). Wenn die zu beweisende Formel falsch sein sollte, würde entweder auch diese Operation nicht zum Ziel führen, oder die Formel würde den Induktionsanfang nicht erfüllen oder beides.

Verallgemeinerungen

Als erste Verallgemeinerung kann man als Startwert anstatt 0 eine beliebige natürliche Zahl k nehmen. Als Induktionsanfang ist dann der Fall n = k zu betrachten. Alles andere bleibt gleich. Die Aussage gilt dann eben nicht für alle natürlichen Zahlen, sondern nur für n ? k.

Eine andere Verallgemeinerung wäre, als Induktionsvoraussetzung nicht nur eine Aussage für die Zahl n zu verwenden, sondern eine Aussage für alle Zahlen m mit 0 ? m ? n. D.h. man darf beim Beweis für n+1 annehmen, dass die Aussage für alle m ? n gilt. Dies eröffnet der Beweisführung mehr Möglichkeiten.

Es wird oft als Induktionsschritt nicht von n auf n + 1 geschlossen sondern von n - 1 auf n. Auch das ist möglich.

Wenn man zu allgemeineren Mengen übergehen will, so zeigt sich, dass die vollständige Induktion auf allen Mengen anwendbar ist, auf denen eine partielle Ordnung definiert ist, wobei keine unendlichen absteigenden Ketten auftreten dürfen (weil sonst keine Anfangselemente gefunden werden können). Eine solche Menge heißt fundierte Menge.

Diese Art der Induktion kann auf Ordinalzahlen angewendet werden (Ordinalzahlen können unendlich und größer werden). In diesem Fall wird die Methode transfinite Induktion genannt. Sie ist wichtig in der Mengenlehre und der Topologie.