Vollständige Induktion — Beweise für alle n

Einführung

Wie kann man beweisen, dass eine Aussage für alle natürlichen Zahlen gilt — also für 1, 2, 3, 4, … bis ins Unendliche? Man kann nicht alle Zahlen nachrechnen. Genau hier kommt die vollständige Induktion ins Spiel: eine elegante Beweismethode, die unendlich viele Fälle mit einem endlichen Argument abdeckt.

Vollständige Induktion ist ein Grundpfeiler der Mathematik und taucht in Abi-Prüfungen regelmäßig auf.

Grundidee

Stell dir eine unendliche Reihe von Dominosteinen vor, nummeriert mit 1, 2, 3, 4, …

Damit alle Steine fallen, braucht man zwei Dinge:

1. Der erste Stein fällt (Anfang)
2. Wenn Stein $n$ fällt, fällt auch Stein $n+1$ (Übertragung)

Wenn beide Bedingungen erfüllt sind, fallen zwingend alle Steine — auch wenn es unendlich viele sind. Das ist das Prinzip der vollständigen Induktion.

Erklärung

Die Beweisstruktur

Ein Induktionsbeweis hat immer drei klar benannte Teile:

IA — Induktionsanfang: Zeige, dass die Aussage für $n = n_0$ (meist $n = 1$) gilt.

IV — Induktionsvoraussetzung: Nimm an, dass die Aussage für ein beliebiges, aber festes $n \geq n_0$ gilt. (Das ist die Annahme, die du im nächsten Schritt benutzt!)

IS — Induktionsschritt: Zeige unter Verwendung der IV, dass die Aussage dann auch für $n+1$ gilt.

Beispiel 1: Summenformel

Behauptung: Für alle $n \in \mathbb{N}$ gilt:

$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$

Das bedeutet: $1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}$

Das $\square$-Symbol am Ende eines Beweises bedeutet „q.e.d.” (quod erat demonstrandum — „was zu beweisen war”).

Beispiel 2: Ungleichungsbeweis

Behauptung: Für alle $n \in \mathbb{N}$ gilt: $2^n > n$

IA ($n = 1$): $2^1 = 2 > 1$ ✓

IV: Für ein festes $n \geq 1$ gelte $2^n > n$.

IS ($n \to n+1$): Zu zeigen: $2^{n+1} > n+1$

$2^{n+1} = 2 \cdot 2^n \overset{\text{IV}}{>} 2 \cdot n = 2n \geq n + 1 \quad \text{für } n \geq 1$

Der letzte Schritt: $2n \geq n+1$ gilt für alle $n \geq 1$, denn $n \geq 1$.

Also gilt $2^{n+1} > n+1$. ✓

Damit ist die Aussage für alle $n \in \mathbb{N}$ bewiesen. $\square$

Induktion vs. Abduktion vs. Deduktion

Begriff	Bedeutung	Beispiel
Deduktion	Aus allgemeinen Regeln auf Einzelfälle schließen	Alle Menschen sind sterblich. Sokrates ist ein Mensch. → Sokrates ist sterblich.
Induktion (empirisch)	Aus vielen Einzelfällen eine allgemeine Regel ableiten	Viele beobachtete Schwäne sind weiß → „Alle Schwäne sind weiß” (bis man einen schwarzen findet!)
Vollständige Induktion	Mathematisch gesicherter Beweis für alle $n$	IA + IS → gilt für alle $n$ (kein Gegenbeispiel möglich)

Die empirische Induktion kann widerlegt werden (schwarze Schwäne!). Die vollständige Induktion ist ein deduktiver Beweis — sie ist absolut sicher, weil sie auf Logik, nicht auf Beobachtung basiert.

Beispiel aus dem Alltag

Kachelung einer Schachbrettecke: Man kann zeigen, dass jede $2^n \times 2^n$-Schachbrettfläche (mit einer entfernten Ecke) vollständig mit L-förmigen Trominos kacheln lässt. Den Beweis führt man per Induktion — für $n=1$ prüft man es direkt, und der Induktionsschritt teilt das Brett in vier kleinere.

Solche Beweise findet man überall in der Informatik: Korrektheitsnachweise für Algorithmen, Komplexitätsanalysen, Datenstrukturen.

Anwendung

Aufgabe: Beweise durch vollständige Induktion:

$\sum_{k=1}^{n} (2k-1) = n^2$

Das heißt: $1 + 3 + 5 + 7 + \ldots + (2n-1) = n^2$ — die Summe der ersten $n$ ungeraden Zahlen ist $n^2$.

Hinweis: Folge exakt dem Schema IA → IV → IS. Hebe im IS deutlich hervor, wo du die IV verwendest.

IA ($n = 1$): $\sum_{k=1}^{1}(2k-1) = 1 = 1^2$ ✓

IV: Für festes $n \geq 1$ gelte $\sum_{k=1}^{n}(2k-1) = n^2$.

IS ($n \to n+1$):

$\sum_{k=1}^{n+1}(2k-1) = \underbrace{\sum_{k=1}^{n}(2k-1)}_{\overset{\text{IV}}{=}\ n^2} + (2(n+1)-1) = n^2 + 2n + 1 = (n+1)^2 \checkmark$

Typische Fehler

„Ich vergesse, die IV im Induktionsschritt explizit zu verwenden.” Ohne die IV ist der Schritt kein Induktionsbeweis. Markiere immer, wo genau die IV eingesetzt wird.

„Der Induktionsanfang ist unwichtig.” Ohne IA scheitert alles. Beispiel: Die Aussage „Alle Zahlen sind gleich” lässt sich mit einem scheinbar korrekten IS formulieren — scheitert aber daran, dass der IA nie gilt.

„Der IS gilt automatisch, weil die Formel stimmt.” Man darf im IS nicht einfach das Ergebnis einsetzen. Die Rechnung muss von der linken Seite ausgehen und — unter Nutzung der IV — zur rechten Seite führen.

Zusammenfassung

Merke dir:

• Vollständige Induktion besteht aus drei Teilen: IA (Anfang), IV (Voraussetzung), IS (Schritt $n \to n+1$)
• Im IS muss die IV explizit genutzt werden — das ist das Herzstück
• Analogie: Dominosteine — erster Stein fällt (IA) + jeder Stein reißt nächsten mit (IS) → alle fallen
• Vollständige Induktion ist ein deduktiver Beweis, keine empirische Verallgemeinerung
• Klassische Anwendungen: Summenformeln, Ungleichungen, Teilbarkeitsaussagen

Quiz

Frage 1: Erkläre das Dominoprinzip der vollständigen Induktion in zwei Sätzen.

Frage 2: In welchem Schritt der Induktion wird die Induktionsvoraussetzung tatsächlich genutzt?

Frage 3: Warum reicht es nicht, eine Summenformel für $n = 1, 2, 3, 4, 5$ zu prüfen?

Frage 4: Formuliere Induktionsanfang und Induktionsvoraussetzung für den Beweis, dass $3^n \geq 3n$ für alle $n \geq 1$ gilt.