Vollständige Induktion
Beweisart
Basiswissen
Die vollständige Induktion ist ein Beweisverfahren für Ausdrücke mit natürlichen Zahlen. Das Verfahren ist hier an einem Beispiel Schritt-für-Schritt erklärt.
Wozu ist das Verfahren gut?
- Mit ihm beweist man Sätze, die für natürliche Zahlen formuliert sind.
- Meistens werden die natürlichen Zahlen mit einem kleinen n geschrieben.
- Beispiel Gaußsche Summenformel: 1+2+3+...n = n(n+1):2
- Mehr dazu unter Gaußsche Summenformel ↗
- Das Verfahren hat 4 Schritte:
1. Induktionsanfang
- Die Wahrheit der Aussage wird für ein konkretes n gezeigt.
- Den Wert in die Aussage einsetzen und zeigen, dass sie "aufgeht".
- Oft nimmt man als konkretes n die Zahl 1.
- Beispiel: n=4 gibt: 1+2+3+4=4(4+1):2
- Ausrechnen: 10 = 10, also wahr.
2. Induktionsannahme
- Man schreibt die Aussage mit n noch einmal hin:
- Beispiel: 1+2+3+...n = n(n+1):2
3. Induktionsbehauptung
- Man formuliert die Aussage für n+1
- Beispiel: 1+2+3+...+n+(n+1) = (n+1)(n+1+1):2
4. Beweis, dass aus der Annahme die Behauptung folgt
- In diesem Schritt müssen die Terme aus Schritt 2 und 3 verbunden werden.
- Man kann in der Behaupt auf der linken Seite das 1+2+3..+n ...
- ersetzen durch die rechte Seite von der Induktionsannahme.
- Das ist als Verbindung ausreichend. Dann vereinfacht man ...
- beide Seiten und zeigt, dass sie gleichwertig sind.
- Beispiel: n(n+1):2 + (n+1) = (n+1)(n+1+1):2
- Vereinfachen: 0,5n²+1,5n+1 = 0,5n²+1,5n+1
- Damit ist der ganze Satz für alle n bewiesen.
Was sind typische Sätze zum Beweisen?
- Summe S der n ersten natürlichen Zahlen = n(n+1):2
- Summe der n ersten Quadratzahlen = n(n+1)(2n+1):6
- Summe der n ersten Kubikzahlen = [n(n+1):2]^2
- Summe der n ersten Potenzen von q =[1-q^(n+1)]/[1-q]
- Mehr unter Summenformeln ↗