arvau

Wikipedia / Zeckendorf's theorem

Zeckendorf's theorem, named after amateur mathematician Edouard Zeckendorf, is a result about the representation of integers as sums of Fibonacci numbers. It states that every positive integer can be represented uniquely as the sum of one or more Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. More precisely, if is any positive integer, there exist positive integers , with , such that

where is the th Fibonacci number. Such a sum is called the Zeckendorf representation of . The Fibonacci coding of can be derived from its Zeckendorf representation.

For example, the Zeckendorf representation of 64 is

  1. .

There are other ways of representing 64 as the sum of Fibonacci numbers

but these are not Zeckendorf representations because 34 and 21 are consecutive Fibonacci numbers, as are 5 and 3.

For any given positive integer, its Zeckendorf representation can be found by using a greedy algorithm, choosing the largest possible Fibonacci number at each stage. For instance, 11 = 8 + 3, whereas 13 = 13 (not 8 + 5), and 31 = 21 + 8 + 2.

Proof

Zeckendorf's theorem has two parts:

  1. Existence: every positive integer has a Zeckendorf representation.

  2. Uniqueness: no positive integer has two different Zeckendorf representations.

The existence part of Zeckendorf's theorem can be proven by induction.

To prove uniqueness, one can use the identity

This can be proven by induction, or by a counting argument.

, and

can be assumed to be the smallest possible.

. However, the sum

. Therefore, one cannot have two different Zeckendorf representations giving the same sum.

Fibonacci multiplication

on natural numbers , we define the Fibonacci product

)

A simple rearrangement of sums shows that this is a commutative operation; however, Donald Knuth proved the surprising fact that this operation is also associative.

Representation with negafibonacci numbers

The Fibonacci sequence can be extended to negative index using the rearranged recurrence relation

which yields the sequence of "negafibonacci" numbers satisfying

Any integer can be uniquely represented as a sum of negafibonacci numbers in which no two consecutive negafibonacci numbers are used. For example:

, for example, so the uniqueness of the representation does depend on the condition that no two consecutive negafibonacci numbers are used.

This gives a system of coding integers, similar to the representation of Zeckendorf's theorem. In the string representing the integer, the th digit is 1 if appears in the sum that represents ; that digit is 0 otherwise. For example, 24 may be represented by the string 100101001, which has the digit 1 in places 9, 6, 4, and 1, because . The integer is represented by a string of odd length if and only if .

See also

References