Zeckendorf’s Theorem and Fibonacci Coding for
Modules
Perathorn Pooksombat, Patanee Udomkavanich, and Wittawat Kositwattanarerk, ∗

arXiv:1706.06655v1 [] 20 Jun 2017

June 22, 2017

Abstract
Zeckendorf’s theorem states that every positive integer can be written uniquely
as a sum of nonconsecutive Fibonacci numbers. This theorem induces a binary
numeration system for the positive integers known as Fibonacci coding. Fibonacci
code is a variable-length prefix code that is robust against insertion and deletion
errors and is useful in data transmission and data compression. In this paper,
we generalize the theorem of Zeckendorf and prove that every element of a free
Z-module can be represented as a sum of elements from a Fibonacci sequence of
higher order. Immediate applications of these results include a Fibonacci coding
for free Z-modules, where encoding and decoding algorithms are obtained naturally
from the approach of our theorems.

Keywords: Zeckendorf’s theorem, Fibonacci codes, Z-module, Gaussian integers

1

Introduction

There are certainly many generalizations of the Fibonacci sequence. The classical one is
defined recursively by
F0 = 0,

F1 = 1,

and Fn−2 + Fn−1 = Fn for all n ≥ 2.

One may allow the index n to be negative, resulting in what is called negaFibonacci sequence. A generalized Fibonacci sequence of order k is a sequence in which each sequence
element is the sum of the preceding k terms. In this view, the usual Fibonacci sequence
is of order 2. Typically, the initial terms of the generalized Fibonacci sequence of order
k are F−k+2 = . . . = F0 = 0 and F1 = 1.
P. Pooksombat and W. Kositwattanarerk are with the Department of Mathematics, Faculty of Science, Mahidol University, Bangkok 10400, Thailand and the Centre of Excellence in Mathematics, the Commission on Higher Education, Bangkok 10400, Thailand (e-mail:
perathorn.pok@student.mahidol.edu and wittawat.kos@mahidol.edu). P. Udomkavanich is with the Department of Mathematics and Computer Science, Faculty of Science, Chulalongkorn University, Bangkok
10330, Thailand (email: pattanee.u@chula.ac.th). The research of W. Kositwattanarerk for this work is
supported by the Thailand Research Fund under Research Grant TRG5880116.
∗

1

The much-celebrated Zeckendorf’s theorem states that every positive integer can be
uniquely written as
Fi1 + Fi2 + . . . + Fij
where i1 , i2 − i1 , . . . , ij − ij−1 ≥ 2. This result can be extended to all integers by using
instead negaFibonacci sequence [5, 22]. In other words, every integer can be written
uniquely as sum of nonconsecutive negaFibonacci numbers. Zeckendorf’s theorem has
been generalized and investigated in many directions; similar results can be stated for
the generalized Fibonacci sequence of order k [6, 30] and linear recurrence sequences
[9, 15]. The distribution of the number of terms in a Zeckendorf decomposition is studied
in [4, 23, 25] where a probabilistic approach has recently been applied [2].
Zeckendorf’s theorem also finds several applications in data transmission and compression. Since the theorem provides a binary numeration system for the integers, it can
be used to design an error-resistant universal code called Fibonacci code. The scheme
was introduced by [12] and generalized to higher order in [1]. Theoretically, Fibonacci
code makes use of the fact that the Zeckendorf representation of an integer involves no
two consecutive terms from the Fibonacci sequence. This coding scheme is optimal under
some distributions and can be used as an alternative to Huffman codes [13, 27]. In addition, it comes with fast encoding and decoding algorithms [31, 32]. Other applications of
Fibonacci sequence in data science include the study of Morse code as a monoid [7, 28]
and Wavelet trees [21].
In this paper, we consider generalizations of Zeckendorf’s theorem and Fibonacci code
for free-Z modules. This includes, for example, the integers, Gaussian and Eisenstein integers, lattices, and the ring Z[α] where α is algebraic. In fact, we will be studying
generalizations of Zeckendorf’s theorem in its purest form: we consider any sequence
that satisfies the generalized Fibonacci recurrence relation and examine elements that
can be written as a sum of terms from the sequence. Since every term in the sequence is
practically a linear combination of the sequence’s initial conditions, one can at best hope
to generate a module using sums of elements from this sequence. Hence, by design we
adopt free Z-modules as a mathematical space of interest.
Noninteger Fibonacci sequences have been studied mostly on complex numbers [3, 16,
17, 14, 19, 26]. In particular, Jordan [19] and Harman [17] consider Fibonacci sequences
whose initial terms and indices are Gaussian integers. Other generalizations usually involve an identity whose integer terms yield the classical Fibonacci numbers. For example,
Binet’s formula is exploited in [16, 26] where a Fibonacci function is defined over the real
and complex numbers.
From number-theoretic point of view, Zeckendorf decomposition can be seen as a numeration system where binary digits are used with Fibonacci numbers as a base. As it
turns out, binary representation for multidimensional number systems is not well studied.
Kátai and Szabó [20] show that Gaussian integers can be written in base −1 + i, thus
giving a binary representation for Gaussian integers where the real part and complex
part are not dealt with separately. In [11], Forney uses 1 + i as a basis to construct
complex lattice codes. While some ring of integers may have special characteristics that
2

permit similar binary representation, these systems at best provide fixed-length codes for
communication over a channel.
This paper studies generalizations of Zeckendorf’s theorem for modules and the subsequent Fibonacci coding. We summarize the contributions of this paper as follows.
• We introduce the notion of k-equivalent sequences. This approach technically treats
elements that can be generated from a Fibonacci sequence as a number system
using sequence elements as a basis. This key mechanism allows us to manipulate
the “digits” without an explicit knowledge of the underlying Fibonacci sequence.
We prove that an element has a Zeckendorf decomposition if and only if it can be
written as a finite sum (with multiplicities) of sequence elements.
• We provide a sufficient and necessary condition for Zeckendorf’s theorem to hold
in a free Z-module. Obviously, the classical Zeckendorf’s theorem can be viewed
as a case of our generalization. We also give a sufficient condition that makes the
representation unique.
• We propose Fibonacci coding for any free Z-module. This is the first work that
makes possible Fibonacci coding for non-integers. Not only that our work substantially enlarges the message spaces for Fibonacci code, the resulting codes inherit
robustness property from the standard Fibonacci code. Naturally, this also gives
binary numeration systems for spaces such as Gaussian integers, Eisenstein integers, quarternions, the ring of integers of any algebraic number field, and lattices.
In addition, explicit encoding and decoding algorithm are also given.
The remainder of this paper is organized as follows. Section 2 sets the definitions
that will be used throughout the paper. In Section 3, we prove several useful results
concerning k-equivalent sequences. Generalizations of Zeckendorf’s theorem are given in
Section 4. We establish Fibonacci coding in Section 5 and conclude with final discussion
in Section 6.

