Zeckendorf's theorem

From Wikipedia, the free encyclopedia

Zeckendorf's theorem, named after Belgian mathematician Edouard Zeckendorf, is a theorem about the representation of integers as sums of Fibonacci numbers.

Zeckendorf's theorem states that every positive integer can be represented in a unique way as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. A sum that meets these conditions is called a Zeckendorf representation.

This can be stated as,

$\forall N \in$ $\mathbb{N}\$ $N = \sum_{ i=0} ^k F_{c_i}$

where $F n$ is the n^th Fibonacci number and $c_i \ge c_{i-1} +2$ for $i=1 \dots k$ .

For example, the Zeckendorf representation of 100 is

100 = 89 + 8 + 3

There are other ways of representing 100 as the sum of Fibonacci numbers - for example

100 = 89 + 8 + 2 + 1

100 = 55 + 34 + 8 + 3

but these are not Zeckendorf representations because 1 and 2 are consecutive Fibonacci numbers, as are 34 and 55.

For any given positive integer, a representation that satisfies the conditions of Zeckendorf's theorem can be found by using a greedy algorithm, choosing the largest possible Fibonacci number at each stage. It is more difficult to show that this representation is unique i.e. it is the only representation that satisfies these conditions.

[edit] Fibonacci multiplication

One can define the following operation $a\circ b$ on natural numbers a, b: given the Zeckendorf representations $a=\sum_{i=0}^kF_{c_i}\;(c_i\ge2)$ and $b=\sum_{j=0}^lF_{d_j}\;(d_j\ge2)$ we define the Fibonacci product $a\circ b=\sum_{i=0}^k\sum_{j=0}^lF_{c_i+d_j}$ .

For example, the Zeckendorf representation of 2 is $F 3$ , and the Zeckendorf representation of 4 is $F 4 + F 2$ ( $F 1$ is disallowed from representations), so $2 \circ 4 = F_{3+4} + F_{3+2} = 13 + 5 = 18$ .