Zeckendorf's theorem (original) (raw)

From Wikipedia, the free encyclopedia

On the unique representation of integers as sums of non-consecutive Fibonacci numbers

The first 89 natural numbers in Zeckendorf form. Each rectangle has a Fibonacci number F j as width (blue number in the center) and F _j_−1 as height. The vertical bands have width 10.

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 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 = ∑ i = 0 k F c i , {\displaystyle N=\sum _{i=0}^{k}F_{c_{i}},} $N=\sum _{i=0}^{k}F_{c_{i}},$

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

For example, the Zeckendorf representation of 64 is

64 = 55 + 8 + 1.

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

64 = 55 + 5 + 3 + 1

64 = 34 + 21 + 8 + 1

64 = 34 + 21 + 5 + 3 + 1

64 = 34 + 13 + 8 + 5 + 3 + 1

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.

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 existence part of Zeckendorf's theorem can be proven by induction. The base case n = 1 {\displaystyle n=1} $n=1$ has the Zeckendorf representation n = 1 = F 2 {\displaystyle n=1=F_{2}} $n=1=F_{2}$ . Assuming that all k < n {\displaystyle k<n} $k<n$ have a Zeckendorf representation let j {\displaystyle j} $j$ be such that F j < n < F j + 1 {\displaystyle F_{j}<n<F_{j+1}} $F_{j}<n<F_{j+1}$ . Then, n − F j < n {\displaystyle n-F_{j}<n} $n-F_{j}<n$ . Therefore, there exists a Zeckendorf representation for n − F j {\displaystyle n-F_{j}} $n-F_{j}$ . The assumption F j < n < F j + 1 {\displaystyle F_{j}<n<F_{j+1}} $F_{j}<n<F_{j+1}$ also implies that F j − 1 = F j + 1 − F j > n − F j {\displaystyle F_{j-1}=F_{j+1}-F_{j}>n-F_{j}} $F_{j-1}=F_{j+1}-F_{j}>n-F_{j}$ . Therefore, the largest Fibonaci number in the Zeckendorf representation of n − F j {\displaystyle n-F_{j}} $n-F_{j}$ must be strictly less than F j − 1 {\displaystyle F_{j-1}} $F_{j-1}$ . This implies that the Zenckendorf representation of n − F j {\displaystyle n-F_{j}} $n-F_{j}$ together with F j {\displaystyle F_{j}} $F_{j}$ is a valid Zeckendorf representation for n {\displaystyle n} $n$ .

To prove uniqueness, one can use the identity

∑ i = 0 ⌊ n / 2 ⌋ − 1 F n − 2 i = F n + 1 − 1 {\displaystyle \sum _{i=0}^{\lfloor n/2\rfloor -1}F_{n-2i}=F_{n+1}-1} $\sum _{i=0}^{\lfloor n/2\rfloor -1}F_{n-2i}=F_{n+1}-1$

This can be proven by induction, or by a counting argument in which one realizes both sides of the identity are two ways of counting the number of ways of writing n {\displaystyle n} $n$ using sums of 1 {\displaystyle 1} $1$ and at least one 2 {\displaystyle 2} $2$ .

To get a contradiction, assume that there are integers c i {\displaystyle c_{i}} $c_{i}$ , for i = 0 , 1 , … , r {\displaystyle i=0,1,\ldots ,r} $i=0,1,\ldots ,r$ , and d i {\displaystyle d_{i}} $d_{i}$ , for i = 0 , 1 , … , s {\displaystyle i=0,1,\ldots ,s} $i=0,1,\ldots ,s$ , such that c 0 , d 0 ≥ 2 {\displaystyle c_{0},d_{0}\geq 2} $c_{0},d_{0}\geq 2$ , c i + 1 > c i + 1 {\displaystyle c_{i+1}>c_{i}+1} $c_{i+1}>c_{i}+1$ , d i + 1 > d i + 1 {\displaystyle d_{i+1}>d_{i}+1} $d_{i+1}>d_{i}+1$ , and

∑ i = 0 r F c i = ∑ i = 0 s F d i {\displaystyle \sum _{i=0}^{r}F_{c_{i}}=\sum _{i=0}^{s}F_{d_{i}}} $\sum _{i=0}^{r}F_{c_{i}}=\sum _{i=0}^{s}F_{d_{i}}$

The lengths r {\displaystyle r} $r$ and s {\displaystyle s} $s$ can be assumed to be the smallest possible.

If c r = d s {\displaystyle c_{r}=d_{s}} $c_{r}=d_{s}$ , that is if the largest terms F c r {\displaystyle F_{c_{r}}} $F_{c_{r}}$ and F d s {\displaystyle F_{d_{s}}} $F_{d_{s}}$ of the two Zeckendorf representations are equal, then they can be deleted from both representations and obtain two new Zeckendorf representations that are equal and have fewer number of summands. This contradicts that r , s {\displaystyle r,s} $r,s$ were the smallest possible. Therefore, c r ≠ d s {\displaystyle c_{r}\neq d_{s}} $c_{r}\neq d_{s}$ . By swapping the names c {\displaystyle c} $c$ and d {\displaystyle d} $d$ , if necessary, one can assume that c r > d s {\displaystyle c_{r}>d_{s}} $c_{r}>d_{s}$ . However, the sum

