1 Fibonacci-Zahlen: Grundlagen

1.1 Definition

Üblicherweise wird die Erfindung der Fibonacci-Zahlen dem italienischen Mathematiker Leonarda von Pisa, der besser unter dem Namen Fibonacci, der Kurzform von filius Bonacci, bekannt ist, zugeschrieben. In der zweiten Version seines Rechenbuchs "Liber Abacci" (Buch vom Abacus) - die erste Version ist nicht überliefert - taucht folgende Aufgabe auf:

Jemand setzt ein Paar Kaninchen in einen Garten, der auf allen Seiten von einer Mauer umgeben ist, um herauszufinden, wieviele Kaninchen innerhalb eines Jahre geboren werden. Wenn angenommen wird, daß jeden Monat jedes Paar ein weiteres Paar erzeugt, und daß Kaninchen zwei Monate nach ihrer Geburt geschlechtsreif sind, wie viele Paare Kaninchen werden dann jedes Jahr geboren?

Ist F_n die Anzahl der Paare nach n Monaten, so sieht man sofort, daß

F_n+1=F_n+F_n-1 und F₀=1.

Wir dagegen definieren:

1.1.1. Definition

Die durch

F₀=0, F₁=1 und F_n+1=F_n+F_n-1

definierten Zahlen F_n (n in IN) heißen "Fibonacci-Zahlen".

Die ersten Fibonacci-Zahlen sind also

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377.

Es gibt natürlich viele Verallgemeinerungen der Fibonacci-Zahlen. Viele der folgenden Sätze kann man z.B. für allgemein linear rekursiv definierte Zahlenfolgen formulieren. Besonders wichtige Verallgemeinerungen oder Abwandlungen sind die Folgenden. Ich selber werde aber in diesem Skript fast ausschließlich Formeln und Sätze behandeln, in denen nur die reinen (normalen) Fibonacci-Zahlen vorkommen, und keine Abwandlungen.

1.1.2 Abwandlungen

Die durch L₀:=2, L₁:=1 und L_n+1:=L_n+L_n-1 definierten Zahlen heißen "Lucas-Zahlen". Zwischen den Fibonacci-Zahlen und den Lucas-Zahlen gibt es viele Zusammenhänge, wie z.B. L_2n+2·(-1)^n-1=5F_n². Oft kann man Summen von Fibonacci-Zahlen elegant mit Lucas-Zahlen ausdrücken.
Die durch F₀:=0, F₁:=1, F₂:=2 (und F₃:=4) und F_n+1=F_n+F_n-1+F_n-2(+F_n-3) definierte Folge heißt "Tribonacci-Folge" bzw. "Quadranacci-Folge". (Allgemein sind die Anfangswerte F_i=2^i-1.)
In der Rekursionsformel F_n+1=F_n+F_n-1 kann man das "+`" auch als Operationssymbol einer abelschen Gruppe auffassen. Im Abschnitt 2.2 werden wir untersuchen, was passiert, wenn man die Fibonacci-Folge in den endlichen zyklischen Gruppen Z/nZ betrachtet.

Die Bedingung, daß die Gruppe kommutativ ist, kann auch noch weggelassen werden: Ist G eine beliebige Gruppe (oder sogar nur eine Halbgruppe), und a,b in G, so kann man Fibonacci-artige Folgen F_n⁽¹⁾ und F_n⁽²⁾ definieren durch

F₀⁽ⁱ⁾:=a, F₁⁽ⁱ⁾:=b, und F_n+1⁽¹⁾:=F_n⁽¹⁾F_n-1⁽¹⁾ bzw. F_n+1⁽²⁾:=F_n-1⁽²⁾F_n⁽²⁾

1.2 Die einfachsten Formeln

In diesem Kapitel werde ich die einfachsten Formeln mit Fibonacci-Zahlen angeben. Insbesondere finden sich darunter Formeln für die Summen von Fibonacci-Zahlen. Fast alle Formeln in diesem Abschnitt können ganz einfach durch vollständige Induktion bewiesen werden. Ich werde sämtliche Beweise weglassen.

1.2.3 Determinantenidentität: Es gilt:

F_n-1F_n+1-F_n²=(-1)ⁿ

Für die Frage, warum ich diese Formel Determinantenidentität genannt habe s. die Bemerkungen nach der Formel von Binet (1.3.9.).

1.2.4 Additionsformel: Es gilt:

F_n+m = F_n-1F_m+F_nF_m+1 = F_nF_m-1+F_n+1F_m.

Insbesondere gilt:

F_2n=F_n+1²-F_n-1², F_2n+1=F_n²+F_n+1² und F_3n=F_n+1³+F_n³-F_n-1³.

Beweis: Für m=0 und m=1 ist die Formel wahr. Man mache nun eine Induktion nach m bei festem n.

