Diskussion:Fibonacci-Folge

Automatische Archivierung

Auf dieser Seite werden Abschnitte monatlich automatisch archiviert, deren jüngster Beitrag mehr als 180 Tage zurückliegt und die mindestens einen signierten Beitrag enthalten. Um die Diskussionsseite nicht komplett zu leeren, verbleiben mindestens 5 Abschnitte.

Kaninchenproblem; Fibonacci-Folge

Liber abbaci, MS Biblioteca Nazionale di Firenze, Codice Magliabechiano cs cI 2616, fol. 124r: Berechnung der „Kaninchenaufgabe“ mit Fibonacci-Reihe

Ich habe ein kleines Problem mit der bisherigen Darstellung des Kaninchenproblems, dieses soll ja eigentlichdie Fibonacci-Folge darstellen, dafür müsste man aber mit einem geschlechtsunreifen Paar anfangen, da auch die Fibnacci-Folge mit [1;1;2...]anfängt es ist also 2 die ersten beiden Monate nur ein Paar vorhanden --95.112.213.74 22:45, 5. Mai 2009 (CEST)

Bei Fibonacci selbst ist (laut dem Artikel, ich habe es nicht nachgeprüft) der Index um eins verschoben, die originale Fibonacci-Folge beginnt also mit 1, 2, 3, 5, 8, … --80.129.96.156 23:34, 5. Mai 2009 (CEST)

Um das mal aufzuklären, weil ich es aus Unachtsamkeit auch schon falsch wiedergegeben habe und es in der Literatur sehr oft falsch dargestellt wird:

Der Liber abbaci liegt mir in der Ausgabe von Boncompagni vor, hier findet Ihr online eine Abschrift der Kaninchenaufgabe mit englischer Übersetzung. Jedes Paar bringt im Monat ein Paar zur Welt, das seinerseits ab dem zweiten Monat ein Paar zur Welt bringt ("cum natura eorum sit per singulum mensem aliud par germinare; et in secundo mense ab eorum natiuitate germinant"), denn die Empfängnis und der Beginn der Austragungszeit liegen im Monat vor der Geburt, wie sich aus der Aussage zum 2. und 3. Monat ergibt. Der Text läßt das erste Paar aber bereits im ersten Monat das zweite Paar werfen und fängt die Reihe deshalb genaugenommen weder mit "1, 2", noch mit "1, 1, 2", sondern mit "2, 3, 5" an:

• primo mense: paria duo
• secundo mense: paria 3
• tercio mense: paria 5
• quarto mense: paria 8
• quinto mense: paria 13

...

• undecimo mense: paria 233
• ultimo mense: paria 377

In der von Boncompagni zugrundegelegten Handschrift, aus der Heinz Lüneburg (Angaben im Artikel Leonardo Fibonacci) die beiden Seiten mit der Kaninchenaufgabe in Photographien reproduziert (er fand sie so unwichtig für Leonardo und das Gewese in der Literatur darüber so übertrieben, daß er sie im Text seines Buches nicht besprechen mochte, der Leser sollte sie sich in der Reproduktion stattdessen selbst anschauen!) findet sich auf dem rechten Rand von f. 124r (oben verlinkt) eine auch von Boncompagni nachgedruckte Zahlenkolonne, die an den Anfang zwar den Eintrug "parium" mit der Zahl 1 (also "An Paaren: 1") stellt, dann aber, wie im Text, erst im folgenden Eintrag mit der Monatszählung und der Zahl 2 für den "ersten Monat" beginnt.

Weil Lüneburg es sich dann doch nicht ganz verkneifen konnte, das verhaßte Thema wenigstens abfällig anzusprechen, schreibt er hierzu (p.197): "Er [Lüneburgs eigener Leser] wird dort [in der Photographie der Handschrift] feststellen, daß Fibonacci die nach ihm benannte Serie mit F₀ = 1 und F₁ = 2 beginnen läßt. Seine Arbeiten würden also von der Zeitschrift 'The Fibonacci Qua[r]terly' nicht zur Publikation angenommen, wie man etwa der Seite 2 des Umschlags des Maiheftres des Jahres 1991 dieser Zeitschrift entnehmen kann." --Otfried Lieberknecht 20:47, 17. Feb. 2011 (CET)

