vollständige Induktion

Die vollständige Induktion ist eine mathematische Beweismethode, nach der eine Aussage für alle natürlichen Zahlen bewiesen wird, die größer oder gleich einem bestimmten Startwert sind. Da es sich um unendlich viele Zahlen handelt, kann eine Herleitung nicht für jede Zahl einzeln erbracht werden. Sie ist ein deduktives Verfahren. Der Beweis, dass die Aussage für alle ( meist 1 oder 0) gilt,wird daher in zwei Etappen durchgeführt: 1. * Im Induktionsanfang wird die Aussage für eine kleinste Zahl hergeleitet. 2. * Im Induktionsschritt wird für ein beliebiges die Aussage aus der Aussage hergeleitet. Oder weniger „mathematisch“ formuliert: 1. * Induktionsanfang: Es wird bewiesen, dass die Aussage für die kleinste Zahl, den Startwert, gilt. 2. * Induktionsschritt: Folgendes wird bewiesen: Gilt die Aussage für eine beliebige Zahl, so gilt sie auch für die Zahl eins größer. Ausgehend vom Beweis für den Startwert erledigt der Induktionsschritt den Beweis für alle natürlichen Zahlen oberhalb des Startwertes. Dieses Beweisverfahren ist von grundlegender Bedeutung für die Arithmetik und Mengenlehre und damit für alle Gebiete der Mathematik.