Fibonaccizahlen
Nach den Primzahlen 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, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Sehr gerne wird die Entstehung dieser Folge mit Kaninchen verdeutlicht, die an ihrem zweiten, dritten, vierten und jedem weiteren Geburtstag ein kleines Häschen werfen. Man beginnt mit einem Hasen, der sich wie folgt vermehrt:
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 Hasen im Alter von 0 Jahren und 1 einen älteren. Das ist natürlich Quatsch, weil es nicht der Natur entspricht, auch wenn man nur die weiblichen Hasen betrachtet. Insbesondere leben Hasen nicht beliebig lang.

Obwohl die Fibonacci-Zahlen 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. Und die Frage ist, wieviele verschiedene Ziegelstein-Muster a(n) für eine Mauer der Lange 20*n Zentimeter möglich sind. Offensichtlich gibt es die 1, 2, 3, 5 und 8 Muster für Mauern der bescheidenen Länge von 10, 20, 30, 40 bzw. 50 Zentimetern.
+---+                   +---+---+   +-------+
|   |                   |   |   |   |       |
|   |                   |   |   |   +-------+
|   |                   |   |   |   |       |
+---+                   +---+---+   +-------+

+---+---+---+   +---+-------+   +-------+---+
|   |   |   |   |   |       |   |       |   |
|   |   |   |   +   +-------+   +-------+   |
|   |   |   |   |   |       |   |       |   |
+---+---+---+   +---+-------+   +-------+---+
gibt n=1,2,3 wieder. 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 wagerechtem a(n-2), insgesamt also a(n)=a(n-1)+a(n-2). Da a(1)=1=F(2) und a(2)=2=F(3) ist, muß a(n)=F(n+1) sein.

Weitgehend bekannt ist, daß das Verhältnis zweier aufeinander folgenden Fibonacci-Zahlen sich dem goldenen Schnitt nähert:
  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,618182
Die Darstellung in zwei Spalten soll verdeutlichen, daß die Näherungen abwechselnd unter und über dem goldenen Schnitt Phi=1,6180... liegen. Mit einem kleinen phi wird der Kehrwert phi=0,6180... bezeichnet. Es ist
Phi = (sqrt(5)+1)/2 = 1/phi = phi+1 = 1,6180339887498948482...
phi = (sqrt(5)-1)/2 = 1/Phi = Phi-1 = 0,6180339887498948482...
Mit diesen beiden an vielen Stellen vorkommenden Zahlen, kann auch eine geschlossene Formel für die Fibonacci-Zahlen angegeben werden. Es ist
F(n) = ( Phi^n - (-phi)^n ) / sqrt(5)
Im wesentlichen wächst also F(n) in jedem Schritt um den Faktor Phi. Von der damit gegebenen Mittellinie Phi^n weicht F(n) um den immer kleiner werdenden Betrag phi^n ab.

Sloane | Goldener Schnitt

... comment

 
Die Folge F(1),F(2),F(3),... der Fibonaccizahlen hat 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 vorkommen:
F:     1   1   2   3   5   8   13   21    34    55    ...
d:   1   0   1   1   2   3   5    8    13    21    ...
Offensichtlich ist d(1)=1, 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 Summenfolge s(n)=F(n+2) annehmen. Das stimmt aber nicht:
F:     1   1   2   3   5    8    13    21    34    55    ...
s:       1   2   4   7   12   20    33    54    88    ...
Offensichtlich ist s(n)=F(n+2)-1. Diese dumme Abweichung um 1 rührt von den Anfangswerten her. Hätte man nicht mit s(1)=1, sondern mit s(2)=2 begonnen, wäre alles viel ebenmäßiger. Dann wäre die Summenfolge einfach die um die vordersten beiden Glieder beschnitte Fibonaccifolge selbst. Zur Behebung dieser Unschönheit liegt die Idee nahe, die Startschwierigkeiten zu beseitigen, indem man die Fibonaccifolge mit Hilfe der Gleichung F(n)=F(n+2)-F(n+1) in die negative Richtung fortsetzt:
F:   ...  5  -3   2  -1   1   0   1   1   2   3   5   8  ...
d:     ... -8   5  -3   2  -1   1   0   1   1   2   3   5  ...
Dann wäre die Differenzenfolge von vorne bis hinten (von minus bis plus unendlich) einfach die um zwei Positionen verschobene Fibonaccifolge selbst. Und in die negative Richtung um zwei verschoben erhielte man sodann eine Summenfolge. Aber eben nur "eine", nicht mehr "die" Summenfolge. Ist nämlich ...,s(-1),s(0),s(1),s(2),... eine Summenfolge, so auch die mit Gliedern s(i)+c, worin c frei wählbar ist.

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 c aufweist. Darüber täuscht man sich leicht hinweg, wenn man zum Beispiel einfach exp(x) als die Integralfunktion von der Exponentialfunktion exp(x) betrachtet, denn 35+exp(x) wäre auch ein Kandidat. Natürlich zeichnet die Integralfunktion exp(x) vor 35+exp(x) aus, daß sie völlig mit der integrierten Funktion identisch ist. Ebenso zeichnet die Summenfolge mit s(i)=F(n+2) aus, daß sie allein durch Verschiebung aus der Fibonaccifolge selbst hervorgeht.

