Zeckendorf representation

Every positive integer $n$ can be expressed uniquely as a sum of distinct non-consecutive Fibonacci numbers. This result is called Zeckendorf's theorem and the sequence of Fibonacci numbers which add up to $n$ is called the Zeckendorf representation of $n$. The theorem and the representation are named after the Belgian medical doctor and amateur mathematician E. Zeckendorf (1901–1983). See [a3] for a fine brief biography of Zeckendorf.

The Fibonacci sequence is defined by $F _ { 1 } = F _ { 2 } = 1$ and $F _ { n } = F _ { n - 1} + F _ { n - 2}$ for $n > 2$. The precise sequence used in the Zeckendorf theorem and representation is the Fibonacci sequence with $F _ { 1 }$ deleted, the first few members being

\begin{equation*} 1,2,3,5,8,13,21 , \ldots . \end{equation*}

Examples of Zeckendorf representations are:

\begin{equation*} 71 = 55 + 13 + 3, \end{equation*}

\begin{equation*} 100 = 89 + 8 + 3,1111 = 987 + 89 + 34 + 1. \end{equation*}

To construct the Zeckendorf representation of $n$, one chooses the largest Fibonacci number not greater than $n$, say $F _ { n _ { 1 } }$, and subtracts it from $n$. Unless $n$ is thereby reduced to zero, one then finds the largest Fibonacci number not greater than $n - F _ { n _ { 1 } }$, say $F _ { n _ { 2 } }$, and subtracts it, etc. If $n$ is reduced to zero after $k$ steps, one obtains a Zeckendorf representation of the form

\begin{equation*} n = F _ { n _ { 1 } } + \ldots + F _ { n _ { k } }, \end{equation*}

where $n _ { 1 } , \ldots , n _ { k }$ is a decreasing sequence of positive integers. This representation cannot include two consecutive Fibonacci numbers, say $F _ { m }$ and $F _ { m - 1 }$, for this would imply that their sum, $F_{m + 1}$, or some larger Fibonacci number should have been chosen in place of $F _ { m }$. The smallest integer whose Zeckendorf representation is the sum of $k$ Fibonacci numbers is

\begin{equation*} F _ { 2 } + \ldots + F _ { 2 k } = F _ { 2 k + 1 } - 1. \end{equation*}

It can be shown by construction that no other sequence can be substituted for the Fibonacci sequence in the statement of Zeckendorf's theorem (see [a1]). Fibonacci numbers have been known to mathematics for some 800 years and it seems rather surprising that this property of them did not receive attention until relatively recently. Indeed, nothing appeared in print concerning the Zeckendorf representation until the middle of the 20th century, with the publication of a paper of C.G. Lekkerkerker [a4]. Zeckendorf did not publish his own account until 1972 (see [a6]) although (see [a3]) he had a proof of his theorem by 1939. Every positive integer can also be uniquely represented as a sum of different powers of two, and it is natural to compare Zeckendorf representations with binary representations. This is pursued in [a2], where there is a discussion of algorithms which, given two positive integers $a$ and $b$ in Zeckendorf form, produce the Zeckendorf forms for $a + b$ and $a b$. Even the addition algorithm is rather more complicated than the corresponding algorithm for binary arithmetic. (If this were not so, "Zeckendorf arithmetic" might be used nowadays instead of binary arithmetic.) The Zeckendorf multiplication algorithm given in [a2] is based on the fact that, for $m \geq n \geq 2$, the Zeckendorf representation of $F _ { m } F _ { n }$ is

for $n$ even. When $n$ is odd, one has to add one further term to the above sum: the term $F _ { m - n + 1}$ when $m > n$ and the term $F _ { 2 }$ when $m = n$. In the upper limit of the summation, $[ n / 2 ]$ denotes the largest integer not greater than $n / 2$.

An amusing trivial "application" of the Zeckendorf representation is a method of converting miles into kilometres and vice versa without having to perform a multiplication. It relies on the coincidence that the number of kilometres in a mile (approximately $1.609$) is close to the golden-section number (cf. also Golden ratio),

\begin{equation*} \operatorname { lim } _ { n \rightarrow \infty } \frac { F _ { n + 1 } } { F _ { n } } = \frac { 1 } { 2 } ( \sqrt { 5 } + 1 ) \simeq 1.618. \end{equation*}

Thus, to convert miles into kilometres one writes down the (integer) number of miles in Zeckendorf form and replaces each of the Fibonacci numbers by its successor. This will give the Zeckendorf form of the corresponding approximate number of kilometres. For example,

\begin{equation*} 50 = 34 + 13 + 3 \ \text{miles} \end{equation*}

is approximately

\begin{equation*} 55 + 21 + 5 = 81\text{kilometres} \end{equation*}

and $50$ kilometres is approximately

\begin{equation*} 21 + 8 + 2 = 31 \text{ miles.} \end{equation*}

References

[a1]	D.E. Daykin, "Representation of natural numbers as sums of generalised Fibonacci numbers" J. London Math. Soc. , 35 (1960) pp. 143–160
[a2]	H. Freitag, G.M. Phillips, "Elements of Zeckendorf arithmetic" , Applications of Fibonacci Numbers (Graz, 1996) , 7 , Kluwer Acad. Publ. (1998) pp. 129–132
[a3]	C. Kimberling, "Edouard Zeckendorf" Fibonacci Quart. , 36 (1998) pp. 416–418
[a4]	C.G. Lekkerkerker, "Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci" Simon Stevin , 29 (1952) pp. 190–195
[a5]	S. Vajda, "Fibonacci & Lucas numbers, and the Golden Section" , Wiley (1989)
[a6]	E. Zeckendorf, "Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas" Bull. Soc. R. Sci. Liège , 41 (1972) pp. 179–182