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

1 Definition
2 The sequence
3 Closed-form expression for individual digits
4 Substitution rules
5 Discussion

[edit] 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}$ .

[edit] 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, ...

[edit] Closed-form expression for individual digits

The n^th 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 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.

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