2

Definitions

We first give a definition for free modules and Fibonacci sequences of higher order. A
free Z-module is a module over Z with a basis. Namely, M is a free Z-module of rank l
if it is a group under addition and
M = α1 Z ⊕ α2 Z ⊕ . . . ⊕ αl Z
for some α1 , α2 , . . . , αl that are integrally independent, meaning that the only integer
solution to the equation n1 α1 + n2 α2 + . . . + nl αl = 0 is n1 = n2 = . . . = nl = 0. Algebraically speaking, modules differ from rings in that multiplication may not be defined for
module elements. Here, for n ∈ Z+ and m ∈ M, we write nm to mean |m + m +
{z. . . + m}.
n times

If M = α1 Z ⊕ α2 Z ⊕ . . . ⊕ αl Z for integrally independent α1 , α2 , . . . , αl , every element
of M can be written uniquely as n1 α1 + n2 α2 + . . . + nl αl where n1 , n2 , . . . , nl ∈ Z. The
3

elements α1 , α2 , . . . , αl are called a basis for M.
If α1 , α2 , . . . , αl are integrally independent, Zhα1 , α2 , . . . , αl i is the free Z-module generated by α1 , α2 , . . . , αl . For example, Zh1i, Zh1, ii, Zh1, ωi are the set of integers, Gaussian integers, and Eisenstein integers respectively.
We are interested in a Fibonacci sequence whose entries are elements of a module,
so we adopt a somewhat broad definition of a Fibonacci sequence and a corresponding
generalization of a Zeckendorf representation.
Definition 2.1 A Fibonacci sequence of order k is a doubly infinite sequence (Fr )r∈Z =
(. . . , F−1 , F0 , F1 , . . .) where
Fn−k + . . . + Fn−2 + Fn−1 = Fn
for all integer n.
Definition 2.2 Let (Fr )r∈Z be a Fibonacci sequence of order k. An element m is Zeckendorf in (Fr ) if it can be written as a finite sum of elements in (Fr ) with no k consecutive
terms. A set M is Zeckendorf in (Fr ) if every element of M is.
Notice that we do not specify the initial conditions for a Fibonacci sequence. In fact,
most of our results hold irrespective of the initial conditions of the sequence. A Fibonacci
sequence of order k has degree of freedom k; knowing any k consecutive terms is sufficient
to generate the entire sequence. For k ≥ 2, the characteristic polynomial of a Fibonacci
sequence of order k is xk − xk−1 − xk−2 − . . . − x − 1. It is known [24] that this polynomial
has k distinct roots λ1 , λ2 , . . . , λk where λ1 ∈ (1, 2) and λ2 , . . . , λk lie in the unit circle.
Note that the sequence (λr1 )r∈Z is a Fibonacci sequence of order k. We call this sequence
primitive.
Example 2.3 In this example we consider several Fibonacci sequences of order 3.
i.) The usual Tribonacci sequence is defined using F0 = F1 = 1, F2 = 2, and Fn−3 +
Fn−2 + Fn−1 = Fn . The first few terms of this sequence are
1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, . . . .
The two-way generalization of this sequence is given by
. . . , 5, −8, 4, 1, −3,
2 0, −1, 1,
0,
0,
1,
1, 2, 4,
7, 13, 24, 44, 81, 149, 274, . . . .
ii.) The three roots of a polynomial x3 − x2 − x − 1 are λ1 ≈ 1.839, λ2 ≈ −0.42 − 0.606i,
and λ3 ≈ −0.42+0.606i. The primitive Fibonacci sequence of order 3 is the sequence
(λr1 )r∈Z , which is approximately
. . . , 0.161, 0.296, 0.544, 1, 1.839, 3.383, 6.222, 11.445, 21.05, . . . .

4

iii.) A Fibonacci sequence of order 3 where F0 = 0, F1 = 1 + i, and F2 = 2 + i is given
by
. . . , 5 + i, −2 − 3i, −1 + 2i,
2, −1 − i,
i,
1,
0,
1 + i,
2 + i, 3 + 2i, 6 + 4i, 11 + 7i, 20 + 13i, . . . .
The element 9 + 5i, for example, is Zeckendorf in this sequence since 9 + 5i =
(5 + i) + (−1 + 2i) + (2) + (3 + 2i).
In order to study elements that are Zeckendorf in (Fr ), it is natural to consider
elements of the form (xr ) · (Fr ) where (xr ) is a doubly infinite sequence of integers and ·
is an infinite dot product, i.e.
X
xr Fr .
(xr ) · (Fr ) =
r∈Z

Roughly speaking, a collection of all elements of the form (xr ) · (Fr ) is a number system
base (Fr ) with the digit set Z. Here, (xr ) acts like digits or coefficients for the basis (Fr ).
These so-called coefficients can be manipulated using the following methods.
Definition 2.4 Doubly infinite sequences (xr ) and (yr ) are k-equivalent, denoted (xr ) ∼k
(yr ), if (yr ) can be obtained from (xr ) using finite applications of the following two operations.
Operation 1: For some n ∈ Z, subtract 1 from xn and add 1 to all of xn−k . . . , xn−2 , xn−1 .
Operation 2: For some n ∈ Z, add 1 to xn and subtract 1 from all of xn−k . . . , xn−2 , xn−1 .
It is not hard to see that Operations 1 and 2 “cancel out”, and ∼k is an equivalent
relation. These operations also preserve the value of the dot product: if (Fr ) is a Fibonacci
sequence of order k and (xr ) ∼k (yr ), then (xr )·(Fr ) = (yr )·(Fr ). As we will see later, this
observation is an important ingredient of our results. Finally, we give a lexicographical
order ≻ to the doubly infinite sequences that are zero almost everywhere, i.e., (xr )r∈Z ≻
(yr )r∈Z if the entry of (xr ) is larger than that of (yr ) at the rightmost index where they
are not equal.

3

k-equivalent Sequences

