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.

Enumerating items from the above definition produces: 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, ... (sequence A003849 in the OEIS) The nth digit of the word is

As a consequence, the infinite Fibonacci word can be characterized by a cutting sequence of a line of slope

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.

A closed form expression for the so-called rabbit sequence: The nth digit of the word is

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 Sn to be Fn +2, the (n +2)nd Fibonacci number.