Vollständige Induktion einfach erklärt

Stell dir eine Reihe von Dominosteinen vor. Damit alle Steine ab dem ersten fallen, brauchst du zwei Sicherheiten: Der erste Stein fällt. Jeder fallende Stein stößt den nächsten um. Beim Induktionsbeweis übernimmt der Induktionsanfang die erste Aufgabe. Der Induktionsschritt sorgt für die Weitergabe von einem Fall zum nächsten. Der Schritt allein liefert noch keinen wahren Fall, von dem aus die Weitergabe starten kann. Der Anfang allein prüft nur einen einzigen Fall. Erst beide Teile zusammen bilden die lückenlose Kette A(n_0)\Rightarrow A(n_0+1)\Rightarrow A(n_0+2)\Rightarrow\dots Das Prüfen vieler Werte ist dagegen kein Beweis. Auch wenn eine Formel für die ersten 5000 Zahlen stimmt, könnte sie beim nächsten Wert scheitern.

Bevor du rechnest, notierst du die Aussage A(n) und ihren Geltungsbereich. Danach gehst du in einer festen Reihenfolge vor. 1. Induktionsanfang: Setze den kleinsten behaupteten Wert n_0 ein und prüfe beide Seiten der Aussage. Ein Satz wie „für n=1 stimmt es“ reicht nicht, wenn die Rechnung nicht sichtbar ist. 2. Induktionsvoraussetzung: Wähle ein beliebiges, aber festes n\ge n_0 und nimm A(n) an. Du behauptest damit nicht, A(n) schon für alle Zahlen bewiesen zu haben. Du untersuchst: Was folgt, wenn dieser eine beliebige Fall gilt? 3. Induktionsbehauptung: Schreibe A(n+1) vollständig hin. Ersetze dazu in der ursprünglichen Aussage jedes passende n durch n+1. So steht dein Rechenziel fest. 4. Induktionsschluss: Beginne mit der Seite von A(n+1), in der der bekannte Fall A(n) steckt. Bei einer Summe trennst du meist den neuen Summanden ab: S_{n+1}=S_n+a_{n+1} Ersetze dann S_n mit der Induktionsvoraussetzung und forme bis zur Zielseite von A(n+1) um. 5. Schlusssatz: Halte fest, dass Anfang und Schritt erbracht sind. Nenne dabei den Geltungsbereich, zum Beispiel: „Damit gilt die Aussage nach dem Prinzip der vollständigen Induktion für alle n\ge1."

Wir beweisen für alle n\ge1 die Gaußsche Summenformel 1+2+\dots+n=\frac{n(n+1)}{2} Der entscheidende Gedanke steckt in der ersten Umformung: In der längeren Summe wird die bekannte Summe bis n sichtbar. Erst dann darfst du die Induktionsvoraussetzung einsetzen. Nach demselben Muster beweist du die Summe der ungeraden Zahlen. Der n-te ungerade Summand ist 2n-1, für den Nachfolger kommt also 2(n+1)-1=2n+1 hinzu. Geometrisch heißt das: Ein Quadrat aus n^2 Punkten wird durch einen L-förmigen Rand aus 2n+1 Punkten zum Quadrat mit (n+1)^2 Punkten.

Ein formal aussehender Beweis kann trotzdem eine Lücke enthalten. Prüfe deshalb nicht nur die Rechnungen, sondern auch Startwert, Geltungsbereich und logischen Anschluss. Typische Fehler: Falscher Startwert: Soll eine Aussage erst ab n=4 gelten, musst du bei 4 beginnen. Ein Anfang bei 1 hilft nicht, wenn die Aussage dort falsch ist. Nicht verwendete Voraussetzung: Aus dem bloßen Hinschreiben von A(n+1) folgt nichts. Im Schluss muss A(n) tatsächlich eingesetzt oder genutzt werden. Ziel schon vorausgesetzt: Du darfst nicht mit „Nach Voraussetzung gilt A(n+1)“ beginnen. Genau das sollst du erst beweisen. Lücke direkt nach dem Anfang: Der allgemeine Schritt muss schon für den Übergang von n_0 zu n_0+1 funktionieren. Verlorene Bedingung: Bei Ungleichungen musst du etwa prüfen, ob ein Faktor nicht negativ ist, bevor du mit ihm multiplizierst. Vertiefung: Starke Induktion: Manchmal hängt ein neuer Fall von mehreren früheren Fällen ab. Dann darfst du bei der starken Induktion für den Schritt annehmen, dass alle Aussagen von A(n_0) bis A(n) gelten, und daraus A(n+1) beweisen. Ein Beispiel sind rekursive Folgen mit zwei Vorgängern. Wenn der neue Wert aus den beiden vorherigen Werten entsteht, brauchst du meist zwei Anfangsfälle. Die stärkere Voraussetzung ersetzt diese Anfangsfälle nicht; sie erweitert nur das Wissen, das du im Schritt benutzen darfst.