Danke für die Aufklärung! Man kann aber, wie Lüneburg, es auch so sehen, dass bei Fibonacci die Folge mit F₀ = 1 (also im nullten Monat) beginnt. Der Umschlag des Maiheftes von 1991 von "The Fibonacci Quarterly" ist hier, an dieser Vorgabe hat sich wohl auch nichts geändert. Der Index ist dann jedenfalls um zwei verschoben. --91.32.82.234 11:42, 18. Feb. 2011 (CET)

Ihr habt sicher beide recht, was Monat 0 betrifft, aber in der ausdrücklichen Formulierung get es erst mit Monat 1 los. Vielen Dank übrigens für das Link, jetzt weiß ich endlich genau, wie er das meinte. Daß jemand das noch mal eigens nachguckt und verlinkt hätte ihn als leidenschaftlichen Spaziergänger auf der Suche nach Antworten auf nebensächliche Fragen bestimmt gefreut! --Otfried Lieberknecht 13:20, 18. Feb. 2011 (CET)

weiteres Beispiel: Varroa-Milbe

bei der Vermehrung der Varroa-Milbe in der Bienenbrut geht man davon aus, daß die Mutter 3-mal verdeckelungsbereite Zellen aufsucht und über die Verdeckelungsdauer von 12 Tagen einen Sohn und zwei vermehrungsfähige Töchter liefert

die daraus sich ergebende Fibonacci-Folge ergibt sich dann zu 1 - 3 - 9 - 26 -76 - 210, also annähernd 3 exp n

die Bestätigung hierfür liefert das Zählen der nach einer durchgeführten (chemischen) Behandlung heruntergefallenen toten Milben, wo nach etwa 8 Brutperioden (entspricht 4 Monaten ungestörter Vermehrung) bis zu 10.000 Exemplare gefunden werden können

eine Grenze liegt nur in der im Bienenvolk geschätzten Gesamtzahl von ca. 60.000 Bienen und zusätzlich darin, daß in den heißen Sommermonaten die Legetätigkeit der Bienenkönigin eine Talsohle (eine Art Diapause) aufweist - trotzdem ist bei der Ende August endenden Brutzeit unentrinnbar das Todesurteil für das Bienenvolk gesprochen

-- kauhl-meersburg (nicht signierter Beitrag von Kauhl-mbg (Diskussion | Beiträge) 21:37, 21. Nov. 2009 (CET))

Mathematische Strenge und Verständnis im Abschnitt: Herleitung mittels Differenzengleichung

Aus verschiedenen Gründen kommt es gelegentlich vor, daß die ausgeführten mathematischen Gedanken noch nicht der vollen mathematischen Strenge genügen. Glücklicherweise ist es aber so, daß in vielen Fällen durch kleine Modifikationen die volle Strenge erreicht und auch das mathematische Verständnis verbessert wird. Ich möchte dies an folgender Altfassung vom 13.3. vorführen. Die ursprünglichen Überlegungen sind formal so nicht zulässig, da der Ansatz $f_{n}=x^{n}$ unzuläsig ist. Denn die Fibonacci-Folge ist offensichtlich keine geometrische Folge. Dieser Fehler findet sich leider häufig. Außerdem finden sich noch die Rudimente $\Phi$ und $\Psi$ einer abweichenden Notation.

„Eine andere Herleitungsmöglichkeit folgt aus der Theorie zu linearen Differenzengleichungen:

Angenommen, die Fibonacci-Folge kann als Potenzfunktion $f_{n}=x^{n},n\in \mathbb {N}$ dargestellt werden. Dann ergibt sich

$f_{n}-f_{n-1}-f_{n-2}=x^{n}-x^{n-1}-x^{n-2}=(x^{2}-x-1)x^{n-2}$

durch Herausheben.

