Vollständige Induktion

Definition

Seit Richard Dedekind ist die vollständige Induktion folgendermaßen festgelegt:

Um zu beweisen, dass ein Satz für alle natürlichen Zahlen n ≥ m gilt, genügt es zu zeigen, dass er für n = m gilt und dass aus der Gültigkeit des Satzes für eine Zahl n ≥ m stets seine Gültigkeit auch für die folgende Zahl n+1 folgt.

Als formale Schlussregel mit Ableitungsoperator lautet die vollständige Induktion für eine Aussage A(n) und eine natürliche Zahl m:

----Diese Schlussregel ist eine kompakte Formulierung des Beweisschemas der vollständigen Induktion, das didaktisch etwas ausführlicher formuliert werden kann:

Soll die Formel A(n) für alle natürlichen Zahlen n ≥ m bewiesen werden, dann genügen dazu zwei Beweisschritte:

1. der Induktionsanfang: der Beweis von A(m)

2. der Induktionsschritt: der Beweis der Induktionsbehauptung A(n+1) mit Hilfe der Induktionsvoraussetzung A(n) und n ≥ m.

Im Normalfall ist m=0 oder m=1. In Sonderfällen kann jedoch m > 1 sein.----Da die Aussage A(n) für n ≥ m gleichwertig ist zur Aussage A(n+m) für n ≥ 0, lässt sich Dedekinds Induktion auf die vollständige Induktion von 0 aus zurückführen:

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Vollständige Induktion aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung