Weiter
Vollständige Induktion
Die vollständige Induktion ist ein höheres Beweisverfahren der Mathematik. Es dient dazu, eine Aussage A(n), die von einem Parameter n abhängt, für alle natürlichen Zahlen n∈IN zu beweisen.
Dabei wird der induktive Aufbau der natürlichen Zahlen benutzt. Diese besitzen folgende wichtigen Eigenschaften:
-
0∈IN.
- Ist n∈IN, so gilt auch n+1∈IN.
- Erfüllt eine Teilmenge M⊂IN die beiden vorherigen Eigenschaften, so gilt bereits M = IN.
Zeigt man nun, dass die Aussage A(0) erfüllt ist, und dass aus der Annahme A(n) sei erfüllt, auch die Gültigkeit von
A(n+1) folgt, so erfüllt die Menge
| M = { n∈IN | A(n) ist erfüllt } |
die beiden ersten Bedingungen, und somit muss bereits M = IN gelten. Damit wäre die Aussage A(n) für alle n∈IN bewiesen — durch vollständige Induktion.
-
Das Beweisen der Aussage A(0) nennt man die Induktionsverankerung oder den Induktionsanfang. Der "Beweis" besteht dabei in der Regel darin, dass man den Wahrheitswert der (logischen) Aussage A(0) direkt überprüft.
- Das Schließen von A(n) auf A(n+1) nennt man den Induktionsschritt oder Induktionsschluss.
- Für den Induktionsschluss nehmen wir an, dass A(n) gültig sei. Das nennen wir die Induktionsannahme.
- Man kann natürlich den Induktionsanfang für einem Startwert n0 > 0 zeigen. Dann gilt die Aussage A(n) für alle natürlichen Zahlen n≥ n0.
Weiter