Fibonacci-Zahlen. Beweis von Fn+22 = Fn2 + Fn+12 durch doppeltes Abzählen

Question

Aufgabe:

Sei n ∈ N. Beweisen Sie durch doppeltes Abzählen:

$$F_{n+2}^{2}=F_{n}^{2}+F_{n+1}^{2}$$

Hinweis:
Fibonacci-Folge, Fallunterscheidung

Machen Sie eine Fallunterscheidung, je nach dem welcher Wagentyp in der Mitte steht. 

Zu den Wagentypen:

Wir betrachten folgendes Problem: Gegeben sind Eisenbahnwagen der Länge 1 und 2. Aus diesen lassen sich Züge zusammenstellen, beispielsweise folgender Zug der Länge 5, mit 3 Wagen der Länge 1 und einem Wagen der Länge 2; die Lokomotive wird dabei nicht mitgezählt.

Dazu gab es noch die Fragestellung (Leider ohne Lösung sollte aber auch nicht so schlimm sein aber eventuell hilft es ja):

Wie viele Möglichkeiten Fn gibt es, einen Zug der Länge n aus Wagen der
Längen 1 und 2 zusammenzustellen?

Comments

Definition für Fibonacci-Folge, welche als Hilfe dienen soll:

Die Folge (F_n) wird als Fibonacci-Folge bezeichnet. Sie ist durch die Rekursion:

F₀ = 1

F₁ = 1

F_n+1 = F_n + F_n-1

definiert.

Machen Sie eine Fallunterscheidung, je nach dem welcher Wagentyp in der Mitte steht.

---

Kannst du noch erklären, was (bei euch) Wagentypen mit Fibonnacci-Zahlen zu tun haben?

Bekannte Vergleiche: https://de.wikipedia.org/wiki/Fibonacci-Folge

---

Zu den Wagentypen:

Wir betrachten folgendes Problem: Gegeben sind Eisenbahnwagen der Länge 1 und 2. Aus diesen lassen sich Züge zusammenstellen, beispielsweise folgender Zug der Länge 5, mit 3 Wagen der Länge 1 und einem Wagen der Länge 2; die Lokomotive wird dabei nicht mitgezählt.

Dazu gab es noch die Fragestellung (Leider ohne Lösung sollte aber auch nicht so schlimm sein aber eventuell hilft es ja):

Wie viele Möglichkeiten F_n gibt es, einen Zug der Länge n aus Wagen der
Längen 1 und 2 zusammenzustellen?

---

Siehe
https://mathepedia.de/Fibonacci-Zahlen.html

Du fängst nur anders an. Hier ist $F_0 = 0$

---

Ich befürchte, Du hast bei dem links vom Gleichheitszeichen die hoch- und tiefgestellten Zeichen nicht richtig. Bitte korrigieren.

---

genauso steht es in der Aufgabe. Alle n sin druntergestellt und 2 ist hochgestellt

---

Dann stell das 2 halt hoch (links vom Gleichheitszeichen).

---

Jemand anders hat es jetzt für Dich korrigiert. Was mich zur Bemerkung veranlasst, wie kann man Dir mit einer Antwort helfen, wenn Dir nicht klar ist was für eine Frage Du stellen willst.

---

@sandwurm & döschwo: Diese Frage war als Duplikat von der hier zum Verschmelzen angemeldet.

Die Rekursionsformel ist sicher gleich geblieben. Vor 6 Tagen gab es da aber noch eine Indexverschiebung um 1.

---

@ Lu
Wenn du glaubst, die von dir so völlig verhunzte Fragestellung beantworten zu können, dann versuch es ruhig. Aber lass dir von vornherein gesagt sein, dass du kaum gegen binomische Formeln ankommen wirst.

Answer 1

Vielleicht wir ja diese Antwort von den strengen Moderatoren akzeptiert.

Zeige zuerst $$F_{n+m+1} = F_{m-1}F_n + F_m F_{n+1}$$ durch Induktion über $n$.

Anschliessend setzt Du $m = n+1$ dann folgt

$$F_{2n+2} = F_n^2 + F_{n+1}^2$$

Der Induktionsanfang für $n= 0$ sollte klar sein, da $F_0 = F_1 = 1$ gilt. Und damit ist der Induktionsanfang lediglich die Definition der Fibonnacci Folge.

Der Induktionsschritt ist wie folgt

$$F_{m-1}F_{n+1}+F_m F_{n+2} = F_{m-1}F_n + F_{m-1}F_{n-1} + F_m F_ {n+1}+F_m F_n = F_{n+m+1} + F_{n+m} = F_{n+m+2}$$

Comments

Zu den Wagentypen:

Wir betrachten folgendes Problem: Gegeben sind Eisenbahnwagen der Länge 1 und 2. Aus diesen lassen sich Züge zusammenstellen, beispielsweise folgender Zug der Länge 5, mit 3 Wagen der Länge 1 und einem Wagen der Länge 2; die Lokomotive wird dabei nicht mitgezählt.

Dazu gab es noch die Fragestellung (Leider ohne Lösung sollte aber auch nicht so schlimm sein aber eventuell hilft es ja):

Wie viele Möglichkeiten Fn gibt es, einen Zug der Länge n aus Wagen der
Längen 1 und 2 zusammenzustellen?

Das ist anscheinend die Interpretation, die beim "doppelten Abzählen" benutzt werden kann / soll.

---

Was soll das. Reicht ein Beweis nicht. Muss es auch noch ein ganz bestimmter sein? Das ist doch Unsinn.

---

"durch doppeltes Abzählen:"

ist anscheinend explizit verlangt.

Da genügt ein formaler Beweis mit vollständiger Induktion leider nicht, auch wenn er sehr elegant aussieht.

---

Beweis mit vollständiger Induktion ... sehr elegant aussieht.

Demgegenüber hat der Beweis mit doppeltem Abzählen den zusätzlichen Vorteil, auch noch sehr elegant zu sein.

---

Würde mich über den Beweis mit doppeltem Abzählen freuen :)

---

Zeige zuerst
Fn+m+1=Fm−1Fn+FmFn+1
durch Induktion über n.

Auch dazu bedarf es keines Induktionsbeweises, denn jeder Zug der Länge  m + n + 1  hat genau eine der beiden folgenden Konstellationen :

---

EDIT :

Die Bildunterschriften sind falsch.

Statt  " k Wagen "  muss es jeweils heißen  " Zugabschnitt der Länge  k " .

Answer 2

etwa so funktioniert es:

Siehe auch https://www.mathelounge.de/677863/fibonacci-zahlen-beweis-von-f-2n-d…

Comments

und wie komme ich davon zu einer Fallunterscheidung? :D sorry ich verstehe gar nichts grade

---

Folge dem Link, dort steht schon alles ausführlich.

---

etwa so funktioniert es

Jetzt musst du nur noch sagen, was du mit  " es "  meinst.

---

Die Aussage bezog sich auf das, was Benutzer "Sandwurm123* andernorts gefragt hatte und jetzt hierher verschoben worden ist.

---

Unter keiner seiner Fragen ist eine, die auch nur annähernd nach einem Beweis von

Σ [k=1 bis n] (F_k)² = F_n * F_n+1   gefragt hätte.