2 Zahlentheoretische Eigenschaften der Fibonacci-Zahlen

Bei einer Folge von natürlichen Zaheln interessiert man sich natürlich für die Primzahlzerlegungen. Also z.B.: Gibt es unter den Fibonacci-Zahlen unendlich viele Primzahlen? Kann man etwas über die Anzahl der Primteiler aussagen. Befinden sich Quadratzahlen, andere Potenzen etc. darunter?

2.1 Der ggT von Fibonacci-Zahlen

Ab jetzt bezeichne ggT(a,b) den größten gemeinsamen Teiler der Zahlen a und b, und kgV(a,b) ihren kleinsten gemeinsamen Vielfach. a|b bedeute, daß a ein Teiler von b ist ("a teilt b"). (Achtung: Der Vertikale Strich ist in der Browser-Darstellung häufig schlecht zu erkennen.)

Wie sieht ggT(F_n, F_m) aus? Die Antwort ist überraschend einfach:

2.1.1 Satz:: Für m,n in IN ist:

ggT(F_n, F_m)=F_ggT(m,n).

Beweis:

Zunächst zeigen, wir, daß F_n|F_kn (für k>0). Und zwar geht dies einfach durch Induktion über k. k=1 ist klar. Und nach der Additionsformel 1.2.4. ist

F_(k+1)n=F_kn-1F_n+F_knF_n+1.

Nach Induktionsvorraussetzung ist dann F_n ein Teiler von F_kn.

Nun sei an den euklidischen Algorithmus erinnert. Den ggT(m,n) bekommt man wie folgt: Ist (oBdA) m>=n, so schreibt man

m	=	q₀n	+r₁	mit r₁<n
n	=	q₁r₁	+r₂	mit r₂<r₁
r₁	=	q₂r₂	+r₃	mit r₃<r₂
	...
r_k-1	=	q_kr_k

r_k ist dann der ggT von m und n. Genauer gesagt ist

ggT(m,n)=ggT(n,r₁)=ggT(r₁,r₂)= ggT(r₂,r₃)=...

Wendet man den euklidischen Algorithmus auf F_n und F_n-1 an, so ist stets q_i=1 und die r_i durchlaufen die Fibonacci-Zahlen nach unten: F_n und F_n-1 sind teilerfremd. Insbesondere sind dann auch F_n und F_kn-1 teilerfremd.

Sind nun r_i und q_iwie oben, so ist:

Auf diese Weise macht man weiter:

ggT(F_m,F_n)= ggT(F_n,F_{r_1})= ggT(F_{r_1},F_{r_2})=...

Am Ende erhält man: ggT(F_m,F_n)=F_{r_k}= F_ggT(m,n).

Wir halten außerdem fest:

2.1.2 Korollar:

Es gilt:

(1): n|m => F_n|F_m.
(2): F_n und F_n-1 sind teilerfremd.

Die Umkehrung von (1) gilt nicht, da F₂=1 ist. So ist F₂ ein Teiler von F₃, obwohl 2 kein Teiler von 3 ist. Abgesehen von diesem Unfall mit der 2 gilt aber auch die Umkehrung.

2.1.3 Korollar:

(1): F_n ist gerade => 3|n
(2): 3|F_n => 4|n
(3): 4|F_n => 6|n
(4): 5|F_n => 5|n
(5): 7|F_n => 8|n

2.1.4 Korollar:: Ist F_n eine Primzahl, so ist n=4, oder n ist selber eine Primzahl.

Die Umkehrung gilt nicht: 19 ist eine Primzahl, aber F₁₉=4181=37·113 ist keine. Die Frage, ob unter den Fibonacci-Zahlen endlich oder unendlich viele Primzahlen sind, ist ungelöst.

2.1.5 Korollar:: Ist ggT(m,n)=1, so gilt: F_n·F_m|F_mn.

2.2 Die Fibonacci-Folge modulo n

Die Periode der Fibonacci-Folge modulo n

Gibt es zu jeder Zahl n eine Fibonacci-Zahl F_k mit n|F_k? Die Antwort ist "Ja!". Um dies zu sehen, betrachten wir die Folge F_k mod n. Die Frage ist also, ob es außer k=0 noch ein anderes k mit F_k=0 mod n gibt.

2.2.6 Satz und Definition:

