Fibonaccizahlen
wuerg, 11.06.2005 01:24
Nach den Prim- und den Polygonalzahlen sind die Fibonaccizahlen von weitreichendem Interesse. Die erste und zweite Fibonaccizahl sind einfach F(1)=F(2)=1, jede weitere entsteht durch Addition der beiden vorangehenden, also F(n)=F(n-1)+F(n-2). 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 Fibonaccizahlen gerne in der Natur vorkommen, ist mir ein genaueres Beispiel aus dem Baubereich doch lieber: Man will eine 20 cm hohe Mauer mit Ziegelsteinen der Größe 10 mal 20 cm verkleiden oder bauen. Diese Steine kann man waagerecht oder senkrecht verwenden. Wieviele Ziegelstein-Muster a(n) für eine Mauer von n Dezimetern 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 Fibonaccizahlen:
F(n) = ( Φn - (-φ)n ) / √5
Im wesentlichen wächst also F(n) in jedem Schritt um den Faktor Φ. Von der damit gegebenen Mittellinie Φⁿ/√5 weicht F(n) um den immer kleiner werdenden Betrag φⁿ/√5 ab. [3]
[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 Fibonaccizahlen und die Fibonaccifolge.
[3] Mit dem Taschenrechner berechnet sich zum Beispiel die 12. Fibonaccizahl wie folgt: 1+√5=/2=^12=/√5 ergibt 144,001..., gerundet F(12)=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 Fibonaccifolge 10110101 ..., für die man keine Kaninchen benötigt: Mit 0 beginnend wird schrittweise 0 durch 1 und 1 durch 10 ersetzt.Obwohl die Fibonaccizahlen gerne in der Natur vorkommen, ist mir ein genaueres Beispiel aus dem Baubereich doch lieber: Man will eine 20 cm hohe Mauer mit Ziegelsteinen der Größe 10 mal 20 cm verkleiden oder bauen. Diese Steine kann man waagerecht oder senkrecht verwenden. Wieviele Ziegelstein-Muster a(n) für eine Mauer von n Dezimetern 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(n)=a(n-1)+a(n-2): 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(n-1) und mit waagerechten a(n-2), insgesamt also a(n)=a(n-1)+a(n-2). Da zudem a(1)=1=F(2) und a(2)=2=F(3) ist, muß a(n)=F(n+1) sein.Weitgehend bekannt ist das sich der goldenen Zahl nähernde Verhältnis zweier aufeinanderfolgenden Fibonaccizahlen:
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,618034 liegen. Mit einem kleinen Phi wird der goldene Schnitt φ=0,6180... 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, kann auch die Binetsche Formel für die Fibonaccizahlen kompakt geschrieben werden:
F(n) = ( Φn - (-φ)n ) / √5
Im wesentlichen wächst also F(n) in jedem Schritt um den Faktor Φ. Von der damit gegebenen Mittellinie Φⁿ/√5 weicht F(n) um den immer kleiner werdenden Betrag φⁿ/√5 ab. [3]
[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 Fibonaccizahlen und die Fibonaccifolge.
[3] Mit dem Taschenrechner berechnet sich zum Beispiel die 12. Fibonaccizahl wie folgt: 1+√5=/2=^12=/√5 ergibt 144,001..., gerundet F(12)=144.
Goldener Schnitt
... comment
wuerg,
18.06.2005 20:04
Die Fibonaccizahlen haben natürlich viele schöne Eigenschaften. Wegen des Bildungsgesetzes F(n)=F(n-1)+F(n-2) verwundert es natürlich nicht, daß die Fibonaccizahlen auch in der Differenzenfolge d(n)=F(n)-F(n-1) vorkommen:
F(-n)=F(-n+2)-F(-n+1)=F(n)·(-1)ⁿ⁻¹ in die negative Richtung fortgesetzt wird:
Differenzenfolge | Summenfolge
n: 1 2 3 4 5 6 7 8 9 10 11 ... F(n): 1 1 2 3 5 8 13 21 34 55 89 ... d(n): 0 1 1 2 3 5 8 13 21 34 ...Offensichtlich ist d(2)=0 und d(n)=F(n-2) für n>2. Der Übergang zur Differenzenfolge besteht also im wesentlichen aus einer Verschiebung um zwei Positionen in die positive Richtung. Aus diesem Grunde könnte man voreilig für die durch s(n)=s(n-1)+F(n) definierte Summenfolge s(n)=F(n+2) annehmen. Das stimmt aber nur, wenn man nicht wie hier
n: 1 2 3 4 5 6 7 8 9 10 ... F(n): 1 1 2 3 5 8 13 21 34 55 ... s(n): 1 2 4 7 12 20 33 54 88 143 ...mit naheliegendem s(0)=0, sondern s(0)=1 beginnt. Das leuchtet sofort ein, wenn die Fibonacci-​Folge mit
F(-n)=F(-n+2)-F(-n+1)=F(n)·(-1)ⁿ⁻¹ in die negative Richtung fortgesetzt wird:
n: ... -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 ... d(n): ... 13 -8 5 -3 2 -1 1 0 1 1 2 3 ... F(n): ... -8 5 -3 2 -1 1 0 1 1 2 3 5 8 ... s(n): ... 2 -1 1 0 1 1 2 3 5 8 13 21 ...Das sollte zumindest Oberschüler an die Differential- und Integralrechnung erinnern, wo die Ableitung des Integrales wieder auf die Funktion selbst führt, umgekehrt die Integration der Ableitung aber einen frei wählbaren Versatz aufweist, der zumeist mit c abgekürzt wird.
Differenzenfolge | Summenfolge
... link
... comment
wuerg,
19.06.2005 22:50
Der Fibonacci-Folge selbst und vor allem der Binetschen Formel
F(n) = ( Φn - (-φ)n ) / √5
entnimmt man, daß mit größer werdendem n sich der Quotient zweier aufeinanderfolgender Fibonaccizahlen immer mehr der goldenen Zahl Φ nähert. Für große n gilt also
F(n-1) : F(n) : F(n-1) ≈ φ : 1 : Φ
womit F(n) in der Nähe des geometrischen Mittels von F(n-1) und F(n+1) liegt. Somit verwundert nicht, daß die Folgen Q(n)=F(n)·F(n) und P(n)=F(n-1)·F(n+1) nur wenig voneinander abweichen:
F(n-1)·F(n+1) = F(n)2 + (-1)n
Bildet man zur Folge Q der Quadrate der Fibonaccizahlen die Summenfolge S
F(1)2 + F(2)2 + F(3)2 + ... + F(n)2 = F(n)·F(n+1)
führt, die durch
F(n) = ( Φn - (-φ)n ) / √5
entnimmt man, daß mit größer werdendem n sich der Quotient zweier aufeinanderfolgender Fibonaccizahlen immer mehr der goldenen Zahl Φ nähert. Für große n gilt also
F(n-1) : F(n) : F(n-1) ≈ φ : 1 : Φ
womit F(n) in der Nähe des geometrischen Mittels von F(n-1) und F(n+1) liegt. Somit verwundert nicht, daß die Folgen Q(n)=F(n)·F(n) und P(n)=F(n-1)·F(n+1) nur wenig voneinander abweichen:
n: 1 2 3 4 5 6 7 8 9 ... F(n): 1 1 2 3 5 8 13 21 34 ... P(n): 2 3 10 24 65 168 442 1155 ... Q(n): 1 1 4 9 25 64 169 441 1156 ...Offensichtlich unterscheiden sich P und Q stets um 1, abwechselnd in die eine und die andere Richtung. Es gilt
F(n-1)·F(n+1) = F(n)2 + (-1)n
Bildet man zur Folge Q der Quadrate der Fibonaccizahlen die Summenfolge S
n: 1 2 3 4 5 6 7 8 9 10 ... F(n): 1 1 2 3 5 8 13 21 34 55 ... Q(n): 1 1 4 9 25 64 169 441 1156 3025 ... S(n): 1 2 6 15 40 104 273 714 1870 3026 ...kann man sehen und sodann nachrechnen, daß S(n)=F(n)·F(n+1) ist, was auf die schöne Beziehung
F(1)2 + F(2)2 + F(3)2 + ... + F(n)2 = F(n)·F(n+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(n)=F(n-1)+F(n-2), gibt es Beziehungen zwischen und mit Fibonaccizahlen wie Sand am Meer. Neben den bereits erwähnten
F(1) + F(2) + F(3) + ... + F(n) = F(n+2)-1
F(n-1)·F(n+1) = F(n)2 + (-1)n
F(1)2 + F(2)2 + F(3)2 + ... + F(n)2 = F(n)·F(n+1)
hier nur noch ein paar davon:
F(1) + F(2) + F(3) + ... + F(n) = F(n+2)-1
F(n-1)·F(n+1) = F(n)2 + (-1)n
F(1)2 + F(2)2 + F(3)2 + ... + F(n)2 = F(n)·F(n+1)
hier nur noch ein paar davon:
F(n+3) + F(n) = 2·F(n+2) 21+5=2·13 34+8=2·21 55+13=2·34 F(n+3) - F(n) = 2·F(n+1) 21-5=2·8 34-8=2·13 55-13=2·21 F(n+2) + F(n-2) = 3·F(n) 13+2=3·5 21+3=3·8 34+5=3·13 F(n+1)2 + F(n)2 = F(2n+1) 82+52=89=F(11) F(n+1)2 - F(n)2 = F(n+2)·F(n-1) 82-52=39=13·3 F(n+1)2 - F(n-1)2 = F(2n) 82-32=55=F(10) F(n+1)3 + F(n)3 - F(n-1)3 = F(3n) 83+53-33=610=F(15)
... link
... comment
