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

{{#invoke:Mathe für Nicht-Freaks/Seite|oben}}

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\dots 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.

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:

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

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

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

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:

Die notwendigen Termumformungen sind:

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 Vorlage:Smiley).

Das Prinzip der vollständigen Induktion Vorlage:Anker

Datei:Vollständige Induktion - Quatematik.webm

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:

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:

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.

Einige Fragen zur vollständigen Induktion

{{#invoke:Mathe für Nicht-Freaks/Seite|unten}}