Zeckendorf representation

This article page is a stub, please help by expanding it.

This article needs more work.

Please help by expanding it!

The Zeckendorf representation of an integer is the unique way of representing that integer as a sum of non-consecutive Fibonacci numbers. For example, the Zeckendorf representation of 12 is 10101, corresponding to 8 + 3 + 1.

Theorem Z0. Every positive integer $n$ has a Zeckendorf representation as a sum of non-consecutive Fibonacci numbers $F_{i}$.

Proof. If an integer $n=F_{k}$, where $F_{k}$ refers to the $k$th Fibonacci number, then $Z_{k}=1$ and $Z_{i}=0$ for all $0<i<k$, where $Z$ is an array of binary digits and $k$ is the index of the most significant digit.

Otherwise, we assign $j=n-F_{i}$ where $F_{i}$ is the largest Fibonacci number such that $F_{i}<n$. Then $Z_{i}>0$. It is obvious that $j<F_{i}$, because it can be safely assumed at this juncture that $F_{i-2}$ and $F_{i-1}$ are distinct, that $F_{i-2}<F_{i-1}$ and therefore $F_{i}<2F_{i-1}$. This proves that $Z_{i}$ must be 1, but no more than that. If $j$ is a Fibonacci number, we can stop now, otherwise, we must again subtract the largest possible Fibonacci number, decrement $i$ accordingly and set the appropriate $Z_{i}=1$. The farthest this iterative process can go is to $i=1$, corresponding to $F_{1}=1$.

Furthermore, the 1s in $Z$ must have 0s in between them because any two consecutive 1s, such as at, say, $Z_{i}$ and $Z_{i-1}$ would indicate a failure to recognize that $F_{i-1}+F_{i}=F_{i+1}$, and thus $Z_{i}$ and $Z_{i-1}$ can be set to zero in favor of setting $Z_{i+1}$ to 1. □

Corollary to Theorem Z0. No binary representation of a Mersenne number should be mistaken for a Zeckendorf representation; in other words, there are no repunits in Zeckendorf representations.

Theorem Z1. For any positive integer $n$, the Zeckendorf representation $Z$ (with $k$ elements all 0s or 1s) of $n$ is unique.

For our proof, we accept it as axiomatic that $F_{1}=F_{2}=1$ but $F_{1}$ is not used in the Zeckendorf representation of any number. We also accept as axiomatic that all $F_{i}$ are distinct as long as $i>1$.

Proof. Assume that there are two integers $a$ and $b$ such that $0<a<b$, yet they both have the same Zeckendorf representation $Z$ with $k$ elements all 0s or 1s. We compute $c=\sum _{i=1}^{k}Z_{i}F_{i},$ where $F_{i}$ is the $i$th Fibonacci number. We can be assured that there is only one possible value for $c$ since all $F_{i}$ are distinct for $i>1$ and each $F_{i}$ was added only once or not at all, since each $Z_{i}$ is limited by definition to 0 or 1. Now $c$ holds the value of the Zeckendorf representation $Z$. If $c=a$, it follows that $c<b$, but that would mean that $Z$ is not the Zeckendorf representation of $b$ after all, hence this results in a contradiction of our initial assumption. And if on the other hand $c=b$ and $c>a$, then this leads to a similar contradiction as to what is the Zeckendorf representation of $a$ really is. □

These facts may also be proven combinatorially.

Theorem ZC. Every nonnegative integer has a unique representation as a sum of nonconsecutive Fibonacci numbers, where we do not use $F_{1}$ and instead use

$F_{2}=1,F_{3}=2,F_{4}=3,F_{5}=5,F_{6}=8,\dots$

(Ignoring $F_{1}$ is necessary only to prevent the trivial counterexamples such as $6=F_{5}+F_{2}=F_{5}+F_{1}$).

Proof. Given a sum $\sum _{i=2}^{n}Z_{i}F_{i}$ where $Z_{i}\in \{0,1\}$, we write that as a sequence of binary digits; thus $F_{4}+F_{2}$ is written as 101, while $F_{7}+F_{5}+F_{2}$ is 101001. Arrange such sequences with no two consecutive 1's (i.e. those sequences corresponding to sums of nonconsecutive Fibonacci numbers) in increasing lexicographic order starting from 0, and assign each one a rank corresponding to its order in the list:

${\begin{array}{c c c c c | c}5&4&3&2&1&rank\\\hline &&&&0&0\\&&&&1&1\\&&&1&0&2\\&&1&0&0&3\\&&1&0&1&4\\&1&0&0&0&5\\&1&0&0&1&6\\&1&0&1&0&7\\1&0&0&0&0&8\end{array}}$

