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

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 all natürlichen Zahlen, sondern nur für n ≥ k.

Eine andere Verallgemeinerung wäre, als Induktionsvoraussetzung nicht nur den Fall n zu verwenden sondern alle m mit 0 ≤ m ≤ n. D.h. man darf annehmen, dass die Aussage für alle m ≤ 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.