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 BeispielaufgabeBearbeiten

 
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[1] konnte der kleine Gauß die Summe der ersten   natürlichen Zahlen sofort und ohne längeres Rechnen angeben.

Seine Idee war dabei, dass es zwischen   genau   Paare von Zahlen gibt, deren Summe   ist:  ,  ,   und so weiter bis  . Wenn man seinen „Trick“ verallgemeinert, kommt man auf folgende Formel:

Für jede natürliche Zahl   ist die Summe   gleich  .

Gut. Wir könnten nun anfangen, diese Behauptung für einzelne natürliche Zahlen   zu beweisen:

Für  :

 , stimmt ✔

Für  :

 , 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  ). 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   die Zahl   einsetzt, entsteht die (wahre) Aussage:

Die Summe   ist gleich  .

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   bezeichnet.   heißt so viel wie: Eine Aussageform mit dem Namen   und der freien Variablen  , also   in Abhängigkeit von  . Die obige Aussage wäre demnach  . Hier einige weitere Beispiele:

  lautet: Die Summe   ist gleich  .

  lautet: Die Summe   ist gleich  .

Unsere Aufgabe ist es, zu beweisen, dass die Aussageform bei Einsetzung aller natürlichen Zahlen   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  “.

 
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   ein. Wir sagen, dass der erste Dominostein für die Aussage   steht, der zweite Dominostein für die Aussage   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   umfällt, ist die Aussage   wahr und beim Fall von Dominostein Nummer   ist die Aussage   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   erfüllt ist.
  2. Zweiter Lösungsschritt: Zeige, dass unter der Annahme, dass die Aussageform für ein beliebiges   erfüllt ist, die Aussageform auch für den Nachfolger   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   wahr ist. Wenn wir nun dieses Wissen auf den zweiten Lösungsschritt anwenden (wenn also   ist), folgt, dass die Behauptung auch für   wahr sein muss. Wenn wir nochmal den zweiten Lösungsschritt anwenden, folgt die Wahrheit für   und bei nochmaliger Anwendung für   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   lautet die zu beweisende Aussage  . Durch Nachrechnen der rechten Seite, zeigt man, dass diese Aussage wahr ist.

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

 

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

 

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

Das Prinzip der vollständigen Induktion Bearbeiten

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   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   erfüllt ist, sie auch für   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   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   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   anwenden, deren eine freie Variable   eine natürliche Zahl ist. Zum Beweis durch vollständige Induktion musst du folgendes leisten:

  1. Induktionsanfang: Beweise, dass   eine wahre Aussage ist.
  2. Induktionsschritt: Beweise, dass wenn   wahr ist, auch   wahr sein muss. Dabei können folgende Teilschritte identifiziert werden:
    • Induktionsvoraussetzung: Die Aussage   ist wahr für ein beliebiges  .
    • Induktionsbehauptung: Die Aussage   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.

Definition (Vollständige Induktion)

Sei   eine Aussageform in der freien Variablen  . Sei   eine wahre Aussage (Induktionsanfang) und die Implikation   für alle   erfüllt (Induktionsschritt), dann ist die Aussageform allgemeingültig in  .

Einige Fragen zur vollständigen InduktionBearbeiten

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.