Die Fibonacci-Folge modulo n (F_k mod n) ist periodisch. Die Periode ist <=n².

Ab jetzt bezeichne $\lambda(n)$ die Periode der Fibonacci-Folge modulo n. $\lambda(n)$ heißt auch manchmal "Wall-Zahl" (nach D.D. Wall; s. [Wall]).

Beweis:: Zunächst beachte man, daß die Fibonacci-Folge durch jedes Paar (F_n,F_n+1) eindeutig festgelegt ist. Nun gibt es aber nur n² Möglichkeiten für (F_n,F_n+1) Daraus folgt die Behauptung.

Wegen F₀=0 mod n gibt es unendlich viele k mit F_k=0 mod n.

Die Perioden kann man auch so sehen: Man betrachtet die Matrizen $\pmatrix{1 & 1\cr 1 & 0}$ in Z/nZ. Da die ersten beiden Vektoren (1,0) und (0,1) linear unabhängig sind, ist $\lambda(n)$ genau die kleinste Zahl >1, für die gilt:

$\pmatrix{1 & 1\cr 1 & 0}^{\lambda(n)}= \pmatrix{1 & 0 \cr 0 & 1}.$

Was kann man über die Perioden $\lambda(n)$ sonst noch aussagen? In diesem Kapitel werden wir uns mit den Perioden beschäftigen, für den Fall, daß n eine zusammengesetzte Zahl ist.

2.2.7 Lemma:: Es seien m,n>1, dann gilt:

m|n => $\lambda(m)$ | $\lambda(n)$ .

Beweis:: Folgt sofort aus der Definition des $\lambda(n)$ mit den Matrizen.

2.2.8 Lemma:: Sind m und n teilerfremd, so gilt:

$\lambda(mn)$ = kgV( $\lambda(m)$ , $\lambda(n)$ ).

Beweis:

Nach obigem Lemma 2.2.7. gilt kgV( $\lambda(m)$ , $\lambda(n)$ )| $\lambda(mn)$

Umgekehrt ist $F_{{\rm kgV}(\lambda(m),\lambda(n))}$ =0 mod m und auch mod n. Und ebenso $F_{{\rmkgV}(\lambda(m),\lambda(n))+1}$ =1 mod m und auch mod n. Nach dem chinesischen Restsatz (Referenz?) gibt es aber, da m und n teilerfremd sind, in Z/nmZ nur genau eine Restklasse [x]=0 mod m und mod n, und genau eine =1 m und mod n. $F_{{\rm kgV}(\lambda(m),\lambda(n))}$ und $F_{{\rm kgV}(\lambda(m),\lambda(n))+1}$ müssen diese beiden Restklassen sein. Es gilt also sogar:

$F_{{\rm kgV}(\lambda(m),\lambda(n))}$ =0 mod mn und $F_{{\rm kgV}(\lambda(m),\lambda(n))+1}$ =1 mod mn

Dies bedeutet: $\lambda(mn)$ |kgV( $\lambda(m)$ , $\lambda(n)$ ).

2.2.9 Lemma:: p sei eine Primzahl, und k>1, dann gilt entweder

$\lambda(p^k)=\lambda(p^{k-1}) oder \lambda(p^k)=p\lambda(p^{k-1}).$

Beweis:

Wir rechnen hier, ohne es dazuzuschreiben, modulo p^k. Nach Definition ist

$\pmatrix{1 & 1 \cr 1 & 0}^{\lambda(p^{k-1})}\pmatrix{1\cr 0}= p^{k-1}\pmatrix{a\cr b}+\pmatrix{1\cr 0}$

mit a,b in {0,1,...,p-1}. Ist a=b=0, so ist $\lambda(p^k)=\lambda{p^{k-1}}$ und wir sind fertig. Ansonsten zeigt man durch wiederholtes Multiplizieren mit $\pmatrix{1 & 1\cr 1 & 0}^{\lambda{p^{k-1}}}$ für l in IN:

$\pmatrix{1 & 1 \cr 1 & 0}^{l\lambda(p^{k-1})}\pmatrix{1\cr 0}= lp^{k-1}\pmatrix{a\cr b}+\pmatrix{1\cr 0}.$

Die Frage ist nun, für welches l der erste Summand zum ersten mal verschwindet. Wenn nicht a=b=0 ist, so ist dies, da p eine Primzahl ist, zum ersten genau mal für l=p der Fall.

