3. Vollständige Induktion
Die natürlichen Zahlen 0, 1, 2, 3, 4, …, n, n + 1, … sind durch die Nachfolgerbildung ausgezeichnet, die ausgehend von einem Anfangselement 0 (alternativ: 1) jeder natürlichen Zahl n einen eindeutigen Nachfolger n + 1 zuordnet. Das Anfangselement ist die einzige natürliche Zahl, die kein Nachfolger einer anderen natürlichen Zahl ist. Die Nachfolgeroperation ist zudem injektiv, d. h. haben zwei Zahlen den gleichen Nachfolger, so sind sie gleich.
Um nun zu zeigen, dass eine Eigenschaft ℰ(n) für alle natürlichen Zahlen n gilt, können wir so vorgehen: Wir zeigen, dass die Eigenschaft für das Anfangselement gültig ist und dass sie sich von jeder natürlichen Zahl auf ihren Nachfolger vererbt, d. h. dass aus ℰ(n) stets auch ℰ(n + 1) folgt. Ein solcher Beweis heißt ein Beweis durch (vollständige) Induktion. Als Schema notiert:
Beweis durch Induktion
Induktionsanfang (I. A.):
Es gilt ℰ(0).
Induktionsschritt (I. S.) von n nach n + 1:
Es gelte ℰ(n) (Induktionsvoraussetzung I.V.). Dann gilt ℰ(n + 1).
In dieses Schema ist der Beweis von ℰ(0) und der Beweis von ℰ(n + 1) (mit Hilfe von ℰ(n)) einzufügen. Sind diese beiden Beweise erbracht, so ist gezeigt, dass jede natürliche Zahl n die Eigenschaft ℰ(n) besitzt.
Das Paradebeispiel für einen Beweis durch Induktion ist:
Satz (Gauß-Summe)
Für alle natürlichen Zahlen n gilt:
0 + 1 + … + n = n(n + 1)2.
Beweis
Wir zeigen den Satz durch Induktion nach n ≥ 0. Die betrachtete Eigenschaft lautet:
ℰ(n) = „0 + … + n = n(n + 1)/2“.
Induktionsanfang n = 0:
Es gilt 0 = 0 (0 + 1)/2. Also gilt ℰ(0).
Induktionsschritt von n nach n + 1:
Es gelte ℰ(n), d. h. 0 + … + n = n (n + 1)/2 (I.V.). Dann gilt
| 0 + … + (n + 1) | = (0 + … + n) + (n + 1) |
| =I. V. n(n + 1)2 + (n + 1) | |
| = n(n + 1) + 2(n + 1)2 | |
| = (n + 1)(n + 2)2. |
Dies zeigt ℰ(n + 1).
Ein Beweis durch Induktion ist durch einen Induktionsanfang, einen Induktionsschritt und eine Induktionsvoraussetzung gekennzeichnet. Aus logischer Sicht ist die Induktionsvoraussetzung Teil des Induktionsschritts (und kein „dritter Teil“ der Induktion). Formal lautet die Induktion für die Eigenschaft ℰ(n):
ℰ(0) ∧ ∀n(ℰ(n) → ℰ(n + 1)) → ∀n ℰ(n).
Ein Beweis durch Induktion zeigt die linke Seite dieser Implikation:
ℰ(0) ∧ ∀n(ℰ(n) → ℰ(n + 1)).
Die linke Seite ist eine Konjunktion, deren Beweis in zwei Teile zerfällt:
(1) | ℰ(0) |
(2) | ∀(n)(ℰ(n) → ℰ(n + 1)) |
Der erste Teil ist der Induktionsanfang, der zweite der Induktionsschritt. Die Aussage (2) ist eine Allaussage. Zu ihrem Beweis starten wir mit:
„Sei n ∈ ℕ beliebig.“
Unser Beweisziel ist:
ℰ(n) → ℰ(n + 1)
Hierzu nehmen wir ℰ(n) an. Dies ist die Induktionsvoraussetzung. Nun zeigen wir mit Hilfe von ℰ(n), dass ℰ(n + 1) gilt.
Diese Argumentation wird durch „Induktionsanfang, Induktionsschritt (mit Induktionsvoraussetzung)“ schematisiert. Im Induktionsschritt verzichten wir der Kürze halber auf „Sei n beliebig.“ und beginnen gleich mit „Es gelte ℰ(n).“
Manchmal ist es nützlich, den Induktionsschritt von n − 1 nach n zu führen, sodass der zweite Teil des Beweises die Form „Induktionsschritt von n − 1 nach n“ besitzt. Die Induktionsvoraussetzung lautet nun ℰ(n − 1) und das Beweisziel innerhalb des Induktionsschritts ist ℰ(n). Wir führen dies anhand der Gauß-Summe explizit durch:
Beweis (Variante zur Illustration der Induktion)
Wir zeigen den Satz durch Induktion nach n ≥ 0.
Induktionsanfang n = 0:
Es gilt 0 = 0 (0 + 1)/2. Also gilt ℰ(0).
Induktionsschritt von n − 1 nach n:
Es gelte ℰ(n − 1), d. h. 0 + … + (n − 1) = (n − 1) n /2 (I.V.). Dann gilt
| 0 + … + n | = (0 + … + (n − 1)) + n |
| =I. V. (n − 1) n2 + n | |
| = (n − 1)n + 2n2 = n(n + 1)2. |
Dies zeigt ℰ(n).
Die Varianten der Induktion sind vielfältig. Prinzipiell ist alles möglich, was die natürlichen Zahlen vollständig einfängt. Wir können zum Beispiel zunächst ℰ(0), ℰ(1), ℰ(2), ℰ(3) zeigen und dann einen Induktionsschritt von n nach n + 1 für alle n ≥ 3 durchführen. Weiter können wir ℰ(0) und ℰ(1) zeigen und einen Induktionsschritt für alle n ≥ 0 von n nach n + 2 durchführen. Die Gültigkeit von ℰ(0) impliziert im Zusammenspiel mit dem Induktionsschritt, dass ℰ(n) für alle geraden Zahlen n gilt. Und aufgrund von ℰ(1) liefert der Induktionsschritt, dass ℰ(n) auch für alle ungeraden Zahlen n gilt.