1.2.5 Summen von Fibonacci-Zahlen: Es gilt:; $\sum_{k=1}^n F_k=F_{n+2}-1, \sum_{k=1}^n F_{2k}=F_{2n+1}-1, \sum_{k=1}^n F_{2k-1}=F_{2n}.$

1.2.6 Summen von Quadraten: Es gilt:

$\sum_{k=1}^n F_k^2=F_nF_{n+1}, \sum_{k=1}^n F_kF_{k+1}=...$

1.2.7 Halbarithmetische Summe: Es gilt:; $\sum_{k=1}^n kF_k=nF_{n+2}-F_{n+3}+2.$

Natürlich gibt es noch eine riesigen Haufen anderer Formeln. Besonders schön finde ich die folgenden:

1.2.8 Noch mehr Formeln: Für passend n in IN gilt:

F_n-2F_n-1 F_n+1F_n+2 = F_n⁴-1 und F_n+1³-F_n-1³ = F_3n-F_n³.

1.3 Die Formel von Binet

Die Formel

1.3.9 Satz (Formel von Binet): Es gilt:

$F_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n -\left(\frac{1-\sqrt{5}}{2}\right)^n\right].$

Beweis

Es gibt viele Möglichkeiten, das zu beweisen. Eine z.B. durch vollständige Induktion, wobei man benutzen muß, daß für $\zeta=\frac{1+\sqrt{5}}{2}$ gilt: $\zeta^2=1+\zeta$ usw..

Eine weitere Möglichkeit ist, daß man die Formel 1.5.20 nimmt, und für die rechte Seite eine Partialbruchzerlegung durchführt, und diese dann in geometrische Reihen entwickelt.

Eine dritte Möglichkeit werden wir gleich besprechen.

Beweis durch Eigenwertrechnung

Und zwar beobachten wir, daß gilt:

$(F_{n+1}, F_n)=(1 1, 1 0)...$

Die Frage ist also, wie wir $(1 & 1 \cr 1 & 0)^n$ explizit ausrechnen können. Dazu suchen wir die beiden Eigenwerte. Diese sind $\frac{1+\sqrt{5}}{2}$ und $\frac{1-\sqrt{5}}{2}$ . Als nächstes stellen wir $\pmatrix{1\cr 0}$ als Linearkombination von Eigenvektoren dar. Dadurch bekommen wir letztendlich wieder genau die Formel von Binet.

Die Methode läßt sich leicht auch verallgemeinern für Folgen, die durch eine lineare Rekursionsformel der Form

$a_{n+k}=\sum_{i=0}^{k-1}c_ia_{n+i}$

definiert sind.

Obige Formel kann man auch so schreiben:

$\pmatrix{F_{n+1} & F_n\cr F_n & F_{n-1}}= \pmatrix{1 & 1 \cr 1 & 0}^n.$

Aus der Formel det(AB)=det(A)·det(B) folgt sofort die Determinantenidentität 1.2.3..

Das charakteristische Polynom

Hat man eine allgemeine lineare Rekursionsformel der Art $a_{n+k}=\sum_{i=0}^{k-1}c_ia_{n+i}$ , so macht man den Ansatz a_i=xⁱ. Die Rekursionsformel ergibt dann für x die Gleichung

x^k-c_k-1x^k-1-...-c₁x-c₀.

Sind x₁ und x₂ zwei Lösungen, so erfüllen alle Ausdrücke der Form l₁x₁+l₂x₂ ebenfalls die Rekursionsformel. Die Frage ist nun, ob man eine Linearkombination der Lösungen x₀,...,x_k-1 finden kann, die die Anfangswerte a₀,...,a_k-1 ergibt:

Gibt es l₀,...,l_k-1 mit a_i=l₀x₀ⁱ+...+ l_k-1x_k-1ⁱ ?

Dies ist ein lineares Gleichungssystem in l_i wobei die Matrixeinträge x_i^j sind. Sind die x_i paarweise verschieden, so ist es lösbar (Vandermondersche Determinante).

Im Falle der Fibonacci-Zahlen ist das charakteristische Polynom

x²-x-1 und x_1,2= $\frac{1\pm\sqrt{5}}{2}$ .

Folgerungen

Die Formel von Binet erlaubt uns, Summen wie F₃+F₆+F₉+... als endliche geometrische Reihen aufzufassen und auszurechnen. Beispiele sind:

1.3.10 Summen von F_kn: Es gilt:

$sum_{k=1}^nF_{3k}=\frac{1}{2}(F_{3n+2}-1), \sum_{k=1}^nF_{6k}=\frac{1}{4}(F_{6n+3}-2).$

1.3.11 Summen von Potenzen der F_n: Es gilt:

$(1) \sum_{k=1}^nF_k^3 = ... usw.$

