Fibonacci word

From Wikipedia, the free encyclopedia

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

Contents

[edit] Definition

Let S0 be "0" and S1 be "01". Now Sn = Sn − 1Sn − 2 (the concatenation of the previous sequence and the one before that). The Fibonacci word is the limit S_{\infty}.

[edit] The sequence

We have:

S0    0

S1    0, 1

S2    0, 1, 0

S3    0, 1, 0, 0, 1

S4    0, 1, 0, 0, 1, 0, 1, 0

S5    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, ...

[edit] Closed-form expression for individual digits

The nth digit of the word is \left\lfloor {\left( {n + 2} \right)\,{\varphi \over {1 + 2\,\varphi }}} \right\rfloor - \left\lfloor {\left( {n + 1} \right)\,{\varphi \over {1 + 2\,\varphi }}} \right\rfloor and \varphi is the golden ratio and \left\lfloor x \right\rfloor is the floor function (see OEIS' A3849).

[edit] Substitution rules

Another way of going from Sn to Sn + 1 is to replace each symbol 0 in Sn with the pair of consecutive symbols 0, 1 in Sn + 1, and to replace each symbol 1 in Sn with the single symbol 0 in Sn + 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.

[edit] 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 Sn to be Fn + 2, the (n + 2)th Fibonacci number. Also the number of 1s in Sn is Fn + 1 and the number of 0s in Sn is Fn.

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