Wie macht man einen detaillierten Induktionsbeweis?

Question

Hi, ich bin beim Üben auf folgende Aufgabe gestoßen:Gegeben sei die Funktion a(n)= 2 * a(n - 1) - a(n - 2) + 8 für n ≥0Jetzt soll man beweisen, dass die Funktion für  ∀n ≥ 0 gilt, also einen Induktionsbeweis durchführen.Ferner soll dies möglichst detalliert gemacht werden und man soll alle Voraussetzungen und Zwischenschritte explizit aufschreiben.Kann mir das vielleicht jemand beispielhaft an dieser Aufgabe machen?

Comments

Zuerst sollte man sich sauber aufschreiben was zu zeigen ist, dass hast du uns übrigens bisher verheimlicht.

---

Oh stimmt, sorry. Hierbei soll die Voraussetzung ∀n ≥ 0 : a(n) ≡ (2·n + 1)² sein*

---

Du kannst aber gar nicht zeigen, dass die rekursive Definition der Funktion für alle \(n\geq0\) gilt sondern nur für alle \(n \geq2\), da \(a(-1)\) und \(a(-2)\) gar nicht definiert sind. Außerdem muss in der Aufgabenstellung bei der rekursiven Definition \(a(1) = 9\) und \(a(0)=1\) vorgegeben sein.

---

Oh sorry, dass habe ich übersehen. Du hast recht, dass ist auch vorgegeben

---

@ Yakyu:

Mit " Voraussetzung ∀n ≥ 0 : a(n) ≡ (2·n + 1)² "  sind a(1) = 9 und a(0) = 1 eigentlich vorgegeben.

Mit n≥2  hast du natürlich recht.

---

@Wolfgang: Ja (falls die rekursive Definition zu zeigen ist) habe aber weiterhin Zweifel daran, dass der Fragesteller die Aufgabe richtig wiedergibt (eventuell ist ja die sogenannte "Voraussetzung" eigentlich zu beweisen). Um die rekursive Definition zu zeigen benötigt man nämlich überhaupt keine Induktion, sondern kann es einfach nachrechnen.

---

Wäre nicht das erste Mal, das etwas sinnloserweise mit vollständiger Induktion gezeigt werden soll, was man einfach nachrechnen kann :- )

Aber du hast recht: Die Originalaufgabe wäre hilfreich!

---

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)² 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)² . 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.

---

Mein Fehler, ihr hattet recht. Man soll die Voraussetzung beweisen. Kann mir vielleicht jemand dabei helfen? Ich müsste das bis morgen können und habe immer noch keinen Plan.

Answer 1

Voraussetzung  ∀n ≥ 0 : a(n) ≡ (2·n + 1)²  

→   a(n+1) = (2•(n+1)+1)²  =  (2n+3)²  =  4n² + 12n + 9

Behauptung:  a(n+1) = 2 ·a((n+1) - 1)  - a((n+1) - 2) + 8 

⇔  a(n+1)  = 2 a(n) - a(n-1) + 8   

⇔  a(n+1)  =  2 · (2·n + 1)²   - [2•(n-1) +1]²  + 8  =  4n² + 12n + 9

> a(n+1)=a((n+1)-1) - a((n+1)-2)+8  (aus deinem Kommentar!)

Wenn du nicht ständig etwas anderes "behaupten" würdest, hätte es direkt gestimmt!

[ Mit "vollständiger Induktion" hat der Nachweis natürlich nichts zu tun ]

Gruß Wolfgang

Comments

Doch es passt schon, der Faktor 2 steht vor dem ersten Term auf der rechten Seite.

---

????????????????

---

a(n+1) = 2a(n)-a(n-1)+8

---

@Yakyu: Danke, habs korrigiert.

> a(n+1)= a((n+1)-1) - a((n+1)-2)+8  (aus Kommentar zur Originalaufgabe!) 

---

Sorry, ich habe wahrscheinlich die Aufgabe nicht richtig verstanden.