In a way, our approach in proving a generalized theorem of Zeckendorf is in asking the
converse question: given a Fibonacci sequence (Fr ) of order k, which elements can be
written as a finite sum of elements from (Fr ) using no k consecutive terms? It is not
hard to see that they are elements of the form (yr ) · (Fr ) where (yr ) is binary, 0 almost
everywhere, and has no k consecutive 1’s. Now, instead of characterizing these elements
directly, we will focus on manipulating the coefficients (yr ) using Operations 1 and 2 from
Definition 2.4. These coefficient manipulations operate independently of the underlying
Fibonacci sequence (Fr ), and so this approach frees us from having to worry about the
choice of (Fr ). As we will see, our results hold in a broad sense and are not limited to
just any specific Fibonacci sequence. Propositions 3.1 and 3.2 given in this section will
provide an effective mechanism for identifying sequences that are k-equivalent to a binary
sequence with the required properties.
5

Proposition 3.1 A sequence (xr )r∈Z of integers that is 0 almost everywhere is k-equivalent
to a sequence (yr )r∈Z that is either
• zero everywhere,
• positive at some k consecutive terms and zero elsewhere, or
• negative at some k consecutive terms and zero elsewhere.
In addition, if (xr )r∈Z 6= (0)r∈Z is nonnegative, then the k consecutive terms of (yr )r∈Z
are positive.
Proof We keep applying either Operation 1 or 2 from Definition 2.4 to eliminate the
rightmost nonzero term of (xr ). Since (xr ) is 0 almost everywhere, we will eventually
obtain a sequence (yr )r∈Z which is 0 everywhere except for some k consecutive terms.
If the k consecutive terms of (yr ) are all positive, all negative, or all zero, then we are
done. Otherwise, we can keep eliminating the rightmost nonzero term of (yr ) and obtain
yet another sequence that is 0 everywhere except for some k consecutive terms. We will
prove that this process will eventually yield a sequence with k consecutive terms that are
either all positive or all negative.
We initialize (y0,r ) = (yr ) and collect the k nonzero terms of (y0,r ) into a 1 × k
vector γ0 = (γ1 , γ2 , . . . , γk ). The rightmost term of (y0,r ) is γk . Using either Operation
1 or 2, we eliminate this term an obtain (y1,r ) whose nonzero entries are given by γ1 =
(γk , γ1 + γk , γ2 + γk , . . . , γk−1 + γk ). In other words, we have
γ1⊤ = Aγ0⊤
where


0
1


A = 0
 ..
.
0


··· 0 1
· · · 0 1

· · · 0 1
.
. . .. .. 
. . .
0 0 ··· 1 1
0
0
1
..
.

0
0
0
..
.

Note that this is independent of the value of γk . We repeat this process, and it is not
hard to see that (y0,r ) is k-equivalent to (yn,r ) for all positive integer n. In addition, the
nonzero terms of (yn,r ) are given by the entries of γn⊤ = An γ0⊤ . Thus, it remains to show
that there is an n for which An γ0⊤ is either positive or negative.
It should not be surprising that A is the transpose of the usual Fibonacci matrix.
Thus, A has characteristic equation xk − xk−1 − xk−2 − . . . − x − 1 and eigenvalues
λ1 ∈ (1, 2) and λ2 , . . . , λk whose complex norms are less than 1 [24]. We denote by vi
eigenvector corresponding to the eigenvalue λi . Note that


λ1k−2


λ1k−2 + λ1k−3


k−2
k−3
k−4


λ1 + λ1 + λ1


v1 = 

.
..


 k−2

k−3
λ1 + λ1 + · · · + λ1 + 1
λ1k−1
6

−1
is real and positive. Now,
 one may diagonalize A as CDC where D = diag(λ1 , . . . , λk )
and C = v1 · · · vk . It follows that

γn⊤ = An γ0⊤

= CD n C −1 γ0⊤

= λn1 v1 · · · λn1 vk C −1 γ0⊤
= λn1 c1 v1 + . . . + λnk ck vk
where (c1 , . . . , ck )⊤ = C −1 γ0⊤ . Since |λ1 | > 1, |λ2 |, . . . , |λk | < 1, and v1 is real and positive, for a sufficiently large n we will have γn⊤ ≈ λn1 c1 v1 , and so the entries of γn⊤ will
either be all positive or all negative, depending on the sign of c1 . If c1 = 0, then γn⊤ = 0,
implying that γ0⊤ = 0.
For the last part of the proposition, if (xr )r∈Z 6= (0)r∈Z is nonnegative, then we only
need to use Operation 1, and so the k consecutive terms of (yr )r∈Z cannot be negative or
zero.
Proposition 3.2 A sequence (xr )r∈Z of nonnegative integers that is 0 almost everywhere
is k-equivalent to a sequence (yr )r∈Z of 0 and 1 with no k consecutive 1’s.
Proof Consider all sequences of nonnegative integers that are k-equivalent to (xr )r∈Z .
Recall that if (xr ) ∼k (yr ), then (xr ) · (λr1 ) = (yr ) · (λr1 ) where (λr1 ) is the primitive Fibonacci sequence. Let N be an integer such that (xr ) · (λr1 ) < λN
1 . Now, if a sequence
of nonnegative integers (yr ) is k-equivalent to (xr ), then we must have (yr ) · (λr1 ) < λN
1 .
r
Since (λ1 ) is strictly positive, it follows that yr = 0 for all r ≥ N. This allows us to
conclude that, among all the sequences of nonnegative integers that are k-equivalent to
(xr ), there must be one with the highest lexicographical order. We call this sequence
(yr )r∈Z and claim that it satisfies the conditions required.
Suppose that ys ≥ 2 for some s ∈ Z. We perform Operation 1 at n = s and Operation
2 at n = s + 1. This results in a sequence with higher lexicographical order than (yr ),
contradicting our choice of (yr ). Suppose now that ys−k = . . . = ys−2 = ys−1 = 1 for
some s ∈ Z. Perform Operation 2 at n = s yields a sequence with higher lexicographical
order, and once again that contradicts the choice of (yr ). We conclude that (yr ) consists
only of 0 and 1 with no k consecutive 1’s.
We illustrate the transformations given in Propositions 3.1 and 3.2 in an example
below.
Example 3.3 We let k = 3 and consider a doubly infinite sequence (xr ) that is zero
everywhere except x−1 = −2, x1 = −1, x2 = −2, and x4 = 1, i.e.,
(xr ) = (. . . , 0, 0, 0, 0, −2, 0, −1, −2, 0, 1, . . .).
We now transform (xr ) into a sequence that is positive at some 3 consecutive terms and

7

zero elsewhere.
(. . . , 0, 0, 0, 0, −2, 0, −1, −2, 0, 1, . . .) ∼3
∼3
∼3
∼3

