Lösung von Beispiel

[Mr. Bringer]

Hi Leute

Rechne gerade alte Übungsbeispiele durch, kann dieses beispiel aber leider nicht lösen:



Man zeige mittels vollständiger induktion, dass für die rekursiv definierte Folge F0=0, F1=1 und Fn+2=Fn+Fn+1, n aus N (Fibonacci Folge) allgemein gilt:
\...Wurzel

Fn= 1/(\5) * [ ( (1+(\5)) / 2) - ( (1-(\5)) / 2) ]

[SS 2002 - Übungsaufgaben zur Mathematik 1 für Informatiker]
[1.Grundlagen 2) Bsp]

vielleicht kann mir jemand die Lösung zeigen....

thx im voraus:( :confused: :(

[Paulchen]

Fn= 1/(\5) * [ ( (1+(\5)) / 2) - ( (1-(\5)) / 2) ]

Das kann's ja wohl nicht sein, das würde ja bedeuten, dass alle Fn gleich sind...
Ich glaube, da fehlt auf der rechten Seite irgendwo ein n, wenn es nicht sogar mehrmals fehlt.

Ansonsten kann ich mir einen Lösungsweg vorstellen, indem du zunächst in obigen Ausdruck Fn+1 und Fn+2 einsetzt und die Ausdrücke für Fn, Fn+1 und Fn+2 in die Bedingung für die Fibonacci-Folge (Fn+2=Fn+Fn+1) einsetzt und zeigst, dass die linke und die rechte Seite gleich groß sind ´(kann ein Batzen an Rechenaufwand sein). Dies wäre im Rahmen des Beweises mit Hilfe der vollständigen Induktion der Induktionsschritt.
Für einen Induktionsstart müsstest du dann nur noch zeigen, dass der zu beweisende Ausdruck für n=0, n=1 sowie n=2 die entsprechenden Glieder der Fibonacci-Folge ergibt.

[duracell]

Fn= 1/(\5) * [ ( (1+(\5)) / 2) - ( (1-(\5)) / 2) ]das sollte wohl beispiel 40 sein.. da sieht die angabe am zettel aber etwas anders aus:

Fn = 1 / sqrt(5) [(1 + sqrt(5) / 2)^n - (1 - sqrt(5) / 2)^n]

das ein üblicher algorithmus um die fibonaccis zu berechnen.

F(0) = 1, F(1) = 1 sind gegeben. F(n+2) = F(n+1) + F(n) => F(2) = F(1) + F(0) = 1 + 1 = 2

das stimmt also sehr wohl, da die reihe so aussieht: 1, 1, 2, 3, 5, 8, 13, 21, etc..
das ist natürlich kein beweis nach der vollständigen induktion. um das zu machen, setzt du F(n+2) = F(n+1) + F(n) gleich, setzt dabei für jeden wert in den klammern (n+2), (n+1) die werte in die funktion ein.

ich hoffe, ich hab das halbwegs klar rübergebracht!?