Beweis: Für die allererste Gleichheit beweise man mit der Formel von Binet zunächst: F_n³=(F_3n-3·(-1)ⁿ F_n)/5. Für die anderen Gleichungen und ähnliche Formeln s. [Clary].

Die Formel von Binet gibt uns genau an, wie schnell die Fibonacci-Zahlen wachsen:

1.3.12 Korollar: Für n>1 ist F_n diejenige natürliche Zahl, die am nächsten bei ( $\frac{1+\sqrt{5}}{2}$ )ⁿ liegt.

Beweis: Die Zahl $\frac{1-\sqrt{5}}{2}$ ist vom Betrag her kleiner als 1. Geteilt durch sqrt(5) ist sie vom Betrag her kleiner als 1/2.

Ganz ähnlich ist die n. Tribonacci-Zahl (s. 1.1.2. (2)) diejenige natürliche Zahl, die am nächsten bei

$\frac{\rho-1}{4\rho-6}\rho^{n-1} mit \rho=\frac{1}{3}(\sqrt[3]{19+3\sqrt{33}}+\sqrt[3]{19-3\sqrt{33}}+1)$

liegt ([Spickerman]).

Fibonacci-Zahlen mit Matrix-Subskript

Die Formel von Binet

$F_n=\frac{\zeta^n-\eta^n}{\sqrt{5}}$

erlaubt es einem ohne Probleme, Fibonacci-Zahlen mit reellem Index (n in IR) zu definieren. Ebenso kann man F_A definieren, wobei A eine (reelle oder komplexe) quadratische Matrix ist. Hierbei soll für x in IR (C) gelten:

$x^A:=e^{A\ln x}=\sum_{k=0}^\infty\frac{(\ln x)^k A^k}{k!},$

wobei ln(x) der Hauptwert des Logarithmus sein soll. Es gelten dann viele Formeln ähnlich zu denen, die wir schon hatten. Bezeichnet I die Einheitsmatrix, so gilt z.B.

F_A+I=F_A-F_A-I, F_A+IF_A-I-F_A²=(-1)^A

1.3.13 Beispiel: $A=\pmatrix{0&1 \cr 0&0}\qquad\Rightarrow\qquadF_A=\pmatrix{0 & \frac{1}{\sqrt{5}}(2\ln\frac{1+\sqrt{5}}{2}-i\pi)\cr 0&0}.$

Es gelten dann solche Sätze wie:

1.3.14 Proposition: Ist A eine diagonalisierbare quadratische (reelle oder komplexe) Matrix, so gilt:

Alle Eigenwerte kommen aus {0,1,5} <=> F_A=A.

1.3.15 Problem

Gegeben sei eine Matrix A. Wir setzen

f₀:=A, f₁:=A, f₂:=F_{f_1}, f₃:=F_{f_2}, ...

Unter welchen Vorraussetzungen konvergiert die Folge (f_i) (i in IN)?

Literatur ist [Brugia].

1.4 Fibonacci-Zahlen und Binomial-Koeffizienten

1.4.16 Satz: Es gilt:

$F_{n+1}=\sum_{k=0}^{[\frac{n-1}{2}]}{n-k\choose k}.$

Die Summe läuft also über alle k, für die ${n-k\choose k}\ne 0$ ist.

Beweis: Folgt sofort via Induktion aus ${n\choose k}={n-1\choose k}+{n-1\choose k-1}$ .

1.4.17 Satz: Für n,i in IN₀ gilt:

$\sum_{k=0}^n{n\choose k}F_{k+i}=F_{2n+i}.$

Beweis: Setzt man $\zeta=\frac{1+\sqrt{5}}{2}$ und $\eta=\frac{1-\sqrt{5}}{2}$ , so bekommt man nach der Formel von Binet (1.3.9.):

$\sum_{k=0}^n{n\choose k}F_{k+i} = ... \frac{1}{\sqrt{5}}(\zeta^{i+2n}-\eta^{i+2n}).$

Mit etwas mehr Mühe kann man aus der Formel von Binet eine ganze Menge ähnlicher Formeln herausholen. Einige Beispiele:

1.4.18 Weitere Summenformeln: Für n,i in IN₀ gilt:

Beweis: Für die ersten beiden Formeln s. [Hoggat1]. (3) bis (5) stammen aus [Long1]. Dieser Artikel enthält noch eine Vielzahl weiterer Formeln.

Auf völlig anderem Weg, nämlich durch Betrachtung der "Diagonalfunktionen dritter Ordnung von Pell-Polynomen" erhält man dagegen folgende Formeln:

1.4.19 Noch mehr Formeln: Für n in IN (n>0) gilt:

Beweis: Für die Beweise und noch viele weitere Formeln s. [Mahon].

Mit derselben Methode wurde übrigens auch die Formel 1.6.25. bewiesen.

1.5 Grenzwerte mit Fibonacci-Zahlen

