4 Der Satz von Zeckendorf

4.1 Der Satz

Jede natürliche Zahl läßt sich eindeutig als Summe von Zweierpotenzen schreiben, wobei jede Zweierpotenz höchstens einmal vorkommen darf. Allgemein kann man sich fragen, ob man, wenn man eine (streng) monoton steigende Folge (an) (n in IN) gegeben hat, jede natürliche Zahl als Summe der an schreiben kann, und in wiefern eine solche Darstellung eindeutig ist.

Damit für jede Zahl eine solche Darstellung existiert, muß sicherlich a1+...+an-1>=an-1 sein. Diese Bedingung ist für die Fibonacci-Zahlen erfüllt (s. 1.2.5.).

Um eine Eindeutigkeit zu bekommen, muß genau die umgekehrte Ungleichung erfüllt sein: a1+...+an-1<=an-1. Dies ist also für die Fibonacci-Zahlen nicht erfüllt. Es gilt aber:

4.1.1 Satz (von Zeckendorf)
Jede natürliche Zahl N läßt sich eindeutig schreiben als

N=F_{n_1}+F_{n_2}+...+F_{n_k}  mit 2\le n_1\le n_2-2,
n_2\le n_3-2,..., n_{k-1}\le n_k-2.

In der Summe dürfen also weder F0, noch F1, noch zwei aufeinanderfolgende Fibonacci-Zahlen vorkommen.

Beweis:

Für n=1,2,3,4 rechnet man das einfach nach.

Nun sei die Behauptung bereits bewiesen für N<Fn, und es sei Fn<=N<Fn+1. Es ist dann N-Fn<Fn+1-Fn=Fn-1. Also läßt sich N-Fn nach Induktionsvorraussetzung als solche Summe schreiben, und außerdem kommt in dieser Summe Fn-1 als Summand nicht vor. Addiert man noch Fn dazu, so bekommt man die Existenz einer Summendarstellung wie behauptet.

Umgekehrt muß in jeder solchen Darstellung von N auch der Summand Fn vorkommen, denn die größte Summe, die sich mit F2,...,Fn-1 bilden läßt, ist Fn-1+Fn-3+Fn-5+... Und diese ist <=Fn-1 (s. die zweite und dritte Formel in 1.2.5. und beachte, daß F1=1 nicht auftreten darf). Aus der Eindeutigkeit der Darstellung von N-Fn folgt dann die Eindeutigkeit derjenigen von N.

4.1.2 Beispiel:

Für n,k in IN ist Fkn/Fn eine natürliche Zahl (s. 2.1.2.). Für diese können wir die Zeckendorf-Darstellung explizit hinschreiben. Für n>=2 ist

komplizierte Summenformeln mit Fallunterscheidung.

Für n=2 (F2=1) reduziert sich die erste Formel natürgemäß auf F2k.

Beweis:
[Filipponi]

4.2 Zeckendorf- oder Fibonacci-Sequenzen

Man kann den Satz von Zeckendorf auch anders sehen:

4.2.3 Definition:
Eine "Zeckendorf-Sequenz" ist eine (endliche Sequenz)
x1, x2,..., xk    mit    xi in {0,1}  und  xi·xi+1=0   und   xk=1.

(Also eine endliche Sequenz aus Nullen und Einsen, in der nie zwei Einsen hintereinander vorkommen, und die mit 1 endet.)

k heißt "die Länge" der Zeckendorf-Sequenz.

Der Satz von Zeckendorf läßt sich dann wie folgt formulieren:

4.2.4 Satz (von Zeckendorf)':

Es gibt eine bijektive Abbildung zwischen der Menge der Zeckendorf-Sequenzen und den natürlichen Zahlen, und zwar

x_1,\ldots,x_k)\mapsto\sum_{i=1}^k x_iF_{i+1}.

4.2.5 Korollar:
Die Anzahl der Zeckendorf-Sequenzen der Länge <=n ist genau Fn+2.
Beweis:

Aus dem Beweis zum Satz von Zeckendorf (4.1.1.) wissen wir, daß man genau alle Zahlen <Fn+2 (einschließlich der Null) mit Hilfe von F2,...,Fn+1 darstellen kann. Dies entspricht genau der Behauptung.

Man kann die Behauptung übrigens auch ganz leicht direkt durch Induktion zeigen.

4.2.6 Fibonacci-Zahlen von Graphen

Eine Teilmenge I von Knoten eines Graphen G heißt "unabhängig", falls keine zwei Knoten aus I durch eine Kante verbunden sind.

Der Graph, der aus n Knoten x1,...,xn besteht, wobei jede xi und xi+1 (i=1,...n-1) durch eine Kante verbunden sind (s. Bild für n=7), hat also genau Fn+2 verschiedene unabhängige Mengen von Knoten, denn jede solche Menge entspricht genau einer Zeckendorf-Sequenz.

o----o----o----o----o----o----o

Ist G nun ein beliebiger Graph, so sei die "Fibonacci-Zahl von G" F(G) die Anzahl der unabhängigen Knotenmengen von G. Für nähere Informationen s. [Prodinger] und [Drmota].

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