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

Definition

Let S₀ be "0" and S₁ 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 .

The Sequence

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

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.

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