Beweis einer Formel zu den Fibonacci Zahlen

Question

Es geht um die Fibonacci Folge Fn, die wie folgt definiert ist:

F1 = 1, F2 = 2 für alle n > 2 : Fn+1 = Fn + Fn-1

Nun soll ein Zusammenhang mit dem goldenen Schnitt hergestellt werden. Aus dem goldenen Schnitt haben wir die quadratische Gleichung

x^2 - x - 1 = 0 dafür habe ich auch schon zwei Werte über pq- Formel ausgerechnet.

x = 1,618 und y = 0,618

Nun soll ich zeigen, dass folgende Formel für alle n aus N gilt:

Fn = x^n - y^n / x - y

EDIT: Gemeint ist Fn =( x^n - y^n )/ (x - y)


Ich habe mit Induktion angefangen, aber bin mir da noch unsicher. Muss ich für n=1 und n=2 die Formel zeigen und dann allgemein für n+1?

Weil bei n=2 ja eigentlich auch der Wert F2 =1 rauskommen muss. Das kommt bei mir aber leider nicht hin.

Vielen Dank für eine Antwort

Comments

Du meinst bestimmt

Fn =( xⁿ - yⁿ )/ (x - y)

---

Ja genau. Habe die Klammern vergessen.

Ist der Ansatz mit Induktion denn ok?

Answer 1

Sei  z = √5, sowie  x = (1 + z)/2  und  y = (1 - z)/2. Dann ist  x = 1 + 1/x  und  y = 1 + 1/y.

Behauptung: F_n = (xⁿ - yⁿ)/z.

Beweis per Induktion über n.

Induktionsanfang:
1 = F₁ = (x¹ - y¹)/z = 1
1 = F₂  = (x² - y²)/z= 1.

Induktionsschritt: Die Behauptung gelte für ein n>1.
Zu zeigen ist  F_n+1 = (xⁿ⁺¹ - yⁿ⁺¹)/z.
Nach Definition und Induktionsvoraussetzung ist
F_n+1 = F_n + F_n-1 = (xⁿ - yⁿ)/z + (x^n-1 - y^n-1)/z
        = ((xⁿ + x^n-1) - (yⁿ + y^n-1))/z
        =(xⁿ·(1 + 1/x) - yⁿ·(1 + 1/y))/z
        =(xⁿ·x - yⁿ·y)/z = (xⁿ⁺¹ - yⁿ⁺¹)/z.

Comments

ich verstehe noch nicht ganz, warum aus x-y im Nenner z wird?

Also wieso ist das denn das Gleiche? Darf ich das einfach so ersetzen?

---

Es ist  x - y = √5. Ich habe einfach  z := √5  definiert, um nicht immer  √5  schreiben zu müssen. Du kannst aber auch jedes  z  durch  √5  ersetzen.

---

Aber x - y wäre doch 1 oder nicht?

Also das wären doch 1,618-0,618 ?

---

Du hast beim  y  ein Minuszeichen vergessen.
x = (1 + √5)/2, y = (1 - √5)/2. x - y = √5.

---

Viele dank! Blöder Fehler,jetzt verstehe ich die Aufgabe!