Wenn also $x$ so gewählt wird, dass $x^{2}-x-1=0$ ist, wird $f_{n}=f_{n-1}+f_{n-2}$, also die Rekursion der Fibonaccifolge. Das tritt ein, wenn $x$ das reziproke Teilverhältnis $\Phi$ des goldenen Schnitts oder sein algebraisch konjugiertes $\Psi$ ist. Die Folgen $\Phi ^{0},\Phi ^{1},\Phi ^{2},\dots$ und $\Psi ^{0},\Psi ^{1},\Psi ^{2},\dots$ sind Lösungen der Rekursionsgleichung. Außerdem wird die fibonaccische Rekursionsformel auch durch Linearkombinationen der beiden Lösungen, $g_{n}=c_{1}\Phi ^{n}+c_{2}\Psi ^{n}$, erfüllt.

Bestimmt man die Koeffizienten $c_{1}$ und $c_{2}$ so, dass sich wie bei der Fibonaccifolge $g_{0}=0$ und $g_{1}=1$ ergibt, erhält man die Binet-Formel. Dazu sind zwei einfache lineare Gleichungen zu lösen.“

---

Die mathematische Idee dahinter ist jedoch so gut, daß durch eine kleine Modifikation des Textes die volle mathematische Strenge erreicht wird:

Sei $C_{n}=x^{n},n\in \mathbb {N} _{0}$ eine geometrische Folge, so ergibt sich:

$C_{n+1}-C_{n}-C_{n-1}=x^{n+1}-x^{n}-x^{n-1}=(x^{2}-x-1)x^{n-1}$

Wenn also $x$ so gewählt wird, dass die charakteristische Gleichung $x^{2}-x-1=0$ erfüllt ist (also $x=\varphi$ oder $x=\psi \$), wird $C_{n+1}=C_{n}+C_{n-1}$, d.h. $C_{n}$ erfüllt die Fibonacci-Rekursion mit dem Rekursionsanfang $C_{0}=1$ und $C_{0}=x$.

Wichtig ist also folgende Erkenntnis:

Die rekursive Folge $A_{0}=1$, $A_{1}=\varphi$, $A_{n+1}=A_{n}+A_{n-1}$ hat die explizite Darstellung $A_{n}=\varphi ^{n}$. Ebenso $B_{0}=1$, $B_{1}=\psi \$, $B_{n}=\psi ^{n}\$

Mit $A_{n}$ und $B_{n}$ genügt auch jede Linearkombination $L_{n}=\alpha A_{n}+\beta B_{n}$der Fibonacci-Rekursion $L_{n+1}=L_{n}+L_{n-1}$. Mit Hilfe eines linearen Gleichungssystems ergibt sich $\alpha ={\frac {1}{\sqrt {5}}}$ und $\beta =-{\frac {1}{\sqrt {5}}}$ damit $L_{0}={\frac {\varphi ^{0}-\psi ^{0}}{\sqrt {5}}}=0=f_{0}$ und $L_{1}={\frac {\varphi ^{1}-\psi ^{1}}{\sqrt {5}}}=1=f_{1}$. Folglich ergibt sich explizit $F_{n}={\frac {A_{n}-B_{n}}{\sqrt {5}}}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}}$.

Für $\alpha =\beta =1$ ergibt sich $L_{0}=2$ und $L_{1}=1$, d.h. die klassische Lucas-Folge mit explizit $L_{n}=A_{n}+B_{n}=\varphi ^{n}+\psi ^{n}$. --Skraemer 13:51, 13. Mär. 2010 (CET)

Ist bei der Formel von Moivre-Binet die Gauß-Klammer nicht fehl an Platz, wird Sie nicht nur bei dem weglassen der hinteren Formel benötigt? (nicht signierter Beitrag von 92.193.8.219 (Diskussion) 09:00, 22. Jun. 2010 (CEST))

Müsste es nicht "...erfüllt die Fibonacci-Rekursion mit dem Rekursionsanfang $C_{0}=1$ und $C_{1}=x$." heißen? Also eine 1 statt einer 0 am zweiten C? -- Epaminaidos 00:58, 7. Okt. 2010 (CEST)

