Fibonacci word

A Fibonacci word is a specific sequence of binary digits (or symbols from any two-letter alphabet). The Fibonacci word is formed by repeated concatenation in the same way that the Fibonacci numbers are formed by repeated addition.

The name “Fibonacci word” has also been used to refer to the members of a formal language L consisting of strings of zeros and ones with no two repeated ones. Any prefix of the specific Fibonacci word belongs to L, but so do many other strings. L has a Fibonacci number of members of each possible length.

Definition

Let $S_{0}$ be "0" and $S_{1}$ be "01". Now $S_{n}=S_{n-1}S_{n-2}$ (the concatenation of the previous sequence and the one before that).

The infinite Fibonacci word is the limit $S_{\infty }$ .

The Fibonacci words

We have:

$S_{0}$ 0

$S_{1}$ 0, 1

$S_{2}$ 0, 1, 0

$S_{3}$ 0, 1, 0, 0, 1

$S_{4}$ 0, 1, 0, 0, 1, 0, 1, 0

$S_{5}$ 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1

...

The first few elements of the infinite Fibonacci word are:

0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, ...

Closed-form expression for individual digits

The n^th digit of the word is $2+\left\lfloor {\left({n+1}\right)\,\varphi }\right\rfloor -\left\lfloor {\left({n+2}\right)\,\varphi }\right\rfloor$ where $\varphi$ is the golden ratio and $\left\lfloor x\right\rfloor$ is the floor function (sequence A003849 in the OEIS).

Substitution rules

Another way of going from S_n to S_n + 1 is to replace each symbol 0 in S_n with the pair of consecutive symbols 0, 1 in S_n + 1, and to replace each symbol 1 in S_n with the single symbol 0 in S_n + 1.

Alternatively, one can imagine directly generating the entire infinite Fibonacci word by the following process: start with a cursor pointing to the single digit 0. Then, at each step, if the cursor is pointing to a 0, append 1, 0 to the end of the word, and if the cursor is pointing to a 1, append 0 to the end of the word. In either case, complete the step by moving the cursor one position to the right.

A similar infinite word, sometimes called the rabbit sequence, is generated by a similar infinite process with a different replacement rule: whenever the cursor is pointing to a 0, append 1, and whenever the cursor is pointing to a 1, append 0, 1. The resulting sequence begins

0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, ...

However this sequence differs from the Fibonacci word only trivially, by swapping 0's for 1's and shifting the positions by one.

Discussion

The word is related to the famous sequence of the same name (the Fibonacci sequence) in the sense that addition of integers in the inductive definition is replaced with string concatenation. This causes the length of S_n to be F_n + 2, the (n + 2)th Fibonacci number. Also the number of 1s in S_n is F_n + 1 and the number of 0s in S_n is F_n.

Other properties

The Infinite Fibonacci word is not periodic and not ultimately periodic.
The last two letters of a Fibonacci word are alternatively "01" and "10"
Suppressing the last two letters of a Fibonacci word, or prefixing the complement of the last two letters, creates a palindrome. Example: 01 $S_{6}$ = 0101001010 is a palindrome.
In the infinite Fibonacci word, the ratio (number of letters)/(number of zeroes) is $\phi$ , the golden ratio, as is the ratio of zeroes to ones.
The infinite Fibonacci word is "balanced": Take two factors of the same length anywhere in the Fibonacci word. The difference between the number of "0" in any of them and the number of "0" in the other one never exceeds 1.
The subwords 11 and 000 never occur.
The infinite Fibonacci word contains k+1 distinct subwords of length k. Example: There are 4 distinct subwords of length 3 : "001", "010", "100" and "101". Being also non-periodic, it is then of "minimal complexity".
The infinite Fibonacci word is recurrent; that is, every subword occurs infinitely often.
If $u$ is a subword of the infinite Fibonacci word, then so is its reversal, denoted $u^{R}$ .
If $u$ is a subword of the infinite Fibonacci word, then the least period of $u$ is a Fibonacci number.
The concatenation of two successive Fibonacci words is "almost commutative". $S_{n+1}=S_{n}S_{n-1}$ and $S_{n-1}S_{n}$ differ only by their last two letters.
The infinite Fibonacci word is the most famous Sturmian word. Its slope equals $1/\phi ^{2}$ .
As a consequence, the infinite Fibonacci word can be characterized by a cutting sequence of a line of slope $\phi$ or $\phi -1$ . See figure above.
The number 0.010010100..., whose decimals are built with the digits of the infinite Fibonacci word, is transcendental.
The letters "1" can be found at the positions given by the successive values of the Upper Wythoff sequence (OEIS A001950): $\lfloor n\phi ^{2}\rfloor$
The letters "0" can be found at the positions given by the successive values of the Lower Wythoff sequence (OEIS A000201): $\lfloor n\phi \rfloor$
The infinite Fibonacci word can contain repetitions of 3 successive identical subwords, but never 4. The infinite Fibonacci word contains at most $2+\phi =3.618$ repetitions. It is the smallest index (or critical exponent) among all Sturmian words.
The infinite Fibonacci word is often cited as the worst case for algorithms detecting repetitions in a string.
The infinite Fibonacci word is the standard word generated by the directive sequence (1,1,1,....).

References

Lothaire, M (1997), Combinatorics on Words, Cambridge Mathematical Library, ISBN 978-0521599245.

Allouche, Jean-Paul; Shallit, Jeffrey (2003), Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, ISBN 9780521823326.

External links

A detailed and accessible description, on Ron Knott's site
Repetitions in the infinite Fibonacci word, by Mignosi and Pirillo
Sequence OEIS: A003849 The Fibonacci word in the On-Line Encyclopedia of Integer Sequences
The Rabbit sequence on Mathworld
Fibonacci Word (First 200,000 bits) on YouTube