Frage: Vollständige Induktion, Korrektheitsbeweis: Wie kommt man auf den Schluss n - 1 auf n?
Hallo, ich verstehe nicht ganz wieso man beim Beweis von n – 1 auf n schließt und generell erschließt mir nicht wirklich wieso der untenstehende Beweis nun aussreicht/ bzw. alles zeigt. Das hier ist eine Musterlösung. Es soll die Korrektheit vom Algorithmus Fakultät-Rekursiv(n) gezeigt werden.
Induktionsanfang für n = 0: Die Bedingung n = 0 bei Aufruf Fakultät-Rekursiv(0) wird wahr und f → 1 ausgeführt. Der Funktionsaufruf bricht ab und es gilt Fakultät-Rekursiv(0) = f = 1 = 0!
Induktionsvoraussetzung: Fakultät-Rekursiv(n) = n! für n ≥ 0
Induktionsschluss von n − 1 auf n für n > 0. Bei Aufruf Fakultät-Rekursiv(n) wird der else-Zweig ausgeführt, da n > 0 gilt. f bekommt den Wert des Ausdrucks n * Fakultät-Rekursiv(n-1) zugewiesen. Mit Hilfe der Induktionsbehauptung für n − 1 ≥ 0 folgt f = n · (n − 1)! = n!.
Erläuterung/ Eigene Überlegung:
Induktionsanfang und Terminierung ist mir klar. Induktionsvoraussetzung denke ich auch. Denn wir nehmen ja an, dass das was wir behaupten schon stimmt und schließen dann von n auf das nächst größere. Eigentlich. Hier ist auch meine Frage: Induktionsschluss von n-1 auf n.
Müsste man nicht normalerweise von n auf n + 1 schließen, da n bereits die Eingabe ist für die wir annehmen, dass die Behauptung Fakultät-Rekursiv(n) = n! für n >= 0 gilt?
Oder wählen wir absichtlich von n - 1 auf n, da wir so folgende Gültigkeit haben: n > 0 bzw. n >= 1
Da man n >= 0 hat und dies auch für n – 1 gelten muss: n - 1 >= 0
Da wir dann vom Schluss von n – 1 auf n praktisch durch Addition von 1 auf n >= 1 kommen (bzw. n > 0) ist das die richtige Erklärung warum hier in der Musterlösung steht: „von n − 1 auf n für n > 0“ ?
Die Überlegung eines Freundes warum wir nicht von n auf n + 1 wählen war Folgende:
Man hat wieder n >= 0 und das soll auch für n + 1 gelten
n + 1 >= 0 | mit – 1 muss n >= -1 gelten und -1 kann bei Fakultät-Rekursiv(n) keine gültige Eingabe sein.
Kommt das irgendwie so hin? Ich glaube das kann man nicht so erklären. Uns verwirrt wieso ausdrücklich n – 1 auf n und nicht n auf n + 1 gewählt wurde. Denn eigentlich ist doch der Sinn von vollständiger Induktion, dass man die Behauptung annimmt und für das nächst größere diese Behauptung als Voraussetzung nimmt und dadurch dann die Gültigkeit beweist.
Meine erste Vermutung war diese: n auf n + 1
Wir haben n >= 0 und schließen durch +1 auf n + 1 >= 1 was ja das gleiche ist wie n + 1 > 0
Und dann die gleiche Erklärung wie oben, „da n > 0 gilt, wird der else-Zweig durchgeführt und man kriegt den Ausdruck: n * Fakultät-Rekursiv(n-1) und ruft damit die Funktion mit um eins verringerten Wert n auf und das wiederholt sich solange bis n = 0 ist (was aufgrund der Terminierung zwangsweise eintreten muss, da n bei jedem rekursivem Aufruf um 1 reduziert wird.
Durch die Induktionsbehauptung für n + 1 >= 1 folgt: f = (n + 1) * n! = (n + 1)!
Zumindest kenne ich das aus Mathe so. Oder muss hier bei Algorithmen ausdrücklich die Behauptung die wir beweisen wollen am Ende im Induktionsschluss stehen? Das finde ich irgendwie widersprüchlich.
Mit freundlichen Grüßen