(. . . , 0, 0, 0, 0, −2, 0, 0, −1, 1, 0, . . .)
(. . . , 0, 0, 0, 0, −2, 1, 1, 0, 0, 0, . . .)
(. . . , 0, 0, 0, 1, −1, 2, 0, 0, 0, 0, . . .)
(. . . , 0, 0, 2, 3, 1, 0, 0, 0, 0, 0, . . .).

Next, we transform (. . . , 0, 0, 2, 3, 1, 0, 0, 0, 0, 0, . . .) into a binary sequence with no 3 consecutive 1’s.
(. . . , 0, 0, 2, 3, 1, 0, 0, 0, 0, 0, . . .) ∼3 (. . . , 0, 0, 1, 2, 0, 1, 0, 0, 0, 0, . . .)
∼3 (. . . , 1, 1, 2, 1, 0, 1, 0, 0, 0, 0, . . .)
∼3 (. . . , 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, . . .).
Consider now a Fibonacci sequence of Gaussian integers
(Fr ) = ( . . . , −1 + 2i, 2, −1 − i, i, 1, 0, 1 + i, 2 + i, 3 + 2i, 6 + 4i, . . . . )
from Example 2.3. Note that all the above 3-equivalent sequences represent the same
quantity when multiplied by (Fr ). In particular, if (yr ) = (. . . , 0, 0, 2, 3, 1, 0, 0, 0, 0, 0, . . .)
and (zr ) = (. . . , 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, . . .), then
(xr ) · (Fr ) = (yr ) · (Fr ) = (zr ) · (Fr ) = −1 + i.
This, in fact, would hold for any other Fibonacci sequences (Fr ) of order 3.
The previous example illustrates a major strength of our approach–each equivalency
class represents the same quantity, given a Fibonacci sequence. If one can find a legitimate
Zeckendorf representation in an equivalency class, then, under any Fibonacci sequence,
the element represented by that class has a Zeckendorf decomposition. We finish this
section with a powerful corollary to Proposition 3.2 and another example. The following
result characterizes all elements that are Zeckendorf in a Fibonacci sequence (Fr ).
Corollary 3.4 Let (Fr ) be a Fibonacci sequence of order k. An element m is Zeckendorf
in (Fr ) if and only if m can be written as a finite sum (with multiplicities) of elements
from (Fr ).
Proof An element m is Zeckendorf in (Fr ) if it is a finite sum of elements from (Fr ).
The converse of this statement follows from Proposition 3.2.
Example 3.5 Consider the primitive Fibonacci sequence of order 2
. . . , ϕ−3 , ϕ−2 , ϕ−1 , 1, ϕ, ϕ2 , ϕ3 , . . . .
√

where ϕ = 1+2 5 is the golden ratio. The elements that are Zeckendorf in this sequence
are precisely positive elements in the ring Z[ϕ], and this numeration system is known as
golden ratio base.
8

Zeckendorf ’s Theorem for Free Z-Modules

4

Intuitively, if an element m is Zeckendorf in a Fibonacci sequence (Fr ) of order k, then it
is an integer combination of the initial terms (or, rather, any k consecutive terms) of (Fr ).
Integer span of these forms a module, so it is natural to attempt to represent every element
of a module using sequence elements. Subsection 4.1 deals with doubly infinite Fibonacci
sequences using tools developed in the last section. One-way Fibonacci sequences are
studied in Subsection 4.2 as a mean to achieve unique Zeckendorf decomposition.

4.1

Two-way Sequences

Corollary 3.4 lays a strong foundation for our work. While it characterizes elements that
are Zeckendorf in a sequence, it gives insufficient information on the algebraic structure
of the set of all elements that have a legitimate representation. The following theorem
now reverses the process. It gives a sufficient and necessary condition for every element
of a free Z-module M to be Zeckendorf in a Fibonacci sequence (Fr ).
Theorem 4.1 Let M be a free Z-module of rank l, and (Fr )r∈Z = (. . . , F−1 , F0 , F1 , . . .)
be a Fibonacci sequence of order k. Then, M is Zeckendorf in (Fr ) if and only if all of
the following conditions are satisfied.
1. Fi , . . . , Fi+k−1 span M for all i.
2. l + 1 ≤ k.
Proof We first remark that the integral span of Fi , . . . , Fi+k−1 is the same as the integral
span of Fi+1 , . . . , Fi+k since Fi + · · · + Fi+k−1 = Fi+k . Thus, Fi , . . . , Fi+k−1 spans M for
all i if and only if Fi , . . . , Fi+k−1 spans M for any i.
It is easy to see that the first condition is necessary. Since the elements of (Fr )r∈Z
are integer combinations of Fi , . . . , Fi+k−1, so must be any sums of the elements from
this sequence. It follows that Fi , . . . , Fi+k−1 span M. This readily implies l ≤ k. We will
now show that l cannot equal to k, thus establishing the necessity of the second condition.
Suppose that l = k, and let m be any nonzero element of M. Since both m and −m
are Zeckendorf in (Fr ), we have
m = (xr ) · (Fr )

and

− m = (yr ) · (Fr )

for some sequences (xr ), (yr ) of 0 and 1 with no k consecutive 1’s. Hence, 0 = (xr + yr ) ·
(Fr ). By Proposition 3.1, (xr + yr ) is k-equivalent to a sequence that is positive at some
k consecutive terms and zero elsewhere. Thus, we have
0 = (xr + yr ) · (Fr ) = (zr ) · (Fr ) = zi Fi + zi+1 Fi+1 + . . . + zi+k−1 Fi+k−1
for some i in which zi , zi+1 , . . . , zi+k−1 > 0. This, however, means that Fi , Fi+1 , . . . , Fi+k−1
are integrally dependent, and so they cannot span a module of rank l = k.

9

