Fibonacci word

From Encyclopedia of Mathematics
Jump to: navigation, search

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$.


How to Cite This Entry:
Fibonacci word. Encyclopedia of Mathematics. URL: