Namespaces
Variants
Actions

Fibonacci word

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

An infinite sequence of symbols over a binary alphabet defined by a recursion related to that of the Fibonacci numbers.

Let $A$ be the alphabet $\{a,b\}$ and define a sequence of finite words $f_n$, $n \ge 1$ by $f_1 = a$, $f_2 = ab$ and $f_{n+1} = f_n \cdot f_{n-1}$ where $\cdot$ denotes concatenation. The Fibonacci word $\mathcal{F}$ is defined as $$ \mathcal{F} = f_1 \cdot f_2 \cdot \cdots \cdot f_n \cdot \cdots $$ and, since $f_n$ is an initial factor of $f_{n+1}$ we may also obtain $\mathcal{F}$ as the limit of the $f_n$. We have $$ \mathcal{F} = a ab aab abaab aababaab abaabaababaab \ldots \ . $$

The Fibonacci word has complexity function $c_{\mathcal{F}}(n) = n+1$ and hence is a Sturmian sequence. It is a morphic word, a fixed point of the endomorphism $a \mapsto ab$, $b \mapsto a$.

References

  • Allouche, Jean-Paul; Shallit, Jeffrey Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press (2003) ISBN 978-0-521-82332-6 Zbl 1086.11015
  • Lothaire, M. Combinatorics on Words (2nd ed.) Encyclopedia of Mathematics and Its Applications 17 Cambridge University Press (1997) ISBN 0-521-59924-5 Zbl 0874.20040
  • Lothaire, M. Algebraic Combinatorics on Words Encyclopedia of Mathematics and Its Applications 90, Cambridge University Press (2011 [2002]) ISBN 978-0-521-18071-9 Zbl 1221.68183
  • Pytheas Fogg, N. (ed.) Substitutions in dynamics, arithmetics and combinatorics Lecture Notes in Mathematics 1794 Springer (2002) ISBN 978-3-540-44141-0 Zbl 1014.11015
How to Cite This Entry:
Fibonacci word. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Fibonacci_word&oldid=54148