Fibonacci word

The Fibonacci word is a specific infinite sequence of binary digits (or symbols from any two-letter alphabet).

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 Fibonacci word is the limit $S\_\{infty\}$.

The sequence

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 sequence 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 $leftlfloor\; \{left(\; \{n\; +\; 2\}\; ight),\{varphi\; over\; \{1\; +\; 2,varphi\; \}\; ight\; floor\; -\; leftlfloor\; \{left(\; \{n\; +\; 1\}\; ight),\{varphi\; over\; \{1\; +\; 2,varphi\; \}\; ight\; floor$ and $varphi$ is the golden ratio and $leftlfloor\; x\; ight\; floor$ is the floor function (see [http://www.research.att.com/~njas/sequences/A3849 OEIS' A3849] ).

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

The Fibonacci word is a famous example of a Sturmian word.