Eine etwas genauere Analyse zeigt, daß gilt:

$\lambda(p^k)=p\lambda(p^{k-1}) => \forall l \ge k: \lambda(p^l)=p\lambda(p^{l-1}).$

Außerdem ist klar, daß es mindestens ein k gibt, für das dies gilt. Man vermutet, daß dies für alle k in IN gilt:

$\lambda(p^k)=p^{k-1}\lambda(p).$

Dies ist allerdings bis heute nicht bewiesen.

Mit Hilfe dieser drei Lemmas können wir, wenn wir mal von der eben angesprochenen ungelösten Frage absehen, $\lambda(n)$ in Termen der lambda der Primfaktoren von n ausrechnen. Im nächsten Abschnitt werden wir uns der ungleich schwierigeren Frage zuwenden, wie die Perioden $\lambda(p)$ für Primzahlen p aussehen.

Die Periode der Fibonacci-Folge modulo p

Bevor wir anfangen, ein Lemma:

2.2.10 Lemma:: Ist p eine Primzahl, so gilt:

$5^{\frac{p-1}{2}}=\cases{+1 mod p & falls $p=\pm 1 ,mod 5$,\cr -1 mod p & falls $p=\pm 2 mod 5$.}$

Beweis:

Man sehe in einem Buch für Zahlentheorie (Referenz?) nach, wie man mit den Legendre-Symbolen $\left(\frac{p}{q}\right)$ rechnet. Und zwar gilt:

$\left(\frac{p}{q}\right)\cdot\left(\frac{q}{p}\right)= (-1)^{\frac{p-1}{2}\frac{q-1}{2}}.$

Für q=5 ergibt sich letztendlich:

