Vollständige Induktion — die Treppe der Wahrheit
Induktion beweist Aussagen der Form "Für alle n ≥ n₀ gilt A(n)". Stell dir eine unendliche Treppe vor: Wenn du die erste Stufe erreichst (Induktionsanfang) und von jeder Stufe auf die nächste kommst (Induktionsschritt), erreichst du jede Stufe.
Drei Schritte:
- Induktionsanfang (IA): Zeige A(n₀) — meistens A(1) oder A(0).
- Induktionsannahme (IV): Nimm an, A(n) gilt für ein beliebiges festes n ≥ n₀.
- Induktionsschritt (IS): Zeige unter Verwendung der IV, dass A(n+1) gilt.
Beispiel — Gauss-Summe
Behauptung: 1 + 2 + 3 + ... + n = n(n+1)/2 für alle n ≥ 1.
| Schritt | Argument |
|---|---|
| IA (n=1) | 1 = 1·2/2 = 1 ✓ |
| IV | 1 + 2 + ... + n = n(n+1)/2 |
| IS | 1 + 2 + ... + n + (n+1) = n(n+1)/2 + (n+1) = (n+1)(n+2)/2 ✓ |
EselsbrückeIA & IS — "Erste Stufe + jede weitere ist erreichbar". Vergiss niemals den Induktionsanfang. Ohne ihn beweist du gar nichts.
Wann Induktion?
- Aussagen über alle natürlichen Zahlen ab einem n₀.
- Summen-/Produktformeln (z. B. ∑k = n(n+1)/2).
- Teilbarkeitsaussagen (z. B. n³ - n teilbar durch 6).
- Ungleichungen wie 2ⁿ > n² für n ≥ 5.