Vollständige Induktion — Prinzip, Schritte & Beispiele

Die vollständige Induktion ist eine Beweismethode, mit der man zeigt, dass eine Aussage ab einem bestimmten Startwert für jede ganze Zahl wahr ist. Um eine Behauptung für alle $n \ge n_0$ zu beweisen, zeigt man zuerst, dass der erste Fall stimmt, und dann, dass die Wahrheit bei einer Zahl die Wahrheit bei der nächsten Zahl nach sich zieht.

Wenn beide Teile korrekt sind, gilt die Aussage für jede ganze Zahl im angegebenen Bereich. Das ist die ganze Idee.

So funktioniert die vollständige Induktion

Schreibe die Behauptung als $P(n)$. Dann hat die Induktion diese Struktur:

1. Beweise den Induktionsanfang: Zeige, dass $P(n_0)$ wahr ist.
2. Beweise den Induktionsschritt: Zeige, dass für eine beliebige ganze Zahl $k \ge n_0$ aus der Wahrheit von $P(k)$ auch die Wahrheit von $P(k+1)$ folgt.

Sobald das erledigt ist, kannst du schließen, dass $P(n)$ für jede ganze Zahl $n \ge n_0$ wahr ist.

Die Logik ist schrittweise. Der Induktionsanfang setzt die Kette in Gang, und der Induktionsschritt hält sie von einer ganzen Zahl zur nächsten am Laufen.

Warum Induktionsanfang und Induktionsschritt beide wichtig sind

Der Induktionsanfang liefert dir die erste wahre Aussage. Der Induktionsschritt sagt, dass die Wahrheit von einer ganzen Zahl auf die nächste übergeht.

Wenn also $P(n_0)$ wahr ist, dann ist auch $P(n_0 + 1)$ wahr. Dann ist auch $P(n_0 + 2)$ wahr und so weiter. Bei der Induktion darf weder der Startpunkt fehlen noch die Verbindung von einem Fall zum nächsten.

Durchgerechnetes Beispiel: Eine Summenformel mit Induktion beweisen

Ein Standardbeispiel ist die Formel

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

für alle ganzen Zahlen $n \ge 1$.

Sei

$$P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

Induktionsanfang

Setze $n = 1$. Die linke Seite ist $1$, und die rechte Seite ist

$$\frac{1(1+1)}{2} = 1$$

Also ist $P(1)$ wahr.

Induktionsschritt

Nimm an, dass $P(k)$ für eine beliebige ganze Zahl $k \ge 1$ wahr ist. Das bedeutet

$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

Nun beweise $P(k+1)$. Beginne mit der linken Seite für $k+1$:

$$1 + 2 + 3 + \cdots + k + (k+1)$$

Mit der Induktionsvoraussetzung erhält man

$$\frac{k(k+1)}{2} + (k+1)$$

Klammere $(k+1)$ aus:

$$(k+1)\left(\frac{k}{2} + 1\right)$$

Dann vereinfache:

$$(k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}$$

Das ist genau die Formel mit $n = k+1$. Also ist $P(k+1)$ wahr.

Da sowohl der Induktionsanfang als auch der Induktionsschritt bewiesen sind, gilt die Formel für alle ganzen Zahlen $n \ge 1$.

Wann man vollständige Induktion verwendet

Induktion ist nützlich, wenn eine Aussage von einem ganzzahligen Parameter abhängt und jeder Fall sich natürlich mit einem früheren verbindet. Das kommt oft bei Summen, Teilbarkeitsaussagen, Ungleichungen, Rekursionsgleichungen und Beweisen zu Algorithmen vor.

Bestimme zuerst den richtigen Startwert. Manche Aussagen beginnen bei $n = 0$, manche bei $n = 1$, und manche ergeben erst für größere ganze Zahlen Sinn.

Prüfe dann, was der nächste gültige Fall ist. Meist geht der Schritt von $k$ zu $k+1$, aber wenn sich die Aussage nur auf gerade Zahlen bezieht, kann ein Schritt von $k$ zu $k+2$ die richtige Variante sein.

Häufige Fehler bei Induktionsbeweisen

Nur den Induktionsanfang beweisen

Der Induktionsanfang überprüft nur den ersten Wert. Für sich allein beweist er die Aussage nicht für spätere ganze Zahlen.

Den falschen Startwert verwenden

Wenn die Behauptung für alle $n \ge 2$ gelten soll, hilft es nicht, nur $P(1)$ zu beweisen. Der Induktionsanfang muss zum tatsächlichen Bereich der Aussage passen.

Mit der Induktionsvoraussetzung ungenau umgehen

Im Induktionsschritt nimmst du $P(k)$ für eine beliebige ganze Zahl $k$ im gültigen Bereich an. Du nimmst nicht an, dass der ganze Satz bereits bewiesen ist.

Den falschen nächsten Fall beweisen

Wenn dein Satz einen Schritt $k \to k+1$ braucht, reicht es nicht, einen anderen Schritt zu beweisen, es sei denn, du erklärst, warum dieser andere Schritt ausreicht.

Eine nützliche Erweiterung: starke Induktion

Manchmal braucht man zum Beweis von $P(k+1)$ mehr als nur $P(k)$. In dieser Situation erlaubt dir die starke Induktion, alle früheren Fälle bis $k$ anzunehmen und dann den nächsten zu beweisen.

Die Idee ist eng verwandt, aber die Annahme ist stärker. Das ist zum Beispiel nützlich, wenn ein Beweis davon abhängt, eine Zahl in kleinere Teile zu zerlegen.

Probiere deine eigene Version

Nimm die Behauptung

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

und beweise sie für alle ganzen Zahlen $n \ge 1$ mit derselben Struktur: zuerst der Induktionsanfang, dann der Schritt von $k$ zu $k+1$. Wenn du diesen Beweis sauber aufschreiben kannst, macht die Methode meist wirklich Klick.