$\left(\frac{5}{p}\right)}={\left(\... ...$p=\pm 1{\rm\,mod\,}5$,\cr -1 & falls $p=\pm 2{\rm\,mod\,}5$.}$

Denn ±1 sind quadratische Reste modulo 5 und ±2 sind keine quadratischen Reste. Außerdem beachte man 5^p-1=1 mod p (kleiner Satz von Fermat).

2.2.11 Satz:

p sei eine Primzahl. Dann kann man die Werte von F_p-1, F_p, F_p+1 in folgender Tabelle ablesen.

	F_p-1 mod p	F_p mod p	F_p+1 mod p
p=2	1	1	0
p=5	3	0	3
p=±1 mod 5	0	1	1
p=±2 mod 5	1	-1	0

Beweis:

Der Beweis erfolgt durch nachrechnen: Man multipliziere die Formel von Binet (1.3.9.) für n=p und n=p+1 mit Hilfe des Binomialgesetzes aus. Alle Terme mit sqrt(5) müssen sich gegenseitig wegheben.

Da p eine Primzahl ist, sind fast alle Binomialkoeffizienten, wenn man modulo p rechnet, Null. Man bekommt auf diese Weise Ausdrücke mit $5^{\frac{p-1}{2}}$ . F_p-1 kann man dann aus F_p und F_p+1 ausrechnen.

Als Korollar erhalten wir:

2.2.12 Satz:

Es sei p verschieden von 2 und 5, dann gilt:

p=±1 mod 5	=>	$\lambda(p)$ \|(p-1)
p=±2 mod 5	=>	$\lambda(p)$ \|2(p+1)

Im zweiten Fall kann $\lambda(p)$ nicht schon ein Teiler von p+1 sein.

Außerdem ist $\lambda$ (2)=3 und $\lambda$ (5)=20.

Beweis:: Kann man sofort aus der Tabelle in 2.2.11. ablesen. Für p=5 muß man das halt nachrechnen.

Weitere Resultate zu bekommen, ist ziemlich schwierig. In [Götsch] wird gezeigt:

2.2.13 Satz:: Es gilt:

Außerdem gilt:

Die Verteilung der Fibonacci-Zahlen modulo n

Tauchen in der Fibonacci-Folge F_k mod n alle Zahlen 0,...,n-1 gleichoft auf? In diesem Abschnitt werden wir die Frage beantworten. Die Frage läßt sich auch ganz allgemein für Folgen definieren:

2.2.14 Definition:

(a_k)_{k in IN} sei eine Folge ganzer Zahlen, n in IN und A_N(j) sei die Anzahl der Folgenglieder a_k mit k<=N und a_k=j mod n.

Dann heißt die Folge (a_k) "uniform verteilt modulo n", falls für alle j=0,...,n-1 gilt:

$lim_{N\to\infty}\frac{A_N(j)}{N}=\frac{1}{n}.$

Im Falle der Fibonacci-Zahlen ist dies relativ einfach nachzuprüfen, da sie periodisch modulo n sind. Sie sind uniform verteilt, falls innerhalb einer Periode alle Zahlen 0,...,n-1 gleichoft vorkommen.

2.2.15 Satz:: Die Fibonacci-Zahlen sind genau dann uniform verteilt modulo n, falls n eine 5er-Potenz ist: n=5^k.

Beweis:

Wir zeigen nur die eine Richtung.

n enthalte einen Primfaktor p verschieden von 5, und wir nehmen an, F_n ist uniform verteilt modulo n. j sei die Anzahl der durch p teilbaren Fibonacci-Zahlen mit Index y< $\lambda(p)$ . Wegen $\lambda(p)$ | $\lambda(n)$ ist die Anzahl der durch p teilbaren Fibonacci-Zahlen mit Index y $\lambda(n)$ dann genau

$k\frac{\lambda(n)}{\lambda(p)}=\frac{\lambda(n)}{p}.$

Also: kp= $\lambda(p)$ . Wir wissen aber (Satz 2.2.12.), daß das für p verschieden von 5 nicht sein kann.

Für den Beweis, daß F_n uniform verteilt modulo 5^k ist, s. [Kuipers] und [Niederreiter].

Summen von Fibonacci-Zahlen modulo n

In diesem Abschnitt werden wir die Summen von Fibonacci-Zahlen modulo n ausrechnen, wobei die Summe genau über eine Periode genommen wird. Zwar können wir solche Summen sogar in Z ausrechnen (s. 1.2.5., 1.2.6. und 1.3.11.), aber hier wird alles noch einfacher, weil wir eine Translationsinvarianz haben:

$\sum_{k=0}^{\lambda(n)-1}F_k= \sum_{k=N}^{N+\lambda(n)-1}F_k\quad({\rm\,mod\,}n).$

Die Ergebnisse sind wie folgt:

2.2.16 Satz:

Es sei n in IN. Werden die folgenden Summen genau über eine Periode und modulo n ausgerechnet, so gilt:

viele komische Summenformeln

In den Fällen (d), (g), (l) sei dabei n eine Primzahl verschieden von 5, im Fall (h) eine Primzahl verschieden von 3, im Fall (i) und (j) eine Primzahl verschieden von 11. Für welche Zahlen (k) (und damit (l)) gilt, ist nicht nicht klar.

Beweis:

Wir zeigen nicht alles.

(a) ist einfach: $\sum F_k=\sum(F_{k-1}+F_{k-2})=2\sum F_k$ .

Für (b) beobachte, daß F_k mit Hilfe seiner Rekursionsformel auch für k<0 definiert ist, und (modulo n) auch dort periodisch ist. Und zwar sieht man schnell, daß F_-k=F_k(-1)^k+1. Daraus folgt (b).

Für (c) rechnen wir:

$\sum F_k^2=\sum (F_{k-1}+F_{k-2})^2=2\sum F_k^2+2\sum F_kF_{k-1},$

und ebenso

$\sum F_k^2=\sum F_{k-2}^2= \sum (F_k-F_{k-1})^2=2\sum F_k^2-2\sum F_kF_{k-1}.$

Addition ergibt die Behauptung.

(e) beweist man so ähnlich, nur ein wenig komplizierter, wie (c). Und (f) folgt aus (e) genau wie (b) aus (a).

Für (d), (g) und (l) s. [Aydin1]. (h), (i), (j) und (k) gehen so ähnlich wie (e) und (c) nur sehr viel komplizierter; s. [Aydin2].

2.3 Primitive Teiler

Wir haben schon gesehen, daß es zu jeder Zahl n eine Fibonacci-Zahl gibt, die durch n teilbar ist, nämlich $F_{\lambda(n)}$ . Es wird aber im Allgemeinen durchaus schon eine kleinere Fibonacci-Zahl durch n teilbar sein.

2.3.17 Definition:

n heißt "primitiver Teiler" von F_k, falls gilt:

(a): n|F_k
(b): Für j<k gilt: n teilt nicht F_j.

Ist p eine Primzahl und ein primitiver Teiler von F_k, so heißt sie "primitiver Primteiler". Die höchste Potenz von p, die F_k in diesem Fall teilt, heißt "primitive Primteilerpotenz" ("ppp") p^e.

Außerdem definieren wir gleich das Produkt aller solchen primitiven Primteilerpotenzen:

$P(F_k):=\prod\limits_{p^e\mbox{ \scriptsize ppp}}p^e.$

Hat F_k keine primitiven Primteiler, so sei P(F_k):=1.

Man beachte, daß, wenn p^e ein primitiver Teiler F_k ist, p^e noch lange keine primitive Primteilerpotenz sein muß, denn p muß kein primitiver Primteiler sein.

Natürlich hat jede Fibonacci-Zahl mindestens einen primitiven Teiler, nämlich sich selbst. Aber hat jede Fibonacci-Zahl einen primitiven Primteiler? Die Antwort ist natürlich "Nein", denn F₆=8, aber bereits F₃=2 ist durch 2 teilbar.

Es stellt sich aber heraus, daß alle Fibonacci-Zahlen bis auf endlich viele primitive Primteiler haben. Und zwar gilt:

2.3.18 Satz:: $\sum\limits_{k\le x}\ln P(F_k)= \frac{3}{\pi^2}\ln({\textstyle\frac{1+\sqrt{5}}{2}})\cdot x^2+O(x\ln x).$

Beweis:: Der Beweis ist, wie der Leser sich denken kann, nicht elementar. Er findet sich in [Kiss], und benutzt diverse zahlentheoretische Funktionen wie z.B. die Möbius-Funktion.

Sonderlich überraschend ist dies allerdings nicht, da die Fibonacci-Zahlen ja viel schneller wachsen, als die Primzahlen. Überraschend ist eher, daß man so etwas beweisen kann.

2.3.19 Korollar:: Es gibt ein N in IN, so daß für alle k>=N die Fibonacci-Zahl F_k primitive Primteiler hat.

Die rechte Seite obiger Formel hat folgende Bedeutung: Ist wieder $\zeta=\frac{1+\sqrt{5}}{2}$ und $\eta=\frac{1-\sqrt{5}}{2}$ , so ist nach der Formel von Binet 1.3.9.:

$\ln\prod_{k=1}^x F_k\sim\ln\prod_{k=1}^x\zeta^k \sim\frac{x^2}{2}\ln\frac{1+\sqrt{5}}{2}.$

Aus diesem Grund ist folgende Formel stark verwandt mit obiger (man kann glaube ich zeigen, daß sie sogar daraus folgt):

2.3.20 Satz:: $\lim_{x\to\infty} \frac{\ln(F_1\cdot\ldots\cdot F_x)}{\ln{\rm kgV}(F_1,\ldots, F_x)} = \frac{\pi^2}{6}.$

Beweis:: s. [Matiyasevich].

2.4 Fibonomial-Koeffizienten

Definition

2.4.21 Definition:: Ist (a_n) (n in IN) eine Folge reeller Zahlen verschieden von 0, so definieren wir

$[n]!_{(a_n)}:=a_1\cdot a_2\cdot\ldots\cdot a_n und ...ray}\right]_{(a_n)}:=\frac{[n]!_{a_n}}{[k]!_{a_n}[n-k]!_{a_n}}.$