So ist es, ich habe es korrigiert. --91.32.87.198 14:11, 7. Okt. 2010 (CEST)

"Negafibonacci"

habe ich nirgends außerhalb Wikipedia und Co. belegt gefunden, abgesehen von [1], wo es etwas anderes bedeutet. Die Bezeichnung erscheint mir auch höchst überflüssig. --91.32.81.210 16:25, 13. Jan. 2011 (CET)

Donald E. Knuth: The Art Of Computer Programming, Volume 4., Seite 36 in diesem Preview: http://www-cs-faculty.stanford.edu/~uno/fasc1a.ps.gz . Das von dir angegebene Textstück referenziert per [41] genau dieses Buch. --Daniel5Ko 17:40, 13. Jan. 2011 (CET)

Hmm, da ist es, wenn ich es richtig sehe, eine Wortbildung analog zu einem früher eingeführten "negadecimal system". Die Schreibweise ist dann auch entsprechend "negaFibonacci" und nicht "Negafibonacci", und die Bezeichnung "negaFibonacci numbers" (nur das erste Wort kursiv) ergibt sich dabei als Rückbildung aus dem "negaFibonacci number system" (alles kursiv). Wenn man all das nicht vorhat, ist die Bezeichnung unverständlich. Ich würde sie immer noch entfernen, solange man nicht die Knuthsche Konstruktion erläutert. --91.32.81.210 18:36, 13. Jan. 2011 (CET)

"Die in den negativen Indexbereich erweiterte Negafibonacci-Folge" (Betonung von mir) ist sowieso falsch. Es ist ja lediglich der Teil gemeint, der aus $F_{k}$ mit $k<1$ besteht. Wie dem auch sei. Mir ist eigentlich ziemlich egal, was mit der Passage passiert. Ich wollte lediglich eine Quelle angeben, für den Fall, dass jemand etwas annehmbares basteln möchte. --Daniel5Ko 20:09, 13. Jan. 2011 (CET)

Danke für die Recherche, auch von mir aus kann das gerne jemand damit erweitern. Ich entferne aber das meiner Ansicht nach eher irreführende "so genannte Negafibonacci-Folge". --91.32.81.210 20:25, 13. Jan. 2011 (CET)

Erzeugende Funktion

Da scheinbar andauernd verkehrt korrigiert wird, hier mal 'ne kurze Herleitung: Wir starten mit Haskell-Folklore, von der wir wissen, dass die Fib-Folge, beginnend mit $0,1$, definiert werden kann als

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Übersetzen wir das in eine erzeugende Funktion $F$, so lautet die Gleichung $F(x)=0+x+x^{2}(F(x)+F(x)/x)$. Nun weiter:

${\begin{aligned}F(x)&=0+x+x^{2}(F(x)+F(x)/x)\\F(x)&=0+x+x^{2}F(x)+xF(x)\\F(x)(1-x-x^{2})&=x\\F(x)&={\frac {x}{1-x-x^{2}}}\end{aligned}}$

Vielleicht könnte man das auch einigermaßen vernünftig (insbesondere der Start mit Haskell-Folklore ist ein wenig faul ;) ) in den Artikel einbauen. So oder so kann man nun per "Siehe Disk." möglicherweise lehrreicher/konstruktiver revertieren^^... --Daniel5Ko 00:19, 2. Feb. 2011 (CET)

Die Fib-Folge beginnend mit $1,1$ kann definiert werden als

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Übersetzen wir das in eine erzeugende Funktion $F$, so lautet die Gleichung $F(x)=1+x+x^{2}(F(x)+(F(x)-1)/x)$. Nun weiter:

${\begin{aligned}F(x)&=1+x+x^{2}(F(x)+(F(x)-1)/x)\\F(x)&=1+x+x^{2}F(x)+xF(x)-x\\F(x)(1-x-x^{2})&=1\\F(x)&={\frac {1}{1-x-x^{2}}}\end{aligned}}$

Aber dieser Folgenstart ist halt nicht der im Artikel verwendete... --Daniel5Ko 00:19, 2. Feb. 2011 (CET)