Vollständige Induktion: Warum sie mich verwirrt hat

Und warum sie trotzdem genial ist

1. Das intuitive Problem

Vollständige Induktion wirkt anfangs faul:

• Man zeigt die Aussage für $n = 1$.
• Dann zeigt man: Aus $P(n)$ folgt $P(n+1)$.
• Und daraus soll plötzlich folgen, dass $P(n)$ für alle $n \in \mathbb{N}$ gilt?

Das fühlt sich wie ein Trick an. Ist es aber nicht. Es ist eine saubere Ausnutzung der Struktur der natürlichen Zahlen.

---

2. Die Domino-Analogie (diesmal korrekt gedacht)

Stell dir eine unendliche Reihe Dominosteine vor:

Die vollständige Induktion besteht aus genau zwei Bausteinen:

1. Induktionsbasis: $P(1)$ ist wahr. → Der erste Stein fällt.
2. Induktionsschritt: Für alle $n \in \mathbb{N}$ gilt: $P(n) \Rightarrow P(n+1)$. → Wenn ein Stein fällt, fällt der nächste.

Wenn beides stimmt, ist klar:

• Stein 1 fällt ⇒ Stein 2 fällt
• Stein 2 fällt ⇒ Stein 3 fällt
• usw. ohne Lücke

Die Kettenreaktion ist der Beweis. Nicht „wir haben unendlich viele Fälle angeguckt", sondern: Wir haben gezeigt, dass keine Zahl entkommen kann, sobald es für die erste gilt.

---

3. Mein Fehler beim klassischen Beispiel

Die Aufgabe

Zeige mit vollständiger Induktion:

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

Mein falscher Ansatz

• Basisfall $n=1$: korrekt.
• Dann dachte ich: „Jetzt prüfe ich $n=2$.“

Also:

• Links: $1+2 = 3$
• Rechts: $\frac{2 \cdot 3}{2} = 3$

Beides stimmt. Und ich dachte ernsthaft: „Nice, fertig.“

Warum das Quatsch ist

Ich hatte effektiv nur das hier gemacht:

P(1): wahr
P(2): wahr
P(3), P(4), P(5), ... : keine Aussage

Zwei Punkte auf einer unendlichen Geraden sagen nichts über den Rest. Vollständige Induktion will nicht „Basis + nächster konkreter Fall", sondern:

Wenn es für ein beliebiges $n$ gilt, dann muss es für $n+1$ gelten.

Das „beliebig, aber fest gewählt" ist der Kern. Ohne diese Verallgemeinerung ist es kein Induktionsbeweis. (Mehr zu Beweistechniken findest du in unserer Mengenlehre-Lektion.)

---

4. Der korrekte Induktionsschritt

Induktionsannahme (I.A.)

Sei $n \in \mathbb{N}$ beliebig aber fest. Angenommen, es gilt:

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

Zu zeigen (I.S.)

Wenn wir in der ursprünglichen Formel überall $n$ durch $n+1$ ersetzen, müsste gelten:

$$\sum_{i=1}^{n+1} i = \frac{(n+1) \cdot ((n+1)+1)}{2} = \frac{(n+1)(n+2)}{2}.$$

Das ist unser Ziel. Wir müssen zeigen, dass die linke Seite wirklich gleich der rechten Seite ist.

Beweis des Schritts

Die zentrale Idee: Wir zerlegen die Summe so, dass wir die Induktionsannahme verwenden können.

Was bedeutet $\sum_{i=1}^{n+1} i$ ausgeschrieben?

$$\sum_{i=1}^{n+1} i = 1 + 2 + 3 + \ldots + n + (n+1)$$

Das können wir aufteilen in:

$$\underbrace{1 + 2 + 3 + \ldots + n}_{\text{Summe bis } n} + (n+1)$$

Die Summe bis $n$ kennen wir schon aus der Induktionsannahme! Also:

Schritt 1: Summe aufteilen

$$\sum_{i=1}^{n+1} i = \underbrace{\sum_{i=1}^{n} i}_{\text{das kennen wir!}} + (n+1)$$

Schritt 2: Induktionsannahme einsetzen

Wir wissen aus der I.A., dass $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$. Also:

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

Schritt 3: $(n+1)$ auf gemeinsamen Nenner bringen

$(n+1)$ ist dasselbe wie $\frac{2(n+1)}{2}$:

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

Schritt 4: Beide Brüche addieren

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

Schritt 5: $(n+1)$ ausklammern

Sowohl im ersten als auch im zweiten Term kommt $(n+1)$ vor:

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

Das war's! Wir haben genau die Form erreicht, die wir zeigen wollten.

Was haben wir gemacht?

• Wir haben die Summe bis $n+1$ geschickt aufgeteilt
• Für den Teil bis $n$ haben wir die Induktionsannahme benutzt (das ist der Trick!)
• Dann nur noch Algebra: Brüche addieren und ausklammern

Wichtig: Ohne die Induktionsannahme könnten wir nichts beweisen. Sie ist das Werkzeug, das den ganzen Beweis erst möglich macht.

