Home

FibonacciWort

FibonacciWort, or the Fibonacci word, is an infinite binary sequence that appears in combinatorics on words and symbolic dynamics. It can be defined by a simple recursive construction or as the fixed point of a morphism, linking it to the Fibonacci numbers and the golden ratio.

One standard construction starts with F0 = 0 and F1 = 01, and for n ≥ 1 defines Fn+1

FibonacciWort is a Sturmian word, characterized by minimal aperiodic complexity. Its subword complexity is p(n) = n

Applications and connections include theoretical computer science and symbolic dynamics, where FibonacciWort serves as a canonical

=
Fn
Fn-1.
The
infinite
word
w
is
the
limit
of
this
sequence
as
n
grows.
Equivalently,
w
is
the
unique
fixed
point
of
the
morphism
φ
on
{0,1}
given
by
φ(0)
=
01
and
φ(1)
=
0,
with
w
=
φ(w).
The
initial
digits
of
w
begin
as
010010100100101001010010010100...
+
1
for
all
n
≥
1,
meaning
there
is
precisely
one
new
factor
of
each
length
n.
It
is
a
balanced
word:
for
any
two
factors
of
the
same
length,
the
numbers
of
0s
(and
of
1s)
differ
by
at
most
one.
The
word
also
arises
as
a
mechanical
(or
rotation)
word
with
slope
α
=
1/φ^2,
approximately
0.381966,
connecting
its
structure
to
irrational
rotations
on
the
circle.
example
of
a
nonperiodic,
highly
regular
sequence.
It
is
used
to
study
substitution
systems,
factor
complexity,
and
morphic
words,
and
it
provides
a
bridge
between
combinatorics
on
words
and
number-theoretic
concepts
related
to
the
Fibonacci
sequence
and
the
golden
ratio.
References
include
standard
texts
on
combinatorics
on
words,
such
as
works
by
Lothaire
and
related
survey
papers
on
Sturmian
words.