∑ i = 0 s F d i ≤ ∑ i = 0 ⌊ d s / 2 ⌋ − 1 F d s − 2 i = F d s + 1 − 1 ≤ F c r − 1 < F c r {\displaystyle \sum _{i=0}^{s}F_{d_{i}}\leq \sum _{i=0}^{\lfloor d_{s}/2\rfloor -1}F_{d_{s}-2i}=F_{d_{s}+1}-1\leq F_{c_{r}}-1<F_{c_{r}}} $\sum _{i=0}^{s}F_{d_{i}}\leq \sum _{i=0}^{\lfloor d_{s}/2\rfloor -1}F_{d_{s}-2i}=F_{d_{s}+1}-1\leq F_{c_{r}}-1<F_{c_{r}}$

Here the first inequality compares the sum with that of the Zeckendorf representation, which largest term is F d s {\displaystyle F_{d_{s}}} $F_{d_{s}}$ , and uses the largest Fibonaci numbers allowed. That is, using every second Fibonacci number descending from F d s {\displaystyle F_{d_{s}}} $F_{d_{s}}$ and stopping at F 2 {\displaystyle F_{2}} $F_{2}$ or F 3 {\displaystyle F_{3}} $F_{3}$ . The equation is the identity above. This shows that, even if the sum ∑ i = 0 s F d s {\displaystyle \sum _{i=0}^{s}F_{d_{s}}} $\sum _{i=0}^{s}F_{d_{s}}$ uses all the largest Fibonacci numbers allowed, its sum is still strictly less than the largest term F c r {\displaystyle F_{c_{r}}} $F_{c_{r}}$ in the sum ∑ i = 0 r F c i {\displaystyle \sum _{i=0}^{r}F_{c_{i}}} $\sum _{i=0}^{r}F_{c_{i}}$ . Therefore, one cannot have two different Zeckendorf representations giving the same sum.

Fibonacci multiplication

[edit]

One can define the following operation a ∘ b {\displaystyle a\circ b} $a\circ b$ on natural numbers a, b: given the Zeckendorf representations a = ∑ i = 0 k F c i ( c i ≥ 2 ) {\displaystyle a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)} $a=\sum _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)$ and b = ∑ j = 0 l F d j ( d j ≥ 2 ) {\displaystyle b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)} $b=\sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)$ we define the Fibonacci product a ∘ b = ∑ i = 0 k ∑ j = 0 l F c i + d j . {\displaystyle a\circ b=\sum _{i=0}^{k}\sum _{j=0}^{l}F_{c_{i}+d_{j}}.} $a\circ b=\sum _{i=0}^{k}\sum _{j=0}^{l}F_{c_{i}+d_{j}}.$

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

(The product is not always in Zeckendorf form. For example, 4 ∘ 4 = ( F 4 + F 2 ) ∘ ( F 4 + F 2 ) = F 4 + 4 + 2 F 4 + 2 + F 2 + 2 = 21 + 2 ⋅ 8 + 3 = 40 = F 9 + F 5 + F 2 . {\displaystyle 4\circ 4=(F_{4}+F_{2})\circ (F_{4}+F_{2})=F_{4+4}+2F_{4+2}+F_{2+2}=21+2\cdot 8+3=40=F_{9}+F_{5}+F_{2}.} $4\circ 4=(F_{4}+F_{2})\circ (F_{4}+F_{2})=F_{4+4}+2F_{4+2}+F_{2+2}=21+2\cdot 8+3=40=F_{9}+F_{5}+F_{2}.$ )

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.[1]

Representation with negafibonacci numbers

[edit]

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

F n − 2 = F n − F n − 1 , {\displaystyle F_{n-2}=F_{n}-F_{n-1},} $F_{n-2}=F_{n}-F_{n-1},$

which yields the sequence of "negafibonacci" numbers satisfying

F − n = ( − 1 ) n + 1 F n . {\displaystyle F_{-n}=(-1)^{n+1}F_{n}.} $F_{-n}=(-1)^{n+1}F_{n}.$

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

−11 = _F_−4 + _F_−6 = (−3) + (−8)
12 = _F_−2 + _F_−7 = (−1) + 13
24 = _F_−1 + _F_−4 + _F_−6 + _F_−9 = 1 + (−3) + (−8) + 34
−43 = _F_−2 + _F_−7 + _F_−10 = (−1) + 13 + (−55)
0 is represented by the empty sum.

0 = _F_−1 + _F_−2 , 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 x, the nth digit is 1 if F−n appears in the sum that represents x; 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 24 = _F_−1 + _F_−4 + _F_−6 + _F_−9 . The integer x is represented by a string of odd length if and only if x > 0.

^ Knuth, Donald E. (1988). "Fibonacci multiplication" (PDF). Applied Mathematics Letters. 1 (1): 57–60. doi:10.1016/0893-9659(88)90176-0. ISSN 0893-9659. Zbl 0633.10011.
^ Knuth, Donald (2008-12-11). Negafibonacci Numbers and the Hyperbolic Plane. Annual meeting, Mathematical Association of America. The Fairmont Hotel, San Jose, CA.

Zeckendorf, E. (1972). "Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas". Bull. Soc. R. Sci. Liège (in French). 41: 179–182. ISSN 0037-9565. Zbl 0252.10011.
Weisstein, Eric W. "Zeckendorf's Theorem". MathWorld.
Weisstein, Eric W. "Zeckendorf Representation". MathWorld.
Zeckendorf's theorem at cut-the-knot
G.M. Phillips (2001) [1994], "Zeckendorf representation", Encyclopedia of Mathematics, EMS Press
OEIS sequence A101330 (Knuth's Fibonacci (or circle) product)

This article incorporates material from proof that the Zeckendorf representation of a positive integer is unique on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.