Ist klar, welche Folge (a_n) gemeint ist, so lassen wir den Index weg. Insbesondere ergeben sich für a_n=n die (normalen) Binomial-Koeffizienten. Für a_n=F_n ergeben sich die "Fibonomial-Koeffizienten". Im folgenden betrachten wir nur diese.

Auf analoge Weise kann man auch verallgemeinerte Multinomial-Koeffizienten definieren.

Die Fibonomial-Koeffizienten sind bisher lediglich rationale Zahlen. Wir wollen natürlich als erstes wissen, ob sie auch ganz sind. Leider kann man das nicht so einfach zeigen, wie bei den Binomial-Koeffizienten, denn deren Rekursionsformel wird hier zu:

$Formeln wie bei Binomialkoeffizienten, aber mit Faktor \frac{F_n}{F_k+F_{n-k}}$

Und der Bruch F_n/(F_k+F_n-k) ist nicht immer ganzzahlig. Trotzdem gilt:

2.4.22 Proposition:: Die Fibonomial-Koeffizienten sind positive ganze Zahlen.

Beweis:

Und zwar folgt dies alleine z.B. aus der Eigenschaft F_ggT(m,n)=ggT(F_m,F_n) (s. [Ward]).

Es sei p eine Primzahl. Welche Potenz von p ist noch ein Teiler von [n]!? Ist s gegeben und $\rho_s$ die kleinste Zahl, für die $p^s\vert F_{\rho_s}$ , so sind alle Fibonacci-Zahlen, die durch p^s geteilt werden können von der Form $F_{k\rho_s}$ . Daraus folgt (nach einigem Nachdenken), daß die höchste Potenz von p, die noch ein Teiler von [n]! ist, gegeben ist durch