We are left to show that the two conditions are sufficient. Since F0 , . . . , Fk−1 span M
and l + 1 ≤ k, F1 , . . . , Fk−1 must be integrally dependent. That is, we may write
0 = x0 F0 + · · · + xk−1 Fk−1
where x0 , . . . , xk−1 are not all zeros. In other words, we have
0 = (xr ) · (F1 )
where (xr ) is zero everywhere but some k consecutive terms. We apply Proposition 3.1
and obtain a sequence (yr ) that is k-equivalent to (xr ) and contain k consecutive terms
of the same sign and zero elsewhere. Note that (yr ) cannot be zero everywhere since that
would imply that x0 = . . . = xk−1 = 0.
Suppose now that (yr ) is nonzero at the terms yi , . . . , yi+k−1. This means
0 = yi Fi + · · · + yi+k−1Fi+k−1
where either yi , . . . , yi+k−1 > 0 or yi , . . . , yi+k−1 < 0. Since Fi , . . . , Fi+k−1 span M, we can
write any element m ∈ M as
m = zi Fi + · · · + zi+k−1 Fi+k−1
where zi , . . . , zi+k−1 are integers. Now, we have
m = m + 0 · N = (zi + yi N)Fi + · · · + (zi+k−1 + yi+k−1N)Fi+k−1
for all integer N. For a sufficiently large (and possibly negative) N, the terms zi +
yi N, . . . , zi+k−1 + yi+k−1N will all be positive, and it follows from Corollary 3.4 that m is
Zeckendorf in (Fr ). This completes the proof of the theorem.
Corollary 4.2 Let (Fr )r∈Z = (. . . , F−1 , F0 , F1 , . . .) be a Fibonacci sequence of order k. If
F1 , . . . , Fk are integrally dependent, then every element in the integral span of F1 , . . . , Fk
is Zeckendorf in (Fr ).
In view of Theorem 4.1, every integer has a (classical) Zeckendorf representation since
Z is a module over itself with rank 1, and the negaFibonacci sequence is of order 2 with
F0 = 0 and F1 = 1. In fact, the same result would hold as long as F0 and F1 are relatively
prime (and hence span Z integrally). This is technically the case for the Lucas sequence
where L0 = 2 and L1 = 1. Next, we give an example for the case of Gaussian integers.
Example 4.3 Consider a Fibonacci sequence
. . . , −4 + 4i, 5 + i, −2 − 3i, −1 + 2i,
2, −1 − i,
i,
1,
0, 1 + i,
2 + i,
3 + 2i, 6 + 4i, 11 + 7i, 20 + 13i, 37 + 24i, . . . .

10

from Example 2.3. Every Gaussian integer can be written as a sum of elements from this
sequence with no 3 consecutive terms. For instance,
−2 = (−2 − 3i) + (−1 + 2i) + (i) + (1)
−1 = (−1 − i) + (i)
2 = (2)
3 = (2) + (1)
1 + 2i = (−1 + 2i) + (2)
−2 + i = (−1 + 2i) + (−1 − i)

−2i = (−2 − 3i) + (2) + (i)
−i = (−1 − i) + (1)
2i = (−1 + 2i) + (1)
3i = (−1 + 2i) + (i) + (1)
1 − 2i = (−2 − 3i) + (i) + (1)
−2 − i = (−2 − 3i) + (−1 + 2i) + (1).

One may observe that (i) + (1) = (1 + i), and so Zeckendorf representation for a Gaussian
integer in this sequence is not unique. Nonetheless, we will see in the next subsection how
certain adjustments can make unique representation possible.
On the contrary, no Fibonacci sequence of order 2 can generate all Gaussian integers.
For example, −1 − i cannot be written as a sum of elements from the sequence
. . . , −21 + 13i, 13 − 8i, −8 + 5i, 5 − 3i, −3 + 2i, 2 − i, −1 + i,
1,
i,
1 + i, 1 + 2i,
2 + 3i, 3 + 5i, 5 + 8i, . . . .
Note that Corollary 4.2 does not apply here since 1 and i are not integrally dependent.
However, it follows from Corollary 3.4 that every element of the form a + bi, a, b ∈ Z+ ,
is Zeckendorf in this sequence.

4.2

One-way Sequences and Unique Representation

So far we have left out one very important aspect of Zeckendorf’s Theorem: the uniqueness
property. It is known that every positive integer can be written uniquely as a sum of
nonconsecutive elements from the Fibonacci sequence
1, 2, 3, 5, 8, 13, 21, 34, . . . ,
and every integer can be written uniquely as a sum of nonconsecutive elements from the
negaFibonacci sequence
. . . , 34, −21, 13, −8, 5, −3, 2, −1, 1.
However, the uniqueness property obviously no longer holds for the two-way sequence
. . . , 34, −21, 13, −8, 5, −3, 2, −1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .
since this sequence contains elements that are equal. In this subsection, we establish
analogous results for Fibonacci sequences of higher order. The key ingredient of this
development is Corollary 4.5, which states that binary sequences with no k consecutive
1’s cannot be k-equivalent.
Lemma 4.4 Let a be an integer, and let (λr1 )r∈Z be the primitive Fibonacci sequence of
order k. Then,
X
λr1 = λa1 .
r<a
k ∤ a−r

11

Proof We have
X

λr1 =

r<a
k∤a−r

X

λr1 −

X

λr1

r<a
k|a−r

r<a

λa
λa1
− k 1
λ1 − 1 λ1 − 1
 k−1

(λ1 + λ1k−2 + . . . + 1) − 1
a
= λ1
λk1 − 1

 k
λ1 − 1
a
= λ1
λk1 − 1
= λa1 .

=

Corollary 4.5 Let (xr ) and (yr ) be doubly infinite binary sequences with no k consecutive
1’s that are 0 almost everywhere.
1. If (xr ) ≻k (yr ), then (xr ) · (λr1 ) > (yr ) · (λr1 ).
2. If (xr ) ∼k (yr ), then (xr ) = (yr ).
Proof Suppose that (xr ) ≻k (yr ), and let a be the largest index where (xr ) and (yr ) are
not equal. It follows that (xa ) = 1, (ya ) = 0, and
X
(xr ) · (λr1 ) ≥ λa1 +
xr λr1
r>a

=

X

r<a
k∤a−r

>

X

λr1 +

X

xr λr1

r>a

yr λr1 +

X

yr λr1 = (yr ) · (λr1 ).

r>a

r≤a

Now, if (xr ) 6= (yr ), then we may assume without loss of generality that (xr ) ≻k (yr ).
This means (xr ) · (λr1 ) > (yr ) · (λr1 ), and so (xr ) ≁k (yr ). This readily establishes part ii.
Typically, (xr ) ∼k (yr ) means that (xr ) · (Fr ) = (yr ) · (Fr ), and so (xr ) and (yr ) are two
representations of the same element. Corollary 4.5 now allows us to identify Fibonacci
sequences (or parts of) that permit unique Zeckendorf representation: if a sequence (Fr )
has the property that (xr )·(Fr ) = (yr )·(Fr ) implies (xr ) ∼k (yr ), then any element that is
Zeckendorf in (Fr ) will have a unique representation. Since we are interested in generating
every element in a Z-module, we look into generalizing negaFibonacci sequence, which is
technically a one-sided Fibonacci sequence to the left whose first excluded term is 0. It
turns out that this observation generalizes well to modules.
Theorem 4.6 Let k ≥ 2 be an integer, and M be a free Z-module of rank k − 1. Let
(Fr )r∈Z = (. . . , F−1 , F0 , F1 , . . .) be a Fibonacci sequence of order k where F0 = 0 and
12

