Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufgabe 4.1. (Induktionsbeweis - Catalan-Zahlen)
Ich habe eine Verständnisfrage zu der Teilaufgabe b):
Ist mit der Frage gemeint, dass ich zeigen soll, dass der Algorithmus in der Methode gleich der in b) angegebenenFormel ist oder soll ich ebendiese Formel beweisen.
Wenn Zweiteres: Wie soll ich denn überhaupt eine Zahlenfolge beweisen, bzw. auf was soll ich in der Induktion hinarbeiten? - Dass eine Verbindung zwischen Cn und C(n+1) besteht, reicht das? Die bisherigen Induktionen in Mathe waren ja doch anders, deswegen verwirrt mich das etwas.
Danke im Voraus!
Du sollst beweisen dass die Formel die in der Methode implementiert ist gleich der angegeben Formel ist, also
cn(n) = C_n
Okay, danke!
Kann mir jemnd helfen ich komm mit vollstaendiger induktion noch nicht wirklich gut zurecht… muss ich wenn ich des beweisen will nun die Formel die Unter b) ist mit hilfe vom Produktzeichen und indutkion umformulieren oder die formel die in der Methode steht so umformulieren das ich sie hinter ein Produktzeichen setzen kann ?
Du brauchst kein Produktzeichen.
Ein Beweis der vollständigen Induktion baut sich in drei Schritten auf:
- Induktionsanfang: Für einen beliebigen Startwert Gültigkeit beweisen
- Induktionshypothese: Annahme, dass die Behauptung für einen Wert n wahr ist
- Induktionsschritt: Gültigkeit der Behauptung für n+1 beweisen. Für diesen Beweis, darf die unter 2. angenommene Hypothese, als wahr betrachtet und ggf. in die Berechnung eingesetzt werden.
Du sollst ja zeigen, dass für jedes n >= 0 gilt: cn(n) = ((2n )!)/((n+1) !⋅n!). Da steht nirgendwo ein Produktzeichen. Also solltest du auch für deinen Beweis keines brauchen. Denn am Ende solltest du cn(n) so umformen, dass es dem Term auf der rechten Seite entspricht.
In meinen Augen repräsentiert die Rekursion ein Produktzeichen?
Würde das überhaupt mit einem Produktzeichen gehen? Was kommt denn für n=0 bei dir dann raus?
naja indutkionsanfang für 0 und 1 und produktzeichen von 1 bis k
Ok, das geht. Sieht dann vllt sogar besser aus der rekursive Aufruf. Vor allem könnte man sich bei der Variante an den ganzen Beispielen in Mathe orientieren.
Hm…
[quote=Maddoc]
Würde das überhaupt mit einem Produktzeichen gehen? Was kommt denn für n=0 bei dir dann raus?
[/quote]Das Produktzeichen ist so definiert, dass es den Wert 1 hat, wenn die obere Grenze kleiner ist als die untere, siehe auch http://de.wikipedia.org/wiki/Produkt_(Mathematik)#Das_leere_Produkt
Die Sache mit dem neutralen Element erinnert mich gerade an die Mathevorlesung. Analog ist ja auch die leere Summe 0, weil das neutrale Element der Addition 0 ist.
Muss man das mit dem Produktzeichen als Nicht-Mathe-Hörer verstehen, um die Aufgabe zu lösen?
also ich verstehe nicht wovon die sprechen und hab glaub zumindest sowas in der Art von nem Induktionsbeweis hingeklatscht.
Allerdings bin ich mir auch ned so sicher ob das so stimmt.
[quote=E.T.]
Muss man das mit dem Produktzeichen als Nicht-Mathe-Hörer verstehen, um die Aufgabe zu lösen?
[/quote]Nein, muss man nicht. Man muss nur wissen, wie die Fakultaet definiert ist. Diese Definition kann man mit dem Produktzeichen machen, welches rekursiv definiert werden kann. Also kann man genausogut die Fakultaet selbst rekursiv definieren: Es reicht zu wissen, dass 0! = 1 und n! = n*(n-1)! ist.