Note that the rank is not the value of the string as a binary string. In fact, it is the sum of the string when interpreted as a sum of Fibonacci numbers, but we do not assume this; as far as we know up to this point, all the rank is is the row number in this table.

We say that such a sequence has length $n$ if the leftmost 1 is in position $n$; thus 100 has length 3.

Claim that the number of representations with length $\leq n$ is $F_{n+2}$. We prove this by induction on $n$; note that it is true for $n=0$ and for $n=1$. Now, given any representation of length $\leq n$, it either has length $\leq n-1$ or it has length exactly $n$. The number of representations of length $\leq n-1$ is, by induction, $F_{n+1}$. To compute the number of representations of length exactly $n$, note that any such representation starts with 10 since we cannot have two consecutive 1's. The digits after the 10 are arbitrary as long as there are not two consecutive 1's, so that the number of such representations is precisely the number of representations of length $\leq n-2$, or $F_{n}$. Thus the number of representations of length $\leq n$ is $F_{n+1}+F_{n}=F_{n+2}$. This proves the claim.

We will now prove the theorem by counting the number of rows preceding row $n$ in two different ways. First, the number of such rows is obviously $n$ (since we just numbered the row consecutively). We now count the number of predecessors by looking at the corresponding sequence. Given a sequence $s$, each of its predecessors $p$ first differs from it in some position $k$; since $s>p$ lexicographically, $s$ must be 1 in that position while $p$ is zero. Since $p$ has a zero in position $k$, the remaining $k-1$ digits of $p$ are arbitrary subject to the consecutivity condition, so the number of possibilities for $p$ is the number of representations of length $\leq k-1$, which is $F_{k+1}$. We can do this for each possible point of difference with $s$ (which occur at the positions in which $s$ has a 1, and thus must have nonconsecutive indices). This counts each predecessor of $s$ once and only once, and gives a representation of the number of predecessors as a sum of nonconsecutive Fibonacci numbers. But there are $n$ predecessors, so we have written $n$ as the required sum.

As an example of this process, consider the row numbered 7, which is the sequence 1010. If a predecessor differs from it at the first 1, it is of the form 0*** where the asterisks are arbitrary (so long as there are no two consecutive 1's, so there are $F_{5}$ of them. If a predecessor differs from it at the second 1, it is of the form 100* and again the asterisks are arbitrary, so there are $F_{3}$ of them. Thus $7=F_{5}+F_{3}$.

This argument shows existence; uniqueness follows as well from this construction since every possible sum is represented in the list, and each one represents a different integer. □

These facts about Zeckendorf representations can be used to prove some facts about Fibonacci numbers.

Theorem ZF. (John W. Layman) A positive integer $n$ has exactly two representations as the sum of two Fibonacci numbers if and only if $n$ is twice a Fibonacci number and $n\geq 4$. (See A078642).

Proof. (Max Alekseyev) Suppose that the number $m$ has exactly two representations as the sum of two Fibonacci numbers. There are three types of representations possible:

• (I) The sum of two equal Fibonacci numbers
• (II) The sum of two consecutive Fibonacci numbers
• (III) The sum of two distinct non-consecutive Fibonacci numbers

The two representations of $m>2$ must be of different types. Two representations of $m>2$ both of type (I) are not possible as $2F_{n}$ is a strictly increasing function for $n\geq 2$. Similarly, two representations of m both of type (II) are not possible as $F_{n}+F_{n+1}$ is a strictly increasing function for $n\geq 0$. Finally, two representations of $m$ both of type (III) are not possible as that would violate the property of the Zeckendorf representation (the uniqueness of representation of all nonnegative integers).

Consider all possible pairs of representation types:

• (I) and (II) are possible only for $m=2$: $2=2F_{1}=2F_{2}=F_{1}+F_{2}$ but $m=2$ has more than two different representations.
• (II) and (III) are not possible together as that would again violate the property of the Zeckendorf numeral system.
• Finally, (I) and (III) gives rise to the sequence of $a(n)=2F_{n}=F_{n+1}+F_{n-1}$. □

This article is based in part on the following PlanetMath articles http://planetmath.org/proofthateverypositiveintegerhasazeckendorfrepresentation and http://planetmath.org/proofthatazeckendorfrepresentationrepresentsauniquepositiveinteger and http://planetmath.org/combinatorialproofofzeckendorfstheorem