F−k+1 , . . . , F−1 span M. Then, every element m ∈ M can be uniquely written as a finite
sum of elements from the one-way sequence
. . . , F−3 , F−2 , F−1
with no k consecutive terms.
Proof We first prove the existence. Let m ∈ M, and write
m = x−k+1 F−k+1 + . . . + x−2 F−2 + x−1 F−1
where x−k+1 , . . . , x−2 , x−1 are integers. We extend x−k+1 , . . . , x−2 , x−1 to a sequence
(xr )r∈Z that is zero everywhere except r = −k+1, . . . , −2, −1. Now, consider all sequences
of integers that are k-equivalent to (xr )r∈Z such that the terms with positive index are zero
and the terms with negative index are nonnegative. Such a sequence exists since one may
apply Operation 1 from Definition 2.4 to (xr ) at n = 0 for max{|x−k+1 |, . . . , |x−2 |, |x−1 |}
times. Denote by (yr )r∈Z the sequence that has the aforementioned properties with highest lexicographical order. We claim that (yr ) gives a Zeckendorf representation for m in
. . . , F−3 , F−2 , F−1 .
P
We first note that yr = 0 for r ∈ Z+ and F0 = 0, and so (yr ) · (Fr ) = r∈Z− yr Fr .
If ys ≥ 2 for some s ∈ Z− , then we perform Operation 1 at n = s and Operation
2 at n = s + 1 to obtain a sequence with higher lexicographical order than (yr ). If
ys−k+1 = . . . = ys−1 = ys = 1 for some s ∈ Z− , then performing Operation 2 at n = s
results in a sequencePwith higher lexicographical order. Thus, (yr ) is binary with no k
consecutive 1’s, and r∈Z− yr Fr is a Zeckendorf representation for m in . . . , F−3 , F−2 , F−1 .
Suppose now for the sake of contradiction that there exists an element m ∈ M that has
two representations as a finite sum of elements from the sequence . . . , F−3 , F−2 , F−1 with
no k consecutive terms. That is, we have m = (xr ) · (Fr ) = (yr ) · (Fr ) where (xr ) 6= (yr )
are doubly infinite binary sequences which are zero for r ≥ 0. Now, we keep applying
either Operation 1 or 2 to eliminate the leftmost nonzero term of (xr ) and (yr ) and obtain
sequences (x′r ) and (yr′ ) which are zero everywhere except for r = −k + 1, . . . , −2, −1, 0.
This means
(x′r ) · (Fr ) = x′−k+1 F−k+1 + . . . + x′−2 F−2 + x′−1 F−1 + x′0 F0
and
′
′
′
(yr′ ) · (Fr ) = y−k+1
F−k+1 + . . . + y−2
F−2 + y−1
F−1 + y0′ F0 .

are both equal to m. Since F−k+1, . . . , F−1 span M of rank k − 1, we must have x′r = yr′
for r = −k + 1, . . . , −2, −1. If x′0 = y0′ , then (xr ) ∼k (x′r ) = (yr′ ) ∼k (yr ), and so (xr )
and (yr ) must be the same from Corollary 4.5. Otherwise, we assume without loss of
generality that x′0 > y0′ . We now have
(xr ) · (λr1 ) − (yr ) · (λr1 ) = (x′r ) · (λr1 ) − (yr′ ) · (λr1 )
= (x′0 − y0′ )λ01
≥ 1.
13

Since (yr ) is binary, it follows that (xr ) · (λr1 ) ≥ 1. However, we see from Lemma 4.4 that
X
(xr ) · (λr1 ) <
λr1 = λ01 = 1,
r<0
k∤−r

which is a contradiction. This completes the proof of the theorem.
Obviously, the usual negaFibonacci sequence serves as an instance of Theorem 4.6.
We give another example using Gaussian integers.
Example 4.7 Consider a Fibonacci sequence
. . . , −4 + 4i, 5 + i, −2 − 3i, −1 + 2i,
2, −1 − i,
i,
1,
0, 1 + i,
2 + i,
3 + 2i, 6 + 4i, 11 + 7i, 20 + 13i, 37 + 24i, . . . .
from Example 2.3 and 4.3. One can see that every representation given in Example 4.3
only involve terms from the sequence
. . . , −4 + 4i, 5 + i, −2 − 3i, −1 + 2i, 2, −1 − i, i, 1.
In fact, every Gaussian integer can be uniquely written as a sum of elements from this
sequence with no 3 consecutive terms. This property will be exploited when we develop
Fibonacci coding for Gaussian integers in Example 5.1 in the next section.

5

Fibonacci Coding for Free Z-Modules

We first give a quick overview of applications of Zeckendorf’s theorem in data storage
and transmission. Suppose that arbitrary positive integers n1 , n2 , . . . , nl are to be sent
over a binary channel. One simple way to do this is to encode each integer using its
base-2 representation and send the corresponding string of 0 and 1 over the channel. An
obvious problem with this approach is that the receiver needs to know the length of each
message a priori. It is possible to also send the length of each message over the channel,
resulting in what is technically called logarithmic ramp (see, for example, [10]). On the
other hand, if codes of fixed length are used, then it is not possible to send large integers,
and at the same time it is wasteful if a lot of small integers are to be sent. Finally, all the
above schemes are vulnerable to insertion and deletion errors; if a bit fails to reach the
receiver or an extraneous bit is picked up, then all of the subsequent messages may not be
decoded correctly. A popular alternative approach is to use variable-length prefix codes.
Here, the number of bits in each codeword varies, and a receiver tell each codeword apart
using some special properties from the design of the code. We refer the readers to [27]
for more details and discuss next the case of Fibonacci coding.
Recall that we initialize the classical Fibonacci sequence with F0 = 0 and F1 =
1. To encode a positive integer n, we appeal to Zeckendorf’s theorem and write n as
P
t
r=1 ar Fr+1 . Then, the Fibonacci coding of n is a1 a2 . . . ar 1.

14

Message
1
2
3
4
5
6
7
8
9
10
11
12

Representation
1
2
3
1+3
5
1+5
2+5
8
1+8
2+8
3+8
1+3+8

Codeword
11
011
0011
1011
00011
10011
01011
000011
100011
010011
001011
101011

