Vollständige Induktion – Serlo „Mathe für Nicht-Freaks“

Die vollständige Induktion ist eine wichtige Beweismethode, die dir in deinem Studium noch häufig begegnen wird. Dabei kann man ihre Wirkungsweise gut mit dem Dominoeffekt vergleichen. Doch wie sieht ein „Beweis mit dem Dominoeffekt“ konkret aus? Betrachten wir zunächst eine Beispielaufgabe, die mit Hilfe der vollständigen Induktion gelöst werden kann.

Eine Beispielaufgabe

Carl Friedrich Gauß

Unsere Beispielaufgabe ist die „Gauß'sche Summenformel“, auch „kleiner Gauß“ genannt. Sie heißt so, weil der neunjährige Carl Friedrich Gauß diese Summenformel in einer Mathestunde entdeckt hat (Gauß ist der geniale Mathematiker, dessen Gesicht später den Zehn-Mark-Schein in Deutschland zieren sollte). Laut Anekdote konnte der kleine Gauß die Summe der ersten $100$ natürlichen Zahlen sofort und ohne längeres Rechnen angeben.

Seine Idee war dabei, dass es zwischen $1\ldots 100$ genau $50$ Paare von Zahlen gibt, deren Summe $101$ ist: $1+100$, $2+99$, $3+98$ und so weiter bis $50+51$. Wenn man seinen „Trick“ verallgemeinert, kommt man auf folgende Formel:

Für jede natürliche Zahl $n$ ist die Summe $1+2+3+\dots +n$ gleich ${\frac {n\cdot (n+1)}{2}}$.

Gut. 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 auch ✔

und so weiter und so fort…

Doch dies ist keine Möglichkeit, einen Beweis zu führen, da es unendlich viele natürliche Zahlen gibt und es daher grundsätzlich 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. Wir haben dir in der Einleitung dieses Kapitels gesagt, dass diese Aufgabe durch vollständige Induktion gelöst werden kann und dass diese Beweismethode einem Dominoeffekt ähnelt. Doch wie lässt sich ein Dominoeffekt in dieser Aufgabe ausnutzen? Analysieren wir dazu die Aufgabe:

Wenn du dir die Aufgabe durchliest, wirst du erkennen, 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 ${\frac {42\cdot (42+1)}{2}}$.

Ein solcher Ausdruck, der eine (oder auch mehrere) freie Variable enthält und der durch Belegung dieser Variablen mit Werten in eine Aussage übergeht, wird Aussageform genannt und mit $A(n)$ bezeichnet. $A(n)$ heißt so viel 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 ${\frac {1\cdot (1+1)}{2}}$.

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

Unsere Aufgabe ist es, zu beweisen, dass die Aussageform bei Einsetzung aller natürlichen Zahlen $n$ immer eine wahre Aussage ergibt. Eine solche Aussageform, die für alle natürlichen Zahlen stets eine wahre Aussage liefert, nennt man „allgemeingültig in $\mathbb {N}$“.

Unsere Aufgabe ist mit einer Dominoreihe vergleichbar.

Doch wie kann man jetzt den Dominoeffekt ins Spiel bringen? Dazu werden wir eine Analogie zwischen der Aussageform und einer Dominoreihe finden: Stelle dir dazu eine unendlich lange Dominoreihe vor, die irgendwo im Raum anfängt. Diese Dominoreihe ist durchnummeriert (der erste Dominostein ist die Eins, der zweite die Zwei 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)$ und so weiter. Gehen wir nun davon aus, dass beim Fallen eines Dominosteins die Wahrheit der ihm zugewiesenen Aussage bewiesen ist. Wenn also Dominostein Nummer $7$ umfällt, ist die Aussage $A(7)$ wahr 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 aus der Kindheit bekannte Problem zurückgeführt, eine Dominoreihe zum Umfallen bringen zu wollen.

Frage: Was musst du tun, damit alle Dominosteine umfallen? Wie muss dazu die Dominoreihe aufgebaut sein?

Wenn du darüber nachdenkst, kommst du auf zwei Bedingungen, die du erfüllen musst, damit alle Dominosteine umfallen.

1. Du musst den ersten Dominostein umstoßen.
2. Die Dominoreihe muss so aufgebaut sein, dass beim Fall eines Dominosteins auch sein Nachfolger umfällt.

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

Frage: Wie lauten die beiden Lösungsschritte aus der Antwort der eben gestellten Frage, wenn wir diese in das Ausgangsproblem zurückübersetzen, die Allgemeingültigkeit einer Aussageform zu beweisen?

1. Erster Lösungsschritt: Zeige, dass die Aussageform für $n=1$ erfüllt ist.
2. Zweiter Lösungsschritt: Zeige, dass unter der Annahme, dass die Aussageform für ein beliebiges $n=k$ erfüllt ist, die Aussageform auch für den Nachfolger $n=k+1$ erfüllt sein muss.

Veranschaulichung der vollständigen Induktion

Dass durch den Beweis dieser beiden Lösungsschritte die Aufgabe gelöst ist, kannst du folgendermaßen erkennen: Zunächst wird im ersten Lösungsschritt gezeigt, dass die Behauptung für $n=1$ wahr ist. Wenn wir nun dieses Wissen auf den zweiten Lösungsschritt 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 den zweiten Lösungsschritt anwenden, folgt die Wahrheit für $n=2+1=3$ und bei nochmaliger Anwendung für $n=3+1=4$ und so weiter…

Wir müssen also die obigen beiden Lösungsschritte beweisen, um die Aufgabe zu lösen. Hier ist der Beweis mit den beiden notwendigen Lösungsschritten:

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

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

$\underbrace {1+2+3+\dots +k={\frac {k\cdot (k+1)}{2}}} _{\text{Die Gleichung haben wir gegeben.}}$

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

$\underbrace {1+2+3+\dots +k+(k+1)={\frac {(k+1)\cdot ((k+1)+1)}{2}}} _{\text{Zielgleichung: Diese Gleichung soll gezeigt werden}}$

Durch Termumformungen zeigen wir nun, dass die linke Seite der Gleichung gleich der rechten Seite der Gleichung ist. Wir müssen also Termumforungen der folgenden Form finden:

$1+2+3+\dots +k+(k+1)=\ldots =\ldots =\ldots ={\frac {(k+1)\cdot ((k+1)+1)}{2}}$

Die notwendigen Termumformungen sind:

${\begin{aligned}\overbrace {1+2+3+\dots +k+(k+1)} ^{\text{linke Seite der Zielgleichung}}&={\color {OliveGreen}(1+2+3+\dots +k)}+(k+1)\\[0.5em]&\qquad {\color {OliveGreen}\downarrow \ {\text{Gegebene Gleichung einsetzen}}}\\[0.5em]&={\color {OliveGreen}{\frac {k\cdot (k+1)}{2}}}+(k+1)\\[0.5em]&={\frac {k\cdot (k+1)}{2}}+{\frac {2\cdot (k+1)}{2}}\\[0.5em]&={\frac {k\cdot (k+1)+2\cdot (k+1)}{2}}\\[0.5em]&\qquad {\color {Gray}\left\downarrow \ a\cdot b=b\cdot a\right.}\\[0.5em]&={\frac {(k+1)\cdot k+(k+1)\cdot 2}{2}}\\[0.5em]&\qquad {\color {Gray}\left\downarrow \ (k+1){\text{ ausklammern}}\right.}\\[0.5em]&={\frac {(k+1)\cdot (k+2)}{2}}\\[0.5em]&\qquad {\color {Gray}\left\downarrow \ k+2=(k+1)+1\right.}\\[0.5em]&=\underbrace {\frac {(k+1)\cdot ((k+1)+1)}{2}} _{\text{rechte Seite der Zielgleichung}}\\\end{aligned}}$

Unter Annahme der gegebenen Gleichung können wir also die linke Seite der Zielgleichung in die rechte Seite der Zielgleichung umformen. Damit haben wir die Zielgleichung bewiesen.

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

Erklärung des Prinzip der vollständigen Induktion anhand eines Beispiels. (YouTube-Video vom Kanal Quatematik)

Bild zur Veranschaulichung des Dominoeffekts bei der vollständigen Induktion

Doch was ist nun das Prinzip der vollständigen Induktion? Dazu schauen wir uns die obige Beispielaufgabe an und versuchen, das dabei verwendete Beweisprinzip zu verallgemeinern.

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