$\sum_{s=1}^\infty[\frac{n}{\rho_s}] wobei [.] die Gaußklammer ist.}$

Die Summe ist dabei in Wirklichkeit endlich. Da für beliebige natürliche Zahlen n,m, rho gilt:

$[\frac{n+m}{\rho}]\ge[\frac{n}{\rho}]+[\frac{m}{\rho}],$

folgt:

$\sum_{s=1}^\infty[\frac{n}{\rho_s}]\ge \sum_{s=1}^\infty[\frac{n-k}{\rho_s}]+ \sum_{s=1}^\infty[\frac{k}{\rho_s}].$

Im Zähler ist also eine mindestens so große Potenz von p enthalten wie im Nenner. Der Koeffizient ist ganz.

Stern-Konfigurationen mit ggT-Eigenschaft

Die Fibonomial-Koeffizienten kann man genau wie die Binomial-Koeffizienten in einer Art Pascalschem Dreieck anordnen. Wir betrachten zunächst sieben Fibonomial-Koeffizienten (oder Binomial-Koeffizienten) A,A₁,A₂,...,A₆, die im Dreieck wie folgt angeordnet sind:

A_6 A_5 oben, A_1 A A_4 darunter, A_2 A_3 darunter.

Diese Anordnung heißt "Hoggatt-Hansell-Hexagon" (engl. "Hoggatt-Hansell Perfect Square Hexagon") nach den beiden Mathematikern, die sie zuerst untersucht haben ([Hoggat2]).

Man sieht, indem man alle Produkte hinschreibt und wegkürzt, leicht daß:

2.4.23 Fakt:: A₁A₃A₅= A₂A₄A₆

Aber das ist nicht alles.

2.4.24 Proposition:: Es gilt:

ggT(A₁,A₃,A₅)= ggT(A₂,A₄,A₆).

Beweis:: s. [Hillman].

Wegen der Auswahl der je drei Punkte heißt dieser Satz auch manchmal "Davids-Stern-Theorem". Die entsprechende Gleichung für den kgV gilt dagegen nicht. Ersetzt man allerdings

$Der Fibonomial-K. [n k] bekommt einen Faktor F_{n+1} davor, der Binomial-K (n k) einen Faktor (n+1)$

so gilt die entsprechende Identität mit dem kgV, allerdings nicht mehr mit dem ggT. Die Produktidentität (2.4.23.) gilt ebenfalls noch. (Für einen Bew. s. [Ando1] oder [Sato].)

Man kann sich nun fragen, ob es noch andere Anordnungen gibt, die solche Eigenschaften haben. Die Antwort ist natürlich "Ja!", denn wegen solchen Formeln wie ggT(ggT(a,b),ggT(c,d))=ggT(a,b,c,d) kann man aus kleineren Anordnungen größere zusammenbasteln.

eine Stern-Anordnung

Diese Konfiguration nennt sich "Tokyo-Bogen". Sie besteht aus drei annähernd gestutzt kegelförmigen Anordnungen, die durch Drehungen ineinander übergehen. Diese Unterstrukturen heißen "Fujiyama", da sie an den gleichnamigen Berg in der Nähe von Tokyo erinnern sollen.

Es gilt:

2.4.25 Proposition:: $\{\bullet\}$ , $\{\circ\}$ und $\{\cdot\}$ bezeichnen die dem Tokyo-Bogen entsprechenden Zahlen im Pascalschen Dreieck aus Fibonomial-Koeffizienten (oder normalen Binomial-Koeffizienten). Dann gilt:

