Vollständige Induktion

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, daß 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 nur mit vollständiger Induktion.

Will man nicht nur hoffen, dass die Gaußsche Argumentation für jede natürliche Zahl zutrifft, sondern einen streng mathematischen Beweis, dann hilft die vollständige Induktion weiter.

Die Idee

Wenn wir wissen, daß 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, daß 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:

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, daß die zu beweisende Formel für n richtig ist, durch Anwendung von richtigen Rechenschritten bewiesen, daß 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, daß 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.

Nun ist klar, wie vorzugehen ist: Erst prüfen wir die Aussage für n=1 (das ist trivial nachzurechnen). Dann schließen wir anhand obiger Rechnung, daß sie auch für n=2 gilt. Sodann schließen wir, wieder anhand der Rechnung, daß sie auch für n=3 gilt, dann für n=4, n=5, ...

Der Witz am Induktionsbeweis ist nun, dass wir diese Schritte nicht mehr einzeln durchführen müssen: Wir haben ja bereits bewiesen, daß der Schritt für jedes einzelne n allgemein gilt. Und es ist sofort klar, daß 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, daß die zu beweisende Aussage für die unterste Zahl gilt (im Beispiel 1, sehr oft jedoch 0), und daß 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), daß 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, daß 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.

Tips 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äßlich. 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, daß die zu beweisende Aussage als Voraussetzung verwendet wird (dies wäre ein wertloser Zirkelschluß). 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.