Ich kann euch auch gerne die Orginalaufgabe geben, sie stammt aber allerdings aus dem Bereich der Informatik.
(Erklärung kommt nach den Anführungszeichen)
"Gegeben sei folgende Methode a(n) für n ≥ 0: long a(long n) { if (n == 0) { return 1; } else if (n == 1) { return 9; } else { return 2 * a(n - 1) - a(n - 2) + 8; } }
a) Beweisen Sie formal zunächst die partielle Korrektheit der Methode a(n) hinsichtlich: ∀n ≥ 0 : a(n) ≡ (2·n + 1)
2 Sie dürfen bei Ihrem Beweis vereinfachend annehmen, dass die benutzten Datentypen unbeschränkt sind und daher keine Überläufe auftreten. Geben Sie Ihren Beweis möglichst detailliert an und führen Sie alle Voraussetzungen und Zwischenschritte explizit auf.
b) Ergänzen Sie nun Ihren Beweis um eine geeignete Terminierungsfunktion für a(n),um auch die totale Korrektheit zu zeigen. Begründen Sie Ihre Wahl! " ---------
Mit partieller Korrektheit soll, laut Buch, die Induktion gemeint sein. Das wichtige (und mathematische) bei dieser Aufgabe ist lediglich, dass die Funktion " a(n - 1) - a(n - 2) + 8", die bei n>=2 durchlaufen wird und die Voraussetzung ∀n ≥ 0 : a(n) ≡ (2·n + 1)
2 . Man muss also wahrscheinlich beweisen, dass a(n+1)=a((n+1)-1) - a((n+1)-2)+8 gilt. Daher würde ich gerne wissen, wie das ausszusehen hat.