Damit ist gezeigt: Aus der Gültigkeit für $n$ folgt die Gültigkeit für $n+1$. Zusammen mit der Basis folgt: Die Formel gilt für alle $n \ge 1$.

Wichtig: Wir rechnen nicht einfach stumpf $n=2$ aus, sondern beweisen eine allgemeine Implikation.

Video-Empfehlung: Wo es bei mir klick gemacht hat

Ich habe diese Aufgabe 3 Mal falsch gemacht, bis ich dieses Video gesehen habe. Hier rechnet eine YouTuberin die Aufgabe sauber durch und zeigt genau, wie man die Induktionsannahme richtig einsetzt:

---

5. Häufige Fehler (und wie man sie ausrottet)

Fehler 1: „Basis + nächster Wert“ statt echter Induktion

Falsch: $P(1)$ prüfen, $P(2)$ prüfen, fertig. Richtig: $P(1)$ prüfen und dann $P(n) \Rightarrow P(n+1)$ für beliebiges $n$ zeigen.

Fehler 2: Induktionsannahme nicht benutzt

Falsch: P$(n+1)$ „direkt“ beweisen, ohne $P(n)$ zu verwenden. Richtig: $P(n)$ ist dein Werkzeug. Wenn du es nicht benutzt, machst du keinen Induktionsbeweis.

Fehler 3: Basis ignorieren

Falsch: „Sieht doch offensichtlich aus, sparen wir uns.“ Richtig: Ohne gültigen Startstein bringt dir der schönste Induktionsschritt nichts.

---

6. Checkliste für Induktionsbeweise

1. Aussage sauber formulieren: Klar definieren, was $P(n)$ ist.

2. Induktionsbasis: Setze Startwert (z.B. $n=0$ oder $n=1$) ein und rechne ihn durch.

3. Induktionsannahme: Schreibe explizit hin: „Angenommen, $P(n)$ gilt für ein beliebiges, aber festes $n$."

4. Induktionsschritt:

• Formuliere $P(n+1)$.
• Beginne auf einer Seite von $P(n+1)$.
• Nutze gezielt die Induktionsannahme.
• Forme um, bis du die andere Seite von $P(n+1)$ hast.

5. Abschluss: „Damit gilt nach dem Prinzip der vollständigen Induktion $P(n)$ für alle $n \ge$ Startwert."

Wenn einer dieser Teile fehlt oder die Induktionsannahme nicht auftaucht: Beweis wegwerfen.

---

7. Warum das kein mathematischer Scam ist

Induktion umgeht das „unendlich viele Fälle“-Problem nicht durch Weggucken, sondern durch ein besseres Ziel:

Wir beweisen keine Liste von Einzelaussagen, sondern eine Regel:

Diese Regel garantiert: Wenn der erste Fall stimmt, stimmt zwangsläufig jeder Nachfolger.

Das funktioniert, weil die natürlichen Zahlen so aufgebaut sind:

• Es gibt ein erstes Element ($0$ oder $1$).
• Zu jeder Zahl gibt es genau einen Nachfolger.
• Jede $n >$ Startwert entsteht durch endliches Wiederholen des Nachfolger-Schritts.

Genau diese Struktur macht vollständige Induktion nicht nur zulässig, sondern fast unvermeidlich, wenn man sauber über $\mathbb{N}$ argumentiert.

---

8. Fazit

• Ich habe am Anfang nicht Induktion gemacht, sondern zwei Beispiele geprüft.
• Der entscheidende Switch war:
  • weg von „ich rechne noch ein Beispiel",
  • hin zu „ich beweise einen Mechanismus $P(n) \Rightarrow P(n+1)$".
• Die Induktionsannahme ist kein Trick, sondern das Werkzeug.
• Seitdem vergesse ich die Induktionsannahme nicht mehr.

Wenn du denselben Fehler gemacht hast: gut. Jetzt hast du eine Chance, das Konzept wirklich zu verstehen – und nicht nur stumpf ein Schema abzuschreiben.

---

Weiterlernen

Verwandte Lektionen

Wenn dir diese Erklärung geholfen hat, schau dir auch diese Lektionen an:

• Mengenlehre-Beweise verstehen - Weitere Beweistechniken für diskrete Mathematik
• Relationen verstehen - Äquivalenzrelationen und partielle Ordnungen
• Algebraisierung des Denkens - Wie mathematisches Denken strukturiert wird

Glossar-Einträge

• Vollständige Induktion - Formale Definition
• Beweis - Was macht einen mathematischen Beweis aus?
• Natürliche Zahlen - Die Struktur von ℕ
• Implikation - Logische Schlussfolgerungen

Community

Hast du Fragen zu vollständiger Induktion oder anderen Beweistechniken?

👉 Komm in unsere Discord-Community: discord.gg/mTPrxMwW

Dort helfen wir uns gegenseitig bei Mathe-Problemen, diskutieren Beweisstrategien und bereiten uns gemeinsam auf Klausuren vor.

---

Hat dir diese Lektion geholfen? Teile sie mit anderen, die auch mit Induktion kämpfen - manchmal hilft es, zu wissen, dass man nicht alleine ist. 🎓