Nun haben wir im ersten Schritt bewiesen, dass die Aussageform für die kleinste natürliche Zahl erfüllt ist (in unserem obigen Beispiel war diese kleinste natürliche Zahl die Eins; in bestimmten Fällen kann es aber auch eine andere natürliche Zahl 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$ erfüllt ist, sie auch für $k+1$ erfüllt sein muss. Dieser Schritt wird Induktionsschritt genannt und entspricht in unserer obigen Analogie der Tatsache, dass die Dominoreihe so aufgebaut sein muss, dass beim Fall eines Dominosteins auch der nächste Dominostein umfallen muss. Die dabei getroffene Annahme, dass die Aussageform für ein beliebiges $k$ erfüllt ist, nennt man Induktionsvoraussetzung oder auch Induktionsannahme (das war die gegebene Gleichung im zweiten Lösungsschritt). Die unter Annahme der Induktionsvoraussetzung zu beweisende Aussage $A(k+1)$ wird Induktionsbehauptung genannt (das war unsere obige Zielgleichung). Der Induktionsschritt hat also die Form:

$\overbrace {\underbrace {A(k)} _{\begin{smallmatrix}{\text{Induktionsvoraussetzung}}/\\{\text{Induktionsannahme}}\end{smallmatrix}}\implies \underbrace {A(k+1)} _{\text{Induktionsbehauptung}}} ^{\text{Induktionsschluss}}$

Im Folgenden werden wir nur noch den Begriff „Induktionsvoraussetzung“ verwenden. 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:
   • Induktionsvoraussetzung: Die Aussage $A(k)$ ist wahr für ein beliebiges $k\in \mathbb {N}$.
   • Induktionsbehauptung: Die Aussage $A(k+1)$ ist wahr.
   • Beweis des Induktionsschritts: Beweise, dass unter Annahme der Induktionsvoraussetzung die Induktionsbehauptung wahr ist.

Der Induktionsschritt hat dementsprechend folgende Form:

${\begin{array}{c}{\text{Induktionsvoraussetzung}}\\{\color {Gray}|}\\{\color {Gray}{\text{Beweis}}}\\{\color {Gray}\downarrow }\\{\text{Induktionsbehauptung}}\end{array}}$

Oftmals (insbesondere bei einfacheren Aufgaben) werden Induktionsvoraussetzung und Induktionsbehauptung weggelassen, wenn sie dem Autor zu trivial erscheinen, als dass sie ausführlich erwähnt werden müssten. Auch der Induktionsanfang bzw. der Induktionsschritt werden manchmal nicht ausgeführt. Oft geben Lehrbuchautoren nur den Hinweis, dass eine bestimmte Aufgabe durch vollständige Induktion bewiesen werden kann und überlassen dem Leser die Auseinandersetzung mit dem jeweiligen Beweis. In diesem Kapitel werden aber alle Teilschritte der vollständigen Induktion ausgefü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 mit der freien Variable $n\in \mathbb {N}$. Sei $A(1)$ eine wahre Aussage (Induktionsanfang) und die Implikation $A(k)\implies A(k+1)$ für alle $k\in \mathbb {N}$ erfüllt (Induktionsschritt), dann ist die Aussageform allgemeingültig in $\mathbb {N}$.

Einige Fragen zur vollständigen Induktion

Frage: Muss man zum Beweis mit vollständiger Induktion immer den Induktionsanfang und den Induktionsschritt durchführen oder kann man sich auch unter Umständen einen der beiden Schritte sparen?

Zur vollständigen Induktion gehören immer Induktionsanfang und Induktionsschritt. Wenn du einen der beiden Schritte weglassen würdest, wäre deine Lösung unvollständig und besäße damit keine Beweiskraft.

Die Antwort auf diese Frage kannst du dir auch über die Analogie zur Dominoreihe überlegen: Wenn du den Induktionsanfang weglässt, entspricht dies der Tatsache, dass du den ersten Dominostein nicht umstößt, was zur Folge hat, dass kein Dominostein umfällt.

Wenn du den Induktionsschritt weglässt, könntest du nach der Analogie nicht gewährleisten, dass ein Dominostein beim Umfallen auch seinen Nachfolger mitreißt. Damit könntest du nicht garantieren, dass alle Dominosteine umfallen (zwei Dominosteine könnten zum Beispiel zu weit voneinander entfernt stehen). Deine Lösung hätte dann keine Beweiskraft.

Frage: Da die Dominoreihe unendlich ist, benötigt sie auch unendlich lange zum Umfallen. Dies würde bedeuten, dass ein Beweis mit vollständiger Induktion nie vollständig wäre (da zu keiner Zeit alle Steine umgefallen sind). Heißt das nicht, dass man die vollständige Induktion nie zu Ende führen kann?

Diese Frage zeigt eine der Grenzen der Dominoanalogie. Die Zeit, die ein Dominostein benötigt, um umzufallen und dabei den nächsten Stein anzustoßen, ist für die Mathematik nicht relevant. Es ist nur wichtig, dass jeder Stein in endlich vielen Schritten fällt.