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 (a_n) (n in IN) gegeben hat, jede natürliche Zahl als Summe der a_n schreiben kann, und in wiefern eine solche Darstellung eindeutig ist.

Damit für jede Zahl eine solche Darstellung existiert, muß sicherlich a₁+...+a_n-1>=a_n-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: a₁+...+a_n-1<=a_n-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 F₀, noch F₁, 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<F_n, und es sei F_n<=N<F_n+1. Es ist dann N-F_n<F_n+1-F_n=F_n-1. Also läßt sich N-F_n nach Induktionsvorraussetzung als solche Summe schreiben, und außerdem kommt in dieser Summe F_n-1 als Summand nicht vor. Addiert man noch F_n dazu, so bekommt man die Existenz einer Summendarstellung wie behauptet.

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

4.1.2 Beispiel:

Für n,k in IN ist F_kn/F_n 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 (F₂=1) reduziert sich die erste Formel natürgemäß auf F_2k.

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)

x₁, x₂,..., x_k mit x_i in {0,1} und x_i·x_i+1=0 und x_k=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 F_n+2.

Beweis:

Aus dem Beweis zum Satz von Zeckendorf (4.1.1.) wissen wir, daß man genau alle Zahlen <F_n+2 (einschließlich der Null) mit Hilfe von F₂,...,F_n+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 x₁,...,x_n besteht, wobei jede x_i und x_i+1 (i=1,...n-1) durch eine Kante verbunden sind (s. Bild für n=7), hat also genau F_n+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].