Beweis:: s. [Ando2].

Dort gibt es noch eine weitere (größere) Konfiguration namens "Julias Schneeflocke", und außerdem einen "Nordstern". Eine weitere Formation, ein größeres Hexagon, findet sich in [Long1].

2.5 Fibonacci-Zahlen als Quadrat- und Kubikzahlen

Gibt es unter den Fibonacci-Zahlen unendlich viele Quadratzahlen? Kubikzahlen? Solchen Fragen lassen sich beliebig abwandeln: Welche Fibonacci-Zahlen haben die Form px²±1, wo p eine Primzahl ist? Wieviele darunter haben einen geraden Index? Ich erwähne hier nur die zwei einfachsten Ergebnisse:

2.5.26 Satz:: Abgesehen von F₀=0 und F₁=F₂=1 ist F₁₂=144 die einzige Quadratzahl unter den Fibonacci-Zahlen. Weitere Kubikzahlen gibt es nicht.

Beweis:: Für die Quadratzahlen s. [Cohn], für die Kubikzahlen [Lagarias].

Einen Überblick über ähnliche Ergebnisse gibt [Robbins]. In [Luo] wird gezeigt, daß die einzigen Fibonacci-Zahlen, die Dreieckeszahlen, d.h. solche von der Form n(n+1)/2 sind, F₁=F₂=1 F₈=21 und F₁₀=55 sind.

2.6 Die Fibonacci-Zahlen als diophantische Menge

In der Theorie der diophantischen Gleichungen beschäftigt man sich mit der Frage, ob eine Gleichung der Form P(x₁,...,x_n)=0, wo P ein Polynom mit ganzzahligen Koeffizienten ist, Lösungen in den ganzen (oder natürlichen) Zahlen hat. Berühmtestes Beispiel ist sicherlich der Große Satz von Fermat. Die Frage nach der Lösbarkeit ist im allgemeinen sehr schwer zu beantworten.

Umgekehrt kann man sich auch fragen, ob es zu einer vorgegebenen Teilmenge A von IN ein Polynom P gibt, so daß die Elemente aus A genau die (ganzen oder natürlichen) Nullstellen von P sind. Etwas präziser definieren wir:

2.6.27 Definition:: Eine Teilmenge A von IN heißt "diophantisch", falls ein Polynom P in k+n Variablen mit ganzzahligen Koeffizienten existiert, so daß

$fuer (a_1,...,a_k)\in A^k existieren (x_1,...,x_n) in N^n mit P(a_1,...,a_k,x_1,...,x_n)=0.$

Interessant ist diese Eigenschaft natürlich nur für unendliche Mengen A.

2.6.28 Beispiel:: Die Menge der durch p teilbaren Zahlen ist diophantisch, sie ist nämlich genau gegeben durch

$\{a\in{I\!\!N}\mid \exists x\in{I\!\!N}: a-px=0\}.$

Wir werden in diesem Abschnitt die Frage behandeln, ob die Menge F der Fibonacci-Zahlen und ihr Komplement IN-F diophantisch sind. Und zwar betrachten wir das "Lucas-Polynom"

L(x,y) = x²-xy-y².

Nun gilt die dazu sehr ähnliche Identität F_n+1²-F_n-1F_n- F_n²=(-1)ⁿ. In [Jones1] wird gezeigt:

L(x,y)=1	<=>	y=F_2n	und	x=F_2n+1
L(x,y)=-1	<=>	y=F_2n-1	und	x=F_2n

Also:

$x\in F\quad\Leftrightarrow\exists y\in{I\!\!N}:\,L(y,x)\in\{\pm 1\}.$

Damit haben wir schon einmal das Polynom für die Fibonacci-Zahlen. Jede Nicht-Fibonacci-Zahl liegt zwischen zwei Fibonacci-Zahlen:

$z\not\in F\Leftrightarrow\exists x,y\in{I\!\!N}:\, L(y,x)\in\{\pm 1\}\mbox{ und }(x-z)(z-y)>0.$

Wir bekommen:

2.6.29 Proposition:: Die Mengen F und IN-F sind diophantisch. Und zwar gilt:

nach [Jones2].