Table 1: Fibonacci code for n = 1, 2, . . . , 12
Since the classical Zeckendorf representation contains no two consecutive terms, each
codeword of the Fibonacci code contains exactly one instance of “11” at the end. Thus,
if several codewords from Fibonacci code are to be sent sequentially over a channel, one
can look for “11” and mark that as the end of a codeword. For example, 01011111011
can be uniquely decoded as 01011 11 1011. Fibonacci code is robust against insertion
and deletion errors in that the separator “11” will make the error local. In addition, it is
not hard to see that an extra bit may be added so that it is possible to represent negative
integers. Alternatively, one may instead use negaFibonacci numbers to begin with.
We now wish to develop an analogous scheme for messages that are from a module.
Modules encompass composite message spaces such as complex numbers and lattices,
which find use in Quadrature Amplitude Modulation (QAM) and wireless communications. See, for example, [29, 33]. We see from Theorem 4.6 that it is possible to write
any element of a module as a sum of entries from a sequence using no k consecutive
terms. This suggests Fibonacci coding for modules with the use of k consecutive 1’s as a
separator. The intuition formalizes into Algorithm 1. Here, we denote k consecutive 1’s,
11
. . . 1}, by 1k .
| {z
k

Note that the coefficients are encoded in reverse order, and each codeword contains
exactly one instance of 1k at the end. Thus, when codewords are sent sequentially over
a channel, the receiver only needs to look for the occurrence of 1k to separate each
codeword. In addition, note that the algorithm simply mimics the arguments given
in the proof of Theorem 4.6. This guarantees that the algorithm terminates since the
operations performed in Step
P 4 and 5 increases the lexicographical order of the sequence.
At every step, the value r∈Z− xr Fr remains unchanged. This fact makes the decoding,
which is outlined as Algorithm 2, easy.
To illustrate, we consider once again the Gaussian Fibonacci sequence given in Examples 2.3, 4.3, and 4.7.
Example 5.1 Consider the Fibonacci sequence
. . . , −4 + 4i, 5 + i, −2 − 3i, −1 + 2i, 2, −1 − i, i, 1,
15

Algorithm 1 Fibonacci Encoding
Input: A Fibonacci sequence . . . , F−3 , F−2 , F−1 of order k where F−k + . . . + F−1 = 0
and F−k+1 , . . . , F−1 span a free Z-module M of rank k − 1, and an element m ∈ M.
Output: Fibonacci code for m.
1: If m = 0, output 1k . END.
2: Write m as
x−k+1 F−k+1 + . . . + x−2 F−2 + x−1 F−1 .
3:
4:
5:
6:

Set x0 = 0 and xr = 0 for r ≤ −k.
If x̌ = min{x−k+1 , . . . , x−2 , x−1 } < 0, subtract x̌ from x−k , x−k+1 , . . . , x−2 , x−1 .
Find the largest index s < 0 such that xs−k+1 , . . . , xs ≥ 1. If there is none, go to Step
5. Otherwise, subtract 1 from xs−k+1 , . . . , xs , add 1 to xs−1 , and repeat this step.
Find the largest index s < 0 such that xs ≥ 2. If there is none, go to Step 6.
Otherwise, subtract 2 from xs , add 1 to xs−k and xs+1 , and go to Step 4.
Find the smallest index s < 0 such that xs = 1. Output x−1 x−2 x−3 . . . xs+2 xs+1 01k .
END.

Algorithm 2 Fibonacci Decoding
Input: A Fibonacci sequence . . . , F−3 , F−2 , F−1 of order k, and a binary string
x1 x2 x3 . . . xs−1 xs 1k .
Output: An element m.
1: If x1 x2 x3 . . . xs−1 xs is empty, output 0. END.
2: Output x1 F−1 + x2 F−2 + . . . + xs−1 F−s+1 + F−s . END.
and let m = −2 + 3i. To encode, we initialize x−2 = 3, x−1 = −2 and obtain x−3 = 2,
x−2 = 5, x−1 = 0 after Step 2. We shorthand this sequence as 2, 5, 0. Iterations of Step
3 and 4 now yield
2, 5, 0 → 1, 0, 2, 3, 1 → 1, 0, 1, 2, 0 → 2, 0, 1, 0, 1 → 1, 0, 0, 0, 1, 1, 0, 1.
Thus, m = −2 + 3i is encoded as 10110000111. This string can then be decoded as
F−1 + F−3 + F−4 + F−8 = 1 + (−1 − i) + 2 + (−4 + 4i) = −2 + 3i. The table below gives
Fibonacci code under this sequence for some Gaussian integers.
b = 2i
b=i
b=0
b = −i
b = −2i

a = −2
a = −1
a=0
a=1
a=2
01100111 00000111 10000111 00010111
1001011
00100111 10100111
00111
10111
0100111
110010111
010111
111
0111
0000111
100010111
000111
100111
0010111
1010111
010000111 110000111 010100111 110000111 0110010111
Table 2: Fibonacci code for a + b using the sequence
. . . , −4 + 4i, 5 + i, −2 − 3i, −1 + 2i, 2, −1 − i, i, 1.

Clearly, one may replace i in Example 5.1 by any other quadratic integer and obtain
a Fibonacci coding for the corresponding ring of quadratic integers. Next, we give an
example of Fibonacci coding for a lattice.
16

Example 5.2 Consider the lattice E8 given by

P
E8 = x ∈ Z8 ∪ (Z + 21 )8 | xi ≡ 0

(mod 2) .

This lattice provides optimal sphere packing and kissing number in 8 dimensions and has
many other interesting properties [8]. We set the basis for E8 as
v1
v3
v5
v7

= (2, 0, 0, 0, 0, 0, 0, 0)
= (0, −1, 1, 0, 0, 0, 0, 0)
= (0, 0, 0, −1, 1, 0, 0, 0)
= (0, 0, 0, 0, 0, −1, 1, 0)

v2
v4
v6
v8

= (−1, 1, 0, 0, 0, 0, 0, 0)
= (0, 0, −1, 1, 0, 0, 0, 0)
= (0, 0, 0, 0, −1, 1, 0, 0)
= ( 12 , 21 , 21 , 12 , 21 , 21 , 21 , 12 )

and consider a Fibonacci sequence of order 9 given by
. . . , 2v2 − v1 , 2v1 , −v1 − v2 − v3 − v4 − v5 − v6 − v7 − v8 , v8 , v7 , v6 , v5 , v4 , v3 , v2 , v1 .
It follows from Theorem 4.6 that every element of E8 can be written as a sum of elements
from this sequence with no 9 consecutive terms. Let m = ( 12 , 2 21 , 12 , 21 , 21 , 21 , 21 , 12 ) ∈ E8 .
Then, m = v1 + 2v2 + 2v3 + v8 and can be encoded as 010000000110111111111.

6

Conclusion

In this paper, we generalize Zeckendorf’s theorem to modules. The notion of equivalent
sequences allows us to identify elements that can be represented as a sum of elements
from a Fibonacci sequence of order k with no k consecutive terms. This results in necessary and sufficient conditions for a Fibonacci sequence of higher order to generate a
module. In addition, under certain circumstances the representation is unique, allowing
us to establish Fibonacci coding for modules. Future work involves identifying other conditions to which the representation remains unique. Under such environments, one can
view Zeckendorf representation as a number system and develop generalized Zeckendorf
arithmetic. It would also be interesting to study the proposed coding algorithm from the
perspective of data compression and computational complexity.

References
[1] A. Apostolico, A. Fraenkel, Robust Transmission of Unbounded Strings Using Fibonacci Representations, IEEE Transactions on Information Theory 33 (1987), 238–
245.
[2] I. Ben-Ari and S. J. Miller, A Probabilistic Approach to Generalized Zeckendorf
Decompositions, SIAM Journal on Discrete Mathematics 30 (2016), no. 2, 1302–
1332.
[3] Berzsenyi, Gaussian Fibonacci Numbers, Fibonacci Quarterly 15 (1977), no. 3, 233–
236.

17

[4] A. Best, P. Dynes, X. Edelsbrunner, B. McDonald, S. J. Miller, C. TurnageButterbaugh, and M. Weinstein, Gaussian Behavior of the Number of Summands in
Zeckendorf Decompositions in Small Intervals, Fibonacci Quarterly 52 (2014), no.
5, 47–53.
[5] M. W. Bunder, Zeckendorf Representations Using Negative Fibonacci Numbers, Fibonacci Quarterly 30 (1992), 111–115.
[6] L. Carlitz, V. E. Hoggatt, Jr., and R. Scoville, Fibonacci Representations of Higher
Order, Fibonacci Quarterly 10 (1972), no. 1, 43–69.
[7] J. Cigler, Some Algebraic Aspects of Morse Code Sequences, Discrete Mathematics
and Theoretical Computer Science 6 (2003), 55–68.
[8] J. Conway, and N.J.A. Sloane, Sphere Packings, Lattices and Groups, Springer.
[9] P. Demontigny, T. Do, A. Kulkarni, S. J. Miller, D. Moon, and U. Varma, Generalizing Zeckendorf’s Theorem to f -decompositions, Journal of Number Theory 141
(2014), 136–158.
[10] S. Even and M. Rodeh, Economical Encoding of Commas Between Strings, Communications of the ACM 21 (1978), 315–317.
[11] G. D. Forney, Coset Codes–Part I: Introduction and Geometrical Classification,
IEEE Trans. Inform. Theory 34 (1988), no. 5, 1123–1151.
[12] A. Fraenkel and S. Klein, Robust Universal Complete Codes As Alternatives to
Huffman Codes, Technical Report CS85-16, The Weizmann Institute of Science,
Rehovot, 1985.
[13] A. Fraenkel and S. Klein, Robust Universal Complete Codes for Transmission and
Compression, Discrete Applied Mathematics 64 (1996), 31–55.
[14] I. J. Good, Complex Fibonacci and Lucas Numbers, Continued Fractions, and the
Square Root of the Golden Ratio, Journal of the Operational Research Society 43
(1992), no. 8, 837–842.
[15] P. J. Grabner, R. F. Tichy, I. Nemes, and A. Pethő, Generalized Zeckendorf Expansions, Applied Mathematics Letters 7 (1994), no. 2, 25–28.
[16] E. Halsey, The Fibonacci Number Fu where u is not an Integer, Fibonacci Quarterly
3 (1965), no. 2, 147–152.
[17] C. J. Harman, Complex Fibonacci Numbers, Fibonacci Quarterly 19 (1981), no. 1,
82–86.
[18] D. Huffman, A Method for the Construction of Minimum Redundancy Codes, Proceedings of the IRE (1952), 1098–1101.
[19] J. H. Jordan, Gaussian Fibonacci and Lucas Numbers, Fibonacci Quarterly 3 (1965),
no. 4, 315–318.
18

[20] I. Kátai, J. Szabó, Canonical Number Systems for Complex Integers, Acta Sci. Math.,
37 (1975), 255–260.
[21] S. T. Klein and D. Shapira, Random Access to Fibonacci Encoded Files, Discrete
Applied Mathematics 212 (2016), 115–128.
[22] D. E. Knuth, Fibonacci Multiplication, Applied Mathematics Letters 1 (1988), no.
1, 57–60.
[23] C. G. Lekkerkerker, Voorstelling van natuurlyke getallen door een som van getallen
van Fibonacci, Simon Stevin 29 (1951-1952), 190–195.
[24] E. P. Miles, Jr., Generalized Fibonacci Numbers and Associated Matrices, American
Math. Monthly, 67 (1960), 745–57.
[25] S. J. Miller and Y. Wang, From Fibonacci Numbers to Central Limit Type Theorems,
Journal of Combinatorial Theory, Series A 119 (2012), no. 7, 1398–1413.
[26] F. D. Parker, A Fibonacci function, Fibonacci Quarterly 6 (1968), no. 1, 1–2.
[27] D. Salomon, Data Compression The Complete Reference, Third Edition, Springer–
Verlag, New York, 2004.
[28] S. Sato, Fibonacci Sequence and its Generalizations Hidden in Algorithms for Generating Morse Codes, Applications of Fibonacci Numbers: Volume 5 Proceedings of
‘The Fifth International Conference on Fibonacci Numbers and Their Applications’
(1993), 481–486.
[29] M. Schwartz, Mobile Wireless Communications, Cambridge University Press, 2005.
[30] N. Utgoff, A generalization of Zeckendorf’s Theorem, preprint.
[31] J. Walder, M. Kratky, and J. Platos, Fast Fibonacci Encoding Algorithm, DATESO
(2010).
[32] J. Walder, M. Kratky, R. Baca, J. Platos, and V. Snasel, Fast Decoding Algorithms
for Variable-Lengths Codes, Information Sciences 183 (2012), 66–91.
[33] R. Zamir, Lattice Coding for Signals and Networks, Cambridge University Press,
2014.

19