Doch das sind Einzelfallbetrachtungen, deren Wert darin besteht, dem Menschen die Vorstellung zu erleichtern, weil die Beziehungen dann ebenmäßiger werden. Auch hat der Mensch den Hang, genau solche Fälle interessant zu finden, was aber hoffentlich über die unvollkommene Natur des Menschen hinaus gerechtfertigt ist. Außerirdische mit vergleichbarer Intelligenz und Merkfähigkeit würden wohl nicht zu völlig anderen Auffassungen gelangen und weitgehend die gleichen Vorstellungen von Einfachheit entwickelt haben. Diese Einfachheit ist ein Grund, weshalb gelegentlich zu Folgen alle oder wenigstens einige Glieder mit Index kleiner als 1 gebildet werden. Der Start bei 0 statt 1 macht Formeln gelegentlich angenehmer. Und geeignete Werte zum Index 0, -1 und kleiner machen manchmal eine Rekursionsformel für alle n>0 gültig, die sonst für n=1 oder weitere kleine n nicht gelten würde.

Differenzenfolge | Summenfolge

... link  


... comment
 
Der Fibonaccifolge selbst und vor allem der Binetschen Formel
F(n) = ( Phi^n - (-phi)^n ) / sqrt(5)
entnimmt man, daß mit größer werdenden n sich der Quotient zweier aufeinanderfolgender Fibonaccizahlen immer mehr dem goldenen Schnitt nähert. Für große n ist F(n)/F(n-1) ungefähr Phi=1,618... und somit F(n)/F(n+1) näherungsweise phi=0,618..., was insbesondere bedeutet, daß F(n) in der Nähe des geometrischen Mittels von F(n-1) und F(n+1) liegt. Somit verwundert es nicht, daß die Folgen Q(n)=F(n)*F(n) und P(n)=F(n-1)*F(n+1) nur wenig voneinander abweichen:
F:     1  1  2   3   5   8   13   21    34   55    ...
P:     -  2  3  10  24  65  168  442  1155   ...
Q:     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. Und
F(n-1)*F(n+1) - F(n)*F(n) = (-1)^n
gilt wirklich für alle n>1, nicht nur für die errechneten ersten neun. Bildet man zur Folge Q der Quadrate der Fibonaccizahlen die Summenfolge S
F:     1  1  2   3   5    8   13   21    34   55    ...
Q:     1  1  4   9  25   64  169  441  1156   ...
S:     1  2  6  15  40  104  273  714  1870   ...
so kann man mit etwas Geduld sehen, daß S(n)=F(n)*F(n+1), also
F(1)^2 + F(2)^2 + F(3)^2 + ... + F(n)^2 = F(n)*F(n+1)
ist. Auch daß läßt sich relativ leicht nachrechnen, womit dieser
+-------------------------+---------------+
|                         |               |
|                         |               |
|                         |               |
|                         |    F(5)^2     |
|                         |               |
|                         |               |
|       F(6)^2            |               | F(6)
|                         +---------+-----+
|                         |         |     |
|                         |         |     |
|                         |         +--+--+
|                         |         |  |  |
+-------------------------+---------+--+--+
                     F(7)
anschauliche Beweis formal untermauert wäre.

... link  


... comment
 
Es ist müßig, eine Beziehung über Fibonaccizahlen nach der anderen aufzuführen. Wegen der Einfachheit der Rekursion F(n)=F(n-1)+F(n-2) gibt es sie 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)*F(n) = (-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)          8*8+5*5=89=F(11)
F(n+1)^2 – F(n)^2 = F(n+2)*F(n–1)    8*8-5*5=39=3*13
F(n+1)^2 – F(n–1)^2 = F(2n)          8*8-3*3=55=F(10)

F(n+1)^3 + F(n)^3 – F(n–1)^3 = F(3n) 8*8*8+5*5*5-3*3*3=610
Jede Zahl m ist Teiler einer der Fibonaccizahlen F(1),F(2),...,F(m*m) und teilt unendlich viele weitere Fibonaccizahlen, denn ist m Teiler von F(n), so ist m auch Teiler von F(kn) für jede natürliche Zahl k.
2 teilt F(3)=2, F(6)=8, F(9)=34, F(12)=144, F(15)=610, ...
3 teilt F(4)=3, F(8)=21, F(12)=144, F(16)=987, ...
4 teilt F(6)=8, F(12)=144, F(18)2584, F(24)=46368, ...
5 teilt F(5)=5, F(10)=55, F(15)=610, F(20)=6765, ...
6 teilt F(12)=144, F(24)=46368, F(36)=14930352, ...
7 teilt F(8)=21, F(16)=987, F(24)=46368, F(32)=2178309, ...
8 teilt F(6)=8, F(12)=144, F(18)2584, F(24)=46368, ...
9 teilt F(12)=144, F(24)=46368, F(36)=14930352, ...
Es ist bemerkenswert, daß die 12. Fibonaccizahl wegen F(12)=144=12*12 gleich der 12. Quadratzahl ist. Doch so zufällig ist der Treffer nicht: Da 4 und 6 Teiler von 12 sind, müssen F(4)=3 und F(6)=8 Teiler von F(12) sein. Für F(12) kommt also nur ein Vielfaches von 24 in Frage.

Knott

... link  


... comment