Mit Google fortfahren
Vollständige Induktion einfach erklärt
Mit der vollständigen Induktion beweist du eine Aussage $A(n)$ für alle natürlichen Zahlen ab einem Startwert $n_0$. Du zeigst zuerst, dass die Aussage am Start gilt. Danach beweist du: Gilt sie für ein beliebiges $n$, dann gilt sie auch für $n+1$.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Warum zwei Schritte unendlich viele Fälle abdecken
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.
Vollständige Induktion
Für eine Aussage $A(n)$ und einen Startwert $n_0$ zeigst du:
- $A(n_0)$ ist wahr.
- Für jedes $n\ge n_0$ gilt $A(n)\Rightarrow A(n+1)$.
Dann gilt $A(n)$ für alle natürlichen Zahlen $n\ge n_0$.
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.
So schreibst du einen Induktionsbeweis
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$."
Die Induktionsvoraussetzung ist ein Werkzeug im Schritt. Du musst sie sichtbar verwenden; bloßes Einsetzen von $n+1$ ist noch kein Induktionsschluss.
Beispiel: Die Gaußsche Summenformel beweisen
Wir beweisen für alle $n\ge1$:
$$1+2+\dots+n=\frac{n(n+1)}{2}$$
Induktionsanfang für $n=1$:
$$1=\frac{1\cdot(1+1)}{2}=1$$
Die Aussage gilt am Start.
Induktionsvoraussetzung: Für ein beliebiges, aber festes $n\ge1$ gelte
$$1+2+\dots+n=\frac{n(n+1)}{2}.$$
Induktionsbehauptung: Zu zeigen ist
$$1+2+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2}.$$
Induktionsschluss: Wir trennen den neuen Summanden $n+1$ ab und verwenden dann die Voraussetzung:
$$1+2+\dots+n+(n+1)$$
$$=\frac{n(n+1)}{2}+(n+1)$$
$$=(n+1)\left(\frac n2+1\right)$$
$$=\frac{(n+1)(n+2)}{2}.$$
Das ist genau die Zielseite für $n+1$. Damit gilt die Summenformel nach vollständiger Induktion für alle $n\ge1$.
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.
Übung: Die Summe ungerader Zahlen
Nun beweist du für alle $n\ge1$:
$$1+3+5+\dots+(2n-1)=n^2$$
Der $n$-te ungerade Summand ist $2n-1$. Für den Nachfolger lautet der neue Summand deshalb
$$2(n+1)-1=2n+1.$$
Deine Aufgabe
Führe Anfang, Voraussetzung, Behauptung und Schluss aus. Achte besonders darauf, den neuen Summanden korrekt zu bestimmen.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Im Induktionsanfang setzt du $n=$. Im Schritt ergänzt du den neuen Summanden $$. Mit der Voraussetzung ersetzt du die alte Summe durch $$. Danach ergibt sich $n^2+2n+1=$.
Lösung
Anfang: Für $n=1$ gilt $1=1^2$.
Voraussetzung: Für ein beliebiges, aber festes $n\ge1$ gelte
$$1+3+\dots+(2n-1)=n^2.$$
Behauptung:
$$1+3+\dots+(2n-1)+\bigl(2(n+1)-1\bigr)=(n+1)^2.$$
Schluss:
$$1+3+\dots+(2n-1)+\bigl(2(n+1)-1\bigr)$$
$$=n^2+2n+1$$
$$=(n+1)^2.$$
Damit gilt die Aussage für alle $n\ge1$.
Das Muster lässt sich geometrisch deuten: Ein Quadrat aus $n^2$ Punkten wird durch einen L-förmigen Rand aus $2n+1$ Punkten zum Quadrat mit $(n+1)^2$ Punkten. Der algebraische Schritt beschreibt genau denselben Zuwachs.
Fehler erkennen und Varianten richtig wählen
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.
Bei der Behauptung „Alle Pferde einer Herde haben dieselbe Farbe“ scheint man zwei Herden mit je $n$ Pferden vergleichen zu können. Der Übergang von einer Herde mit einem Pferd zu einer Herde mit zwei Pferden scheitert aber: Die beiden betrachteten Ein-Pferd-Herden haben kein gemeinsames Pferd. Es gibt daher keine Verbindung, über die die Farbinformation weitergegeben werden könnte.
Das Beispiel zeigt: Eine versteckte Voraussetzung im Schritt muss auch unmittelbar nach dem Anfang erfüllt sein.
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.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Vollständige Induktion
- Induktionsanfang: $A(n_0)$ prüfen
- Induktionsschritt: $A(n)\Rightarrow A(n+1)$ zeigen
- Voraussetzung: $A(n)$ annehmen
- Behauptung: $A(n+1)$ notieren
- Schluss: bekannten Fall verwenden
- Geltungsbereich
- passenden Startwert wählen
- lückenlosen Anschluss prüfen
- Anwendungen
- Summen und Produkte
- Teilbarkeit und Ungleichungen
- rekursive Folgen
- Fehlerkontrolle
- Ziel nicht voraussetzen
- Bedingungen im Schritt prüfen