Zeckendorf's theorem

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. More precisely, if "N" is any positive integer, there exist positive integers "c"_"i" ≥ 2, with "c"_{"i" + 1} > "c"_"i" + 1, such that

:$N\; =\; sum\_\{i\; =\; 0\}^k\; F\_\{c\_i\},$ where "F"_"n" is the "n"^th Fibonacci number. Such a sum is called the Zeckendorf representation of "N".

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.

Proof of Zeckendorf's theorem

Zeckendorf's theorem has two parts:

#Existence: every positive integer "n" has a Zeckendorf representation.
#Uniqueness: no positive integer "n" has two different Zeckendorf representations.

The first part of Zeckendorf's theorem (existence) can be proved by induction. For "n" = 1, 2, 3 it is clearly true, for "n" = 4 we have 4 = 3 + 1.Now let each $n\; leq\; k$ have a Zeckendorf's representation. If "k" + 1 is a Fibonacci number then we're done, else there exists "j" such that

The second part of Zeckendorf's theorem (uniqueness) requires the following lemma:

:"Lemma": The sum of any non-empty set of distinct, non-consecutive Fibonacci numbers whose largest member is "F"_"j" is strictly less than the next largest Fibonacci number "F"_"j"+1.

The lemma can be proved by induction on "F"_"j".

Now take two non-empty sets of distinct non-consecutive Fibonacci numbers S and T which have the same sum. Eliminate common members to form two sets S' and T' with no members in common. We want to show that S' and T' are both empty i.e. that S=T.

First we show that at least one of S' and T' is empty. Assume the contrary i.e. that S' and T' are both non-empty. Let the largest member of S' be "F"_"s" and the largest member of T' be "F"_"t". Without loss of generality, suppose "F"_"s"<"F"_"t". Then by the lemma, the sum of S' is strictly less than "F"_"s+1", and so is strictly less than "F"_"t", whereas the sum of T' is clearly at least "F"_"t". This means that S' and T' cannot have the same sum, and so S and T cannot have the same sum. So our assumption that S' and T' are both non-empty must be incorrect.

If S' is empty and T' is non-empty then S is a proper sub-set of T, and so S and T cannot have the same sum. Similarly we can eliminate the case where S' is non-empty and T' is empty. The only remaining case is that S' and T' are both empty, so S=T. We conclude that any two Zeckendorf representations that have the same sum must be identical (up to order).

Fibonacci multiplication

One can define the following operation $acirc\; b$ on natural numbers "a", "b": given the Zeckendorf representations$a=sum\_\{i=0\}^kF\_\{c\_i\};(c\_ige2)$ and $b=sum\_\{j=0\}^lF\_\{d\_j\};(d\_jge2)$ we define the Fibonacci product $acirc\; b=sum\_\{i=0\}^ksum\_\{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$.

Don Knuth proved the surprising fact that this operation is associative. See also OEIS2C|id=A101330.

References

D. E. Knuth, Fibonacci multiplication, "Appl. Math. Lett." 1 (1988), 57–60

ee also

* Fibonacci coding

External links

*MathWorld |title=Zeckendorf's Theorem |urlname=ZeckendorfsTheorem
*MathWorld |title=Zeckendorf Representation |urlname=ZeckendorfRepresentation
* [http://www.cut-the-knot.org/ctk/OnePile.shtml#fibnim Zeckendorf's theorem] at cut-the-knot
*SpringerEOM|urlname=Z/z120020|title=Zeckendorf representation|author=G.M. Phillips