1.5.20 Die erzeugende Funktion: Für $\vert x\vert <\frac{\sqrt{5}-1}{2}$ gilt:

$\sum_{k=0}^\infty F_kx^k=\frac{x}{1-x-x^2} .$

Beweis

Zunächst einmal ist wegen F_n<=2F_n-1: F_n<=2ⁿ. Die Reihe hat also einen positiven Konvergenzradius. Wir dürfen sie manipulieren:

$\sum_{k=0}^\infty F_kx^k=x+\sum_{k=2}^\infty(F_{k-1}+F_{k-2})x^k= x+x^2\sum_{k=0}^\infty F_kx^k+x\sum_{k=0}^\infty F_kx^k.$

Daraus folgt die Behauptung.

Daß die Reihe für $\vert x\vert <\frac{\sqrt{5}-1}{2}$ konvergiert, sieht man durch Berechnung der Nullstelle von 1-x-x², oder einfach mit der Formeln von Binet (1.3.9.).

1.5.21 Kettenbrüche: Der n. Näherungsbruch des Kettenbruches

$1+\frac{1}{\displaystyle 1+\frac{1}{1+\frac{1}{1+\ldots}}}$

ist genau F_n+1/F_n.

Beweis: Folgt sofort via Induktion.

Insbesondere sieht man, daß der Grenzwert des Kettenbruchs genau

$\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\frac{1+\sqrt{5}}{2}$

ist. (Vergl. Formel von Binet (1.3.9.).)

1.5.22 Weitere Formeln: Es gilt:

$9=\sqrt{3F_2F_4+F_4\sqrt{3F_4F_6+F_6\sqrt{3F_6F_8+\ldots}}}.$

Beweis: s. [Makarov].

1.6 Die Inversen der Fibonacci-Zahlen

Formeln, in denen nicht die Fibonacci-Zahlen, sondern ihre Inversen auftauchen, sind deutlich seltener. Nur selten sind sie so einfach zu beweisen, wie die folgende kleine Kuriosität:

1.6.23 Proposition: Für n in IN (n>0) gilt:

$\arctan\frac{1}{F_{2n}}= \arctan\frac{1}{F_{2n+1}}+\arctan\frac{1}{F_{2n+2}}$

und

$artanh \frac{1}{F_{2n+1}}= artanh\frac{1}{F_{2n+2}}+artanh\frac{1}{F_{2n+3}}.$

Beweis: Mit Hilfe der Deteminanten-Identität 1.2.3. rechnet man sofort nach, daß F_n-1(F_n+F_n+1)-F_nF_n+1= (-1)ⁿ. Der Rest folgt dann aus der Additionsformel für die inversen Winkelfunktionen, wie z.B.

$\arctan x+\arctan y =\arctan \frac{x+y}{1-xy}.$

Die Umkehrung gilt (fast) auch: Sind für eine Folge die obigen zwei Formeln erfüllt, und noch ein paar andere Vorraussetzungen erfüllt, so ist die Folge durch eine einfache lineare Rekursionsformel entstanden (s. [Imada]).

1.6.24 Korollar: $\sum_{n=0}^\infty\arctan\frac{1}{F_{2n+1}}=\frac{\pi}{2} ... \sum{n=1}^\infty artanh\frac{1}{F_{2n+2}}=\frac{1}{2}\ln 3.$

(Man beachte, daß artanh(1/F₂) noch nicht definiert ist.)

Beweis: Beide Summen sind nach 1.6.23. in Wirklichkeit Teleskopsummen.

Nichttrivial dagegen ist:

1.6.25 Proposition: Für n in IN (n>0) gilt:

$\sum_{k=1}^n\frac{F_k+(-1)^k}{(F_{k+2}-1)(F_{k+3}-1)} = 2-\frac{F_{n+4}-1}{F_{n+3}-1}.$

Beweis: s. [Mahon]. Man kann dies vermutlich aber auch durch Induktion nachrechnen.

1.6.26 Eine kuriose Eigenschaft von F₁₁

Es ist

$\frac{1}{F_{11}}=\frac{1}{89}=0,01123595\ldots$

Die Dezimalbruchentwicklung von 1/F₁₁ fängt also genau mit den Fibonacci-Zahlen an. Das ist kein Zufall, denn wegen der Formel 1.5.20. ist

$\sum_{k=0}^\infty \frac{F_k}{10^{k+1}}=\frac{1}{89}.$

Man kann sich fragen, ob es noch andere Lösungen der diophantischen Gleichung

$\frac{1}{F_n}=\sum_{k=0}^\infty\frac{F_k}{m^{k+1}}$

(also mit m,n in IN) gibt. In [Weger] wird gezeigt, daß die einzigen Lösungen, abgesehen von der obigen (n=11, m=10) die folgenden sind:

Dies zu zeigen, ist allerdings nicht besonders einfach.