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 Fn die Anzahl der Paare nach n Monaten, so sieht man sofort, daß

Fn+1=Fn+Fn-1    und    F0=1.

Wir dagegen definieren:

1.1.1. Definition
Die durch

F0=0,   F1=1    und    Fn+1=Fn+Fn-1

definierten Zahlen Fn (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
  1. Die durch L0:=2, L1:=1 und Ln+1:=Ln+Ln-1 definierten Zahlen heißen "Lucas-Zahlen". Zwischen den Fibonacci-Zahlen und den Lucas-Zahlen gibt es viele Zusammenhänge, wie z.B. L2n+2·(-1)n-1=5Fn2. Oft kann man Summen von Fibonacci-Zahlen elegant mit Lucas-Zahlen ausdrücken.

  2. Die durch F0:=0, F1:=1, F2:=2 (und F3:=4) und Fn+1=Fn+Fn-1+Fn-2(+Fn-3) definierte Folge heißt "Tribonacci-Folge" bzw. "Quadranacci-Folge". (Allgemein sind die Anfangswerte Fi=2i-1.)

  3. In der Rekursionsformel Fn+1=Fn+Fn-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 Fn(1) und Fn(2) definieren durch

    F0(i):=a,    F1(i):=b,   und    Fn+1(1):=Fn(1)Fn-1(1)    bzw.    Fn+1(2):=Fn-1(2)Fn(2)

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:

Fn-1Fn+1-Fn2=(-1)n

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:

Fn+m  =  Fn-1Fm +Fn Fm+1  =  Fn Fm-1+Fn+1Fm .

Insbesondere gilt:

F2n=Fn+12-Fn-12,     F2n+1=Fn2+Fn+12    und    F3n=Fn+13+Fn3-Fn-13.

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:

Fn-2Fn-1 Fn+1Fn+2 = Fn4-1    und     Fn+13-Fn-13 = F3n-Fn3.

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 ai=xi. Die Rekursionsformel ergibt dann für x die Gleichung

xk-ck-1xk-1-...-c1x-c0.

Sind x1 und x2 zwei Lösungen, so erfüllen alle Ausdrücke der Form l1x1+l2x2 ebenfalls die Rekursionsformel. Die Frage ist nun, ob man eine Linearkombination der Lösungen x0,...,xk-1 finden kann, die die Anfangswerte a0,...,ak-1 ergibt:

Gibt es    l0,...,lk-1    mit    ai=l0x0i+...+ lk-1xk-1i ?

Dies ist ein lineares Gleichungssystem in li wobei die Matrixeinträge xij sind. Sind die xi paarweise verschieden, so ist es lösbar (Vandermondersche Determinante).

Im Falle der Fibonacci-Zahlen ist das charakteristische Polynom

x2-x-1    und     x1,2= \frac{1\pm\sqrt{5}}{2}.

Folgerungen

Die Formel von Binet erlaubt uns, Summen wie F3+F6+F9+... als endliche geometrische Reihen aufzufassen und auszurechnen. Beispiele sind:

1.3.10 Summen von Fkn
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 Fn
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: Fn3=(F3n-3·(-1)n Fn)/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 Fn diejenige natürliche Zahl, die am nächsten bei ($\frac{1+\sqrt{5}}{2}$)n 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 FA 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.

FA+I=FA-FA-I,      FA+IFA-I-FA2=(-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}    <=>    FA=A.

1.3.15 Problem

Gegeben sei eine Matrix A. Wir setzen

f0:=A,    f1:=A,    f2:=Ff_1,   f3:=Ff_2,    ...

Unter welchen Vorraussetzungen konvergiert die Folge (fi) (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 IN0 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 IN0 gilt:

diverse Summenformeln

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:

zwei komplizierte Formeln

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 Fn<=2Fn-1:   Fn<=2n. 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-x2, 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 Fn+1/Fn.

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ß Fn-1(Fn+Fn+1)-FnFn+1= (-1)n. 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/F2) 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 F11
Es ist

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

Die Dezimalbruchentwicklung von 1/F11 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:

m=2 und n=1 oder 2; m=3 und n=5; m=8 und n=10

Dies zu zeigen, ist allerdings nicht besonders einfach.

by Michael Becker, 5/2003. Letzte Änderung: 5/2003.