Fibonacci-Zahlen
wuerg, 11.06.2005 01:24
Nach den Prim- und den Polygonalzahlen sind die Fibonacci-Zahlen von weitreichendem Interesse. Die erste und zweite Fibonacci-Zahl lauten einfach F₁=F₂=1, jede weitere entsteht durch Addition der beiden vorangehenden, also Fₙ=Fₙ₋₁+Fₙ₋₂. Das ergibt die Fibonacci-Folge [1]
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Sehr gerne wird die Entstehung dieser Folge mit Kaninchen verdeutlicht. Werfen sie an ihrem zweiten, dritten, vierten und jedem weiteren Geburtstag ein kleines Häschen [2], vermehren sie sich wie folgt:
Obwohl die Fibonacci-Zahlen gerne in der Natur vorkommen, ist mir ein zutreffenderes Beispiel aus dem Baubereich doch lieber: Es ist eine 20 cm hohe Mauer mit Ziegelsteinen der Größe 10 mal 20 cm zu verkleiden. Diese Steine können waagerecht oder senkrecht verbaut werden. Wieviele Muster aₙ für eine Mauer von n Dezimetern Länge sind möglich? Offensichtlich gibt es 1, 2 und 3 Muster für Mauern der bescheidenen Länge von 10, 20 und 30 Zentimetern.
Weitgehend bekannt ist das sich der goldenen Zahl nähernde Verhältnis zweier aufeinanderfolgenden Fibonacci-Zahlen:
Φ = (√5+1)/2 = 1/φ = φ+1 = 1,6180339887498948482...
φ = (√5−1)/2 = 1/Φ = Φ−1 = 0,6180339887498948482...
Mit diesen beiden an vielen Stellen vorkommenden Zahlen, lautet die Binetsche Formel [4] für die Fibonacci-Zahlen:
Fₙ = ( Φn − (−φ)n ) / √5
Im wesentlichen wächst also Fₙ in jedem Schritt um den Faktor Φ. Von der damit gegebenen Mittellinie Φⁿ/√5 weicht Fₙ um den immer kleiner werdenden Betrag φⁿ/√5 ab. [5]
[1] The On-Line Ecyclopedia of Integer Sequences. A000203
[2] Ich weiß, Has*innen sind keine Kaninchen, und auch die gebärenden unter ihnen werfen nicht beliebig lange genau ein Häschen/elein pro Jahr. Hauptsache es entstehen die Fibonacci-Zahlen und die Fibonacci-Folge. Man kann die Zibben auch schon im ersten Jahr werfen und dafür mit der Geburt eines zweiten Zibbeleins sterben lassen. So habe ich es in meinem Beitrag zur Zahl 13 geschehen lassen.
[3] Der aufmerksame Leser wird nun einwenden können, die Überlegung sei unvollständig, weil immer nur geradlinig abschließende Mauern verlängert würden. Doch habe ich dies stillschweigend vorausgesetzt, da ja gradlinig begonnen wird und auch nur gradlinig fortgesetzt werden kann. Ein Ziegelversatz wie an Hauswänden ist also nicht möglich. Aber tatsächlich steckt in der Ungradlinigkeit die Herausforderung, wenn man die Mauer höher als zwei Einheiten anlegt.
[4] Die Binetsche Formel ergibt sich aus folgender Überlegung: Da Φ und −φ Wurzeln der Gleichung x²=x+1 sind, erfüllen nicht nur die beiden Folgen der Potenzen von Φ und −φ die Rekursionsgleichung der Fibonacci-Folge, sondern auch alle Linearkombinationen αΦⁿ+β(−φ)ⁿ. Aus den Gleichungen αΦ−βφ=F₁=1 und αΦ²+βφ²=F₂=1 ergeben sich für die Fibonacci-Folge die beiden Gewichte α=1/√5 und β=−1/√5.
[5] Mit dem Taschenrechner berechnet sich zum Beispiel die 12. Fibonacci-Zahl wie folgt: 1+√5=/2=^12=/√5 ergibt 144,001…, gerundet F₁₂=144.
Goldener Schnitt
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Sehr gerne wird die Entstehung dieser Folge mit Kaninchen verdeutlicht. Werfen sie an ihrem zweiten, dritten, vierten und jedem weiteren Geburtstag ein kleines Häschen [2], vermehren sie sich wie folgt:
Beginn des 1. Jahres: 0
|
Beginn des 2. Jahres: 1--------------+
| |
Beginn des 3. Jahres: 1--------+ 0
| | |
Beginn des 4. Jahres: 1-----+ 0 1-----+
| | | | |
Beginn des 5. Jahres: 1--+ 0 1--+ 1--+ 0
| | | | | | | |
Beginn des 6. Jahres: 1 0 1 1 0 1 0 1
Darin bezeichnet 0 einen neugeborenen Hasen und 1 einen nach seinem ersten Geburtstag. Ordnen sie sich wie dargestellt an, entsteht die Fibonacci-Folge 10110101…, für die man keine Kaninchen benötigt: Mit 0 beginnend wird schrittweise 0 durch 1 und 1 durch 10 ersetzt.Obwohl die Fibonacci-Zahlen gerne in der Natur vorkommen, ist mir ein zutreffenderes Beispiel aus dem Baubereich doch lieber: Es ist eine 20 cm hohe Mauer mit Ziegelsteinen der Größe 10 mal 20 cm zu verkleiden. Diese Steine können waagerecht oder senkrecht verbaut werden. Wieviele Muster aₙ für eine Mauer von n Dezimetern Länge sind möglich? Offensichtlich gibt es 1, 2 und 3 Muster für Mauern der bescheidenen Länge von 10, 20 und 30 Zentimetern.
+---+ +---+---+ +-------+ | | | | | | | | | | | | +-------+ | | | | | | | +---+ +---+---+ +-------+ +---+---+---+ +---+-------+ +-------+---+ | | | | | | | | | | | | | | | +-------+ +-------+ | | | | | | | | | | | +---+---+---+ +---+-------+ +-------+---+Für größere n wähle ich eine kompaktere Darstellung mit | für einen senkrechten und == für zwei waagerechte Ziegel:
n=4: |||| ||== |==| ==|| ====
n=5: ||||| |||== ||==| |==||
==||| |==== ==|== ====|
Damit ist Verdacht auf Fibonacci gegeben, und tatsächlich führt die folgende Überlegung auf aₙ=aₙ₋₁+aₙ₋₂: Mauern der Länge n mit einem senkrechten Ziegel am Ende gibt es soviele wie Mauern der Länge n−1, und Mauern der Länge n mit zwei waagerechten Ziegeln am Ende soviele wie von der Länge n−2. Mit senkrechtem Ziegel am Ende sind es demnach aₙ₋₁ und mit waagerechten aₙ₋₂, insgesamt also aₙ=aₙ₋₁+aₙ₋₂. Da zudem a₁=1=F₂ und a₂=2=F₃ ist, muß aₙ=Fₙ₊₁ sein. [3]Weitgehend bekannt ist das sich der goldenen Zahl nähernde Verhältnis zweier aufeinanderfolgenden Fibonacci-Zahlen:
3/2 = 1,500000 5/3 = 1,666667 8/5 = 1,600000 13/8 = 1,625000 21/13 = 1,615385 34/21 = 1,619048 55/34 = 1,617647 89/55 = 1,618182Die Darstellung in zwei Spalten soll verdeutlichen, daß die Näherungen abwechselnd unter und über der goldenen Zahl Φ≈1,618 liegen. Mit einem kleinen Phi wird der goldene Schnitt φ≈0,618 bezeichnet. Es gilt:
Φ = (√5+1)/2 = 1/φ = φ+1 = 1,6180339887498948482...
φ = (√5−1)/2 = 1/Φ = Φ−1 = 0,6180339887498948482...
Mit diesen beiden an vielen Stellen vorkommenden Zahlen, lautet die Binetsche Formel [4] für die Fibonacci-Zahlen:
Fₙ = ( Φn − (−φ)n ) / √5
Im wesentlichen wächst also Fₙ in jedem Schritt um den Faktor Φ. Von der damit gegebenen Mittellinie Φⁿ/√5 weicht Fₙ um den immer kleiner werdenden Betrag φⁿ/√5 ab. [5]
[1] The On-Line Ecyclopedia of Integer Sequences. A000203
[2] Ich weiß, Has*innen sind keine Kaninchen, und auch die gebärenden unter ihnen werfen nicht beliebig lange genau ein Häschen/elein pro Jahr. Hauptsache es entstehen die Fibonacci-Zahlen und die Fibonacci-Folge. Man kann die Zibben auch schon im ersten Jahr werfen und dafür mit der Geburt eines zweiten Zibbeleins sterben lassen. So habe ich es in meinem Beitrag zur Zahl 13 geschehen lassen.
[3] Der aufmerksame Leser wird nun einwenden können, die Überlegung sei unvollständig, weil immer nur geradlinig abschließende Mauern verlängert würden. Doch habe ich dies stillschweigend vorausgesetzt, da ja gradlinig begonnen wird und auch nur gradlinig fortgesetzt werden kann. Ein Ziegelversatz wie an Hauswänden ist also nicht möglich. Aber tatsächlich steckt in der Ungradlinigkeit die Herausforderung, wenn man die Mauer höher als zwei Einheiten anlegt.
[4] Die Binetsche Formel ergibt sich aus folgender Überlegung: Da Φ und −φ Wurzeln der Gleichung x²=x+1 sind, erfüllen nicht nur die beiden Folgen der Potenzen von Φ und −φ die Rekursionsgleichung der Fibonacci-Folge, sondern auch alle Linearkombinationen αΦⁿ+β(−φ)ⁿ. Aus den Gleichungen αΦ−βφ=F₁=1 und αΦ²+βφ²=F₂=1 ergeben sich für die Fibonacci-Folge die beiden Gewichte α=1/√5 und β=−1/√5.
[5] Mit dem Taschenrechner berechnet sich zum Beispiel die 12. Fibonacci-Zahl wie folgt: 1+√5=/2=^12=/√5 ergibt 144,001…, gerundet F₁₂=144.
Goldener Schnitt
... comment
wuerg,
18.06.2005 20:04
Die Fibonacci-Zahlen haben natürlich viele schöne Eigenschaften. Wegen des Bildungsgesetzes Fₙ=Fₙ₋₁+Fₙ₋₂ verwundert es natürlich nicht, daß die Fibonacci-Zahlen auch in der Differenzenfolge dₙ=Fₙ₊₁−Fₙ vorkommen:
Differenzenfolge | Summenfolge
n: 1 2 3 4 5 6 7 8 9 10 11 ... Fn: 1 1 2 3 5 8 13 21 34 55 89 ... dn: 0 1 1 2 3 5 8 13 21 34 55 ...Offensichtlich ist d₁=0 und dₙ=Fₙ₋₁ für n>1. Der Übergang zur Differenzenfolge besteht also im wesentlichen aus einer Verschiebung um eine Positionen in die positive Richtung. Aus diesem Grunde könnte man für die durch sₙ=F₁+F₂+…+Fₙ definierte Summenfolge sₙ=Fₙ₊₁ erwarten. Doch
n: 1 2 3 4 5 6 7 8 9 10 ... Fn: 1 1 2 3 5 8 13 21 34 55 ... sn: 1 2 4 7 12 20 33 54 88 143 ...verdeutlicht sₙ=Fₙ₊₂−1 mit zwei Unschönheiten. Versöhnlicher sähe es aus, wenn man die Fibonacci-Folge mit F₋ₙ=F₂₋ₙ−F₁₋ₙ=Fₙ·(−1)ⁿ⁻¹ in die negative Richtung fortsetzte, die Summation ab n=−2 mit s₋₂=0 begänne und die Differenzen gemäß dₙ=Fₙ−Fₙ₋₁ definierte:
n: ... -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 ... dn: ... 21 13 -8 5 -3 2 -1 1 0 1 1 2 3 ... Fn: ... -8 5 -3 2 -1 1 0 1 1 2 3 5 8 ... sn: ... 2 -1 1 0 1 1 2 3 5 8 13 21 ...Doch beides ist aus guten Gründen nicht die Konvention.
Differenzenfolge | Summenfolge
... link
... comment
wuerg,
19.06.2005 22:50
Der Fibonacci-Folge selbst und vor allem der Binetschen Formel
Fₙ = ( Φn − (−φ)n ) / √5
entnimmt man, daß mit größer werdendem n sich der Quotient zweier aufeinanderfolgender Fibonacci-Zahlen immer mehr der goldenen Zahl Φ nähert. Für große n gilt also
Fn−1 : Fn : Fn+1 ≈ φ : 1 : Φ
womit Fₙ in der Nähe des geometrischen Mittels von Fₙ₋₁ und Fₙ₊₁ liegt. Somit verwundert nicht, daß die Folgen qₙ=Fₙ² und pₙ=Fₙ₋₁·Fₙ₊₁ nur wenig voneinander abweichen:
Fn−1 · Fn+1 = Fn2 + (−1)n
Bildet man zur Folge q der Quadrate der Fibonacci-Zahlen die Summenfolge s
F12 + F22 + F32 + … + Fn2 = Fn · Fn+1
führt, die durch
Fₙ = ( Φn − (−φ)n ) / √5
entnimmt man, daß mit größer werdendem n sich der Quotient zweier aufeinanderfolgender Fibonacci-Zahlen immer mehr der goldenen Zahl Φ nähert. Für große n gilt also
Fn−1 : Fn : Fn+1 ≈ φ : 1 : Φ
womit Fₙ in der Nähe des geometrischen Mittels von Fₙ₋₁ und Fₙ₊₁ liegt. Somit verwundert nicht, daß die Folgen qₙ=Fₙ² und pₙ=Fₙ₋₁·Fₙ₊₁ nur wenig voneinander abweichen:
n: 1 2 3 4 5 6 7 8 9 ... Fn: 1 1 2 3 5 8 13 21 34 ... qn: 1 1 4 9 25 64 169 441 1156 ... pn: 2 3 10 24 65 168 442 1155 ...Offensichtlich unterscheiden sich q und p stets um 1, abwechselnd in die eine und die andere Richtung. Es gilt
Fn−1 · Fn+1 = Fn2 + (−1)n
Bildet man zur Folge q der Quadrate der Fibonacci-Zahlen die Summenfolge s
n: 1 2 3 4 5 6 7 8 9 10 ... Fn: 1 1 2 3 5 8 13 21 34 55 ... qn: 1 1 4 9 25 64 169 441 1156 3025 ... sn: 1 2 6 15 40 104 273 714 1870 3026 ...kann man sehen und sodann nachrechnen, daß sₙ=Fₙ·Fₙ₊₁ ist, was auf die schöne Beziehung
F12 + F22 + F32 + … + Fn2 = Fn · Fn+1
führt, die durch
+-------------------------+---------------+
| F(6) | F(5) |
| | |
| | |
| | F(5)|
| | |
| | |
|F(6) | |
| +---------+-----+
| | F(4) | |
| | | |
| |F(4) +--+--+
| | | | |
+-------------------------+---------+--+--+
F(7)
veranschaulicht werden kann.... link
... comment
wuerg,
21.06.2005 00:03
Wegen der Einfachheit der Rekursion Fₙ=Fₙ₋₁+Fₙ₋₂, gibt es Beziehungen zwischen und mit Fibonacci-Zahlen wie Sand am Meer. Neben den bereits erwähnten
F1 + F2 + F3 + … + Fn = Fn+2−1
Fn−1 · Fn+1 = Fn2 + (−1)n
F12 + F22 + F32 + … + Fn2 = Fn · Fn+1
hier nur noch ein paar davon:
F1 + F2 + F3 + … + Fn = Fn+2−1
Fn−1 · Fn+1 = Fn2 + (−1)n
F12 + F22 + F32 + … + Fn2 = Fn · Fn+1
hier nur noch ein paar davon:
Fn+3 + Fn = 2·Fn+2 21+5=2·13 34+8=2·21 55+13=2·34 Fn+3 - Fn = 2·Fn+1 21-5=2·8 34-8=2·13 55-13=2·21 Fn+2 + Fn-2 = 3·Fn 13+2=3·5 21+3=3·8 34+5=3·13 Fn+12 + Fn2 = F2n+1 82+52=89=F11 Fn+12 - Fn-12 = F2n 82-32=55=F10 Fn+13 + Fn3 - Fn-13 = F3n 83+53-33=610=F15
... link
... comment
