Vollständige Induktion

Induktion oder vollständige Induktion 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).

Im einfachsten Fall zeigt man mittels vollständiger Induktion, dass eine Aussage für alle natürlichen Zahlen n wahr ist durch folgende Beweisschritte:

1. Induktionsanfang: Zeige, dass die Aussage für n = 0 wahr ist.
2. Induktionsschritt: Zeige, dass die Aussage für n + 1 wahr ist unter der Annahme, dass sie für n wahr ist (Induktionsannahme oder Induktionsvoraussetzung).

Hat man diese beiden Beweisschritte durchgeführt, dann ist die Aussage aus folgendem Grund für alle natürlichen Zahlen bewiesen:

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.

Beispiel

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

1. Als erstes zeigen wir den Fall n = 0. Die Summe der ersten 0 Zahlen ist natürlich 0. Es ist aber auch 0(0 + 1)/2=0.
2. Jetzt nehmen wir an, die Formel stimmt für n. Wir müssen zeigen, dass

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

   Wenn man hier (n + 2) ausmultipliziert, erhält man:

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

   Wenn man statt (n + 1)n/2 nun 1 + 2 + ... n einsetzt (Induktionsannahme), so ergibt sich obige Behauptung. Fertig.

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 $\geq$ k.

Eine andere Verallgemeinerung wäre, als Induktionsvoraussetzung nicht nur den Fall n zu verwenden, sondern alle m mit 0 $\leq$ m $\leq$ n. D.h. man darf annehmen, dass die Aussage für alle m $\leq$ n gilt. Dies lässt dem Beweis viel mehr Möglichkeiten, der Beweis ist aber ebenso gültig.

Es wird oft als Induktionsschritt nicht von n auf n + 1 geschlossen sondern von n - 1 auf n. Auch das ist zulässig.

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).

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.