Fibonacci Word - Substitution Rules

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.

A closed form expression for the so-called rabbit sequence:

The nth digit of the word is where is the golden ratio and is the floor function.