The Fibonacci word is a specific infinite sequence of binary digits (or symbols from any two-letter alphabet). Infinity is a term with very distinct, separate meanings which arise in theology, philosophy, mathematics and everyday life. ... In mathematics and computer science, the binary (base_two) numeral system is a representation for numbers that uses only zeroes and ones as digits. ... An alphabet is a complete standardized set of letters — basic written symbols — each of which roughly represents a phoneme of a spoken language, either as it exists now or as it may have been in the past. ...

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

We have:

S₂ 0, 1, 0

S₃ 0, 1, 0, 0, 1

S₄ 0, 1, 0, 0, 1, 0, 1, 0

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

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. In mathematics, the Fibonacci numbers form a sequence defined recursively by: In words: you start with 0 and 1, and then produce the next Fibonacci number by adding the two previous Fibonacci numbers. ... A recursive definition is a one which defines a word in terms of itself, albeit in a useful way. ...

Another way of going from S_n to S_n+1 is to replace each 0 with 0, 1 and each 1 with 0.

The Fibonacci word is a famous example of a Sturmian word. In mathematics, a Sturmian word is a certain kind of infinite word. ...