Mathe für Nicht-Freaks: Vollständige Induktion

Die vollständige Induktion ist eine wichtige Beweismethode in der Mathematik, die dir in deinem Studium noch häufig begegnen wird. Dabei kann man die Wirkungsweise der vollständigen Induktion gut mit dem Dominoeffekt vergleichen. Doch wie kann ein solcher Beweis mit dem Dominoeffekt in der Mathematik angewandt werden? Betrachten wir dazu eine Beispielaufgabe, die man mit Hilfe der vollständigen Induktion lösen kann.

Eine Beispielaufgabe

Carl Friedrich Gauß

Unsere Beispielaufgabe ist die Gaußsche Summenformel, auch kleiner Gauß genannt. Sie heißt so, weil der kleine 9 jährige Carl Friedrich Gauß diese Summenformel in einer Mathestunde gefunden hat (Gauß ist der geniale Mathematiker, dessen Gesicht später den 10-Mark-Schein in Deutschland zieren sollte). Laut Anekdote konnte der kleine Gauß die ersten 100 natürlichen Zahlen sofort und ohne größere Probleme aufsummieren. Wenn man seinen „Trick“ verallgemeinert, kommt man auf folgende Formel:

Beispiel (Der kleine Gauß):

Beweise, dass für alle natürlichen Zahlen $n$ die Summe $1 + 2 + 3 + \dots + n$ gleich ${n \cdot (n+1)} \over 2$ ist.

Ok, wir könnten nun anfangen, diese Behauptung für einzelne natürliche Zahlen $n$ zu beweisen:

• Für $n = 1$:

  $1 = \frac{1(1+1)}{2}$, stimmt ✔

• Für $n = 2$:

  $1 + 2 = 3 = \frac{2(2+1)}{2}$, stimmt ✔

• und so weiter …

Doch dies ist keine Möglichkeit, einen Beweis zu führen, da es unendlich viele natürlichen Zahlen gibt und es immer mühseliger wird und unmöglich ist, alle Summen auszurechnen (Denk an die armen Mitschüler von Gauß, wie sie versucht haben, die einzelnen Zahlen nacheinander aufzusummieren). Wir brauchen also eine andere Lösungsmethode. Ich habe dir gesagt, dass die vollständige Induktion ein Beweis mit dem Dominoeffekt ist und sich auch diese Aufgabe durch vollständige Induktion lösen lässt. Doch wie lässt sich ein Dominoeffekt in dieser Aufgabe ausnutzen (Hast du schon eine Idee?). Analysieren wir dazu die Aufgabe.

Wenn du dir die Aufgabe durchliest, kannst du feststellen, dass es in der Aufgabenstellung eine freie Variable gibt (die natürliche Zahl $n$). Wenn du für diese freie Variable einen bestimmten Wert einsetzt, entsteht eine konkrete Aussage. Durch Nachrechnen kannst du feststellen, ob diese Aussage wahr oder falsch ist. Wenn du z. B. für $n$ die Zahl 42 einsetzt, entsteht die (wahre) Aussage:

Die Summe $1+2+3+\dots +42$ ist gleich ${{42 \cdot (42+1)} \over 2}$.

Ein solcher Ausdruck, der eine (oder auch mehrere) freie Variable enthält und die durch Belegung dieser Variablen mit Werten in eine Aussage übergeht, wird Aussageform genannt und mit $A(n)$ bezeichnet. $A(n)$ heißt soviel wie: eine Aussageform mit dem Namen $A$ und der freien Variablen $n$, also $A$ in Abhängigkeit von $n$. Die obige Aussage wäre demnach $A(42)$. Hier einige weitere Beispiele:

$A(1)$ lautet: Die Summe $1$ ist gleich ${{1 \cdot (1+1)} \over 2}$.

$A(4)$ lautet: Die Summe $1+2+3+4$ ist gleich ${{4 \cdot (4+1)} \over 2}$.

Unsere Aufgabe ist es, zu zeigen, dass die Aussageform für alle natürlichen Zahlen $n$ wahr ist. Wir müssen also beweisen, dass wenn wir für $n$ irgendeine beliebige natürliche Zahl einsetzen, die daraus entstehende Aussage wahr ist. Eine solche Aussageform, die für alle natürlichen Zahlen wahr ist, nennt man allgemeingültig in $\N$.

Unsere Aufgabe ist eine Dominoreihe

Doch wie kann man jetzt den Dominoeffekt ins Spiel bringen? Dazu werden wir eine Analogie zwischen der Aussageform und einer Dominoreihe finden. Stell dir dazu eine unendlich lange Dominoreihe vor, die irgendwo im Raum anfängt. Diese Dominoreihe ist durchnummeriert (der erste Dominostein ist die 1, der Zweite die 2 und so weiter). Nun führen wir eine Beziehung zwischen der Dominoreihe und der zu beweisenden Aussageform $A(n)$ ein. Wir sagen, dass der erste Dominostein für die Aussage $A(1)$ steht, der zweite Dominostein für die Aussage $A(2)$ steht und so weiter. Gehen wir nun davon aus, dass wenn ein Dominostein umfällt, die Wahrheit der zu diesem Dominostein zugewiesenen Aussage bewiesen ist. Wenn also Dominostein Nummer 7 umfällt, die Aussage $A(7)$ wahr ist und beim Fall von Dominostein Nummer 23, ist die Aussage $A(23)$ wahr.

Der Dominoeffekt

Wir haben nun das Problem der Aufgabe auf das von uns in der Kindheit bekannte Problem zurückgeführt, dass wir eine Dominoreihe zum Umfallen bringen wollen.

Frage: Doch was musst du machen, damit alle Dominosteine umfallen? Wie muss dazu die Dominoreihe aufgebaut sein?

Wenn du darüber nachdenkst, kommst du auf 2 Schritte, die du einhalten musst, damit alle Dominosteine umfallen.

Schritt 1: Du musst den ersten Dominostein umstoßen.

Schritt 2: Die Dominoreihe muss so aufgebaut sein, dass wenn ein Dominostein umfällt auch sein Nachfolger umfällt.

Wenn beide Schritte eingehalten werden, fallen alle Steine in der Dominoreihe nacheinander um (Dominoeffekt). Du musst also dafür Sorge tragen, dass beide Schritte erfüllt sind.

Frage: Wie lauten nun die beiden Lösungsschritte, wenn wir die obigen beiden Schritte durch unsere Analogie in das Ausgangsproblem zurückübersetzen?

Lösungsschritt 1: Die Aussageform ist für $n=1$ wahr.

Lösungsschritt 2: Wenn die Aussageform für ein beliebiges $n=k$ wahr ist, muss die Aussageform auch für den Nachfolger $n=k+1$ wahr sein.

Veranschaulichung der vollständigen Induktion

Dass durch den Beweis dieser beiden Lösungsschritte die Aufgabe gelöst ist, kannst du folgendermaßen erkennen (beachte den dabei eintretenden Dominoeffekt!). Zunächst wird im ersten Lösungsschritt gezeigt, dass die Behauptung für $n=1$ wahr ist. Wenn wir nun Lösungsschritt 2 auf dieses Wissen anwenden (wenn also $n=k=1$ ist), folgt, dass die Behauptung auch für $n=k+1=1+1=2$ wahr sein muss. Wenn wir nochmal Lösungsschritt 2 anwenden, folgt die Wahrheit für $n=2+1=3$ und bei nochmaliger Anwendung für $n=3+1=4$ und so weiter...

Damit müssen wir nur die obigen beiden Lösungsschritte beweisen, um die Aufgabe zu lösen. Hier der Beweis zu den beiden Lösungsschritten:

Lösungsschritt 1:

Für $n=1$ lautet die zu beweisende Aussage $1={{1 \cdot (1+1)} \over 2}$. Durch Nachrechnen der rechten Seite, zeigt man, dass diese Aussage wahr ist.

Lösungsschritt 2:

Gehen wir davon aus, dass die Aussage für $n=k$ bereits bewiesen ist. Gehen wir also davon aus, dass gilt:

$1+2+3+ \dots +k = {{k \cdot (k+1)} \over 2}$ (Anfangsgleichung: Das haben wir gegeben)

Wir müssen nun die Summenformel für $k+1$ beweisen. Wir müssen also beweisen, dass gilt:

$1+2+3+ \dots + k + (k+1) = {{(k+1) \cdot ((k+1)+1)} \over 2}$ (Zielgleichung: Das wollen wir beweisen)

Fangen wir auf der linken Seite dieser zu beweisenden Aussage an:

$\begin{alignat}{1} \overbrace{1+2+3+ \dots +k+(k+1)}^{\text{linke Seite der Zielgleichung}} & = { \color{OliveGreen}(1+2+ 3+ \dots +k) } + (k+1) \\[3px] & \qquad{\color{OliveGreen}\downarrow \mathrm{\ Anfangsgleichung\ einsetzen}} \\[3px] & = { \color{OliveGreen} {{k \cdot (k+1)} \over 2}} + (k+1) \\[3px] & \qquad\left\downarrow\ \text{Summe in Bruch zusammenfassen}\right. \\[3px] & = {{k \cdot (k+1) + 2(k+1)} \over 2} \\[3px] & \qquad\left\downarrow\ (k+1) \text{ ausklammern}\right. \\[3px] & = {{(k+1) \cdot (k+2)} \over 2} \\[3px] & \qquad\left\downarrow\ k+2=(k+1)+1\right. \\[3px] & = \underbrace{{{(k+1) \cdot ((k+1)+1)} \over 2}}_{\text{rechte Seite der Zielgleichung}} \\ \end{alignat}$

Wir haben so eine kurze und elegante Lösung der Aufgabe gefunden (Gauß' Lehrer wäre sicherlich stolz auf uns ^^).

Das Prinzip der vollständigen Induktion

Doch was ist nun das Prinzip der vollständigen Induktion? Schauen wir uns dazu die obige Beispielaufgabe an und versuchen das dabei verwendete Beweisprinzip zu abstrahieren. (Kannst du dieses Prinzip schon jetzt erklären?)

Hinweis:

Im Folgenden wird die vollständige Induktion so beschrieben, wie sie in vielen Lehrbüchern definiert wird. Das Prinzip kann aber auch allgemeiner formuliert werden (siehe späterer Abschnitt). Dementsprechend kann es dir bei einigen Aufgaben passieren, dass du die vollständige Induktion (ein wenig) anders anwendest, als sie hier beschrieben wird.

Zunächst stellen wir fest, dass es sich um eine Aussageform handelt, deren eine freie Variable eine natürliche Zahl ist. Die Aufgabe besteht nun darin, zu beweisen, dass die Aussageform für alle natürlichen Zahlen wahr ist, dass also die Aussageform allgemeingültig in $\N$ ist.

Nun haben wir im ersten Schritt bewiesen, dass die Aussageform für die kleinste natürliche Zahl wahr ist (in unserem obigen Beispiel war diese kleinste natürliche Zahl die 1; in bestimmten Fällen kann sie aber auch die 0 sein, je nachdem wie die zu beweisende Aufgabe lautet). Dieser Schritt wird Induktionsanfang genannt und entspricht in unserer obigen Analogie dem Umstoßen des ersten Dominosteins.

Im zweiten Schritt haben wir bewiesen, dass wenn die Aussageform für eine beliebige natürliche Zahl $k$ wahr ist, sie auch für $k+1$ wahr sein muss. Dieser Schritt wird Induktionsschritt genannt und entspricht in unserer obigen Analogie der Tatsache, dass die Dominoreihe so aufgebaut sein muss, dass wenn ein Dominostein umfällt, auch der nächste Dominostein umfallen muss. Die dabei getroffene Annahme, dass die Aussageform für ein beliebiges $k$ wahr ist, nennt man Induktionsvoraussetzung (das war unsere obige Anfangsgleichung). Die unter Annahme der Induktionsvoraussetzung zu beweisende Aussage $A(k+1)$ wird Induktionsbehauptung genannt (das war unsere obige Zielgleichung).

$\overbrace{\underbrace{A(k)}_{\text{Induktionsvoraussetzung}} \Rightarrow \underbrace{A(k+1)}_{\text{Induktionsbehauptung}} }^{\text{Induktionsschluss}}$

Fassen wir zusammen: Die vollständige Induktion lässt sich beim Beweis der Allgemeingültigkeit von Aussageformen $A(n)$ anwenden, deren eine freie Variable $n$ eine natürliche Zahl ist. Zum Beweis durch vollständige Induktion musst du folgendes leisten:

1. Induktionsanfang: Beweise, dass $A(1)$ eine wahre Aussage ist.

2. Induktionsschritt: Beweise, dass wenn $A(n=k)$ wahr ist, auch $A(n=k+1)$ wahr sein muss. Dabei können folgende Teilschritte identifiziert werden:

2a. Induktionsvoraussetzung: Die Aussage $A(k)$ ist wahr für ein bestimmtes $k\in\N$.

2b. Induktionsbehauptung: Die Aussage $A(k+1)$ ist wahr.

2c. Beweis des Induktionsschritts: Beweise, dass unter Annahme der Induktionsvoraussetzung die Induktionsbehauptung folgt.

Schritt 2 hat dementsprechend folgende Form:

2a Induktionsvoraussetzung (Anfang des Beweises; ist gegeben)

$\vdots$

(2c Der Beweis)

$\vdots$

2b Induktionsbehauptung (Ziel des Beweises; soll bewiesen werden)

Oftmals (insbesondere bei einfachen Aufgaben) werden Schritt (2a) und (2b) weggelassen, wenn sie dem Autor zu trivial erscheinen, um aufgeschrieben zu werden. Dies kann möglicherweise auch auf den Induktionsanfang bzw. den Induktionsschritt zutreffen, wenn der Autor z. B. sie für zu einfach hält. Manchmal gibt der Autor eines Buches auch nur den Hinweis, dass eine bestimmte Aufgabe durch vollständige Induktion bewiesen werden kann und überlässt dem Leser diesen Beweis. In diesem Kapitel werden aber alle Teilschritte aufgeführt.

Wenn wir nun die obige Beweismethode in mathematischer Sprache formulieren, erhalten wir die Definition der vollständigen Induktion.

Definition (Vollständige Induktion):

Sei $A(n)$ eine Aussageform in der freien Variablen $n \in \N$. Sei $A(1)$ (oder $A(0)$) eine wahre Aussage (Induktionsanfang) und die Implikation $A(k) \Rightarrow A(k+1)$ für alle $k \in \N$ erfüllt (Induktionsschritt), dann ist die Aussageform allgemeingültig in $\N$.

Hier noch eine Grafik, welche das Prinzip der vollständigen Induktion gut veranschaulicht: