Fibonacci Word Generator - Generate Fibonacci Words Online

What is a Fibonacci Word?

A Fibonacci Word is a specific sequence of symbols (usually binary digits like $0$ and $1$) formed by repeated concatenation, mirroring the way Fibonacci numbers are formed by repeated addition. It is a fundamental example of a Sturmian word, which has minimal subword complexity and numerous applications in mathematics, computer science, physics (crystallography), and music theory.

Mathematical Definition

The Fibonacci word sequence is defined recursively over a two-letter alphabet $\{A, B\}$ as follows: $$S_0 = A$$ $$S_1 = B$$ $$S_n = S_{n-1} S_{n-2} \quad \text{for } n \ge 2$$

If we set $A = \text{"0"}$ and $B = \text{"01"}$, the first few iterations produce the following words:

$S_0 = \text{"0"}$
$S_1 = \text{"01"}$
$S_2 = S_1 S_0 = \text{"010"}$
$S_3 = S_2 S_1 = \text{"01001"}$
$S_4 = S_3 S_2 = \text{"01001010"}$
$S_5 = S_4 S_3 = \text{"0100101001001"}$

The infinite limit of this sequence is known as the Infinite Fibonacci Word.

The Morphic/Substitution Method

Another elegant way to generate the infinite Fibonacci word is starting with the single letter $0$ and repeatedly applying a substitution rule (or morphism): $$0 \to 01$$ $$1 \to 0$$

Tracing this substitution:

Start: $0$
Apply morphism: $01$
Apply morphism: $010$ (since $0 \to 01$ and $1 \to 0$)
Apply morphism: $01001$
Apply morphism: $01001010$

Both the recursive concatenation and the morphic substitution yield the exact same binary pattern.

Fascinating Properties

Golden Ratio Limit: The length of the word $S_n$ corresponds to the $(n+2)$-th Fibonacci number ($F_{n+2}$). As $n$ approaches infinity, the ratio of the number of $0$s to $1$s (and the ratio of term lengths $\frac{|S_n|}{|S_{n-1}|}$) converges exactly to the Golden Ratio $\phi = \frac{1+\sqrt{5}}{2} \approx 1.6180339887$.
Aperiodic and Sturmian: The infinite Fibonacci word is aperiodic, meaning it never repeats in a periodic cycle. Yet, it is highly structured. For any length $L$, the word contains exactly $L+1$ distinct subwords of length $L$.
Palindromes: If we delete the last two characters of $S_n$ (for $n \ge 2$), the remaining word is a perfect palindrome (reads the same forwards and backwards).

Frequently Asked Questions

What is the difference between a Fibonacci number and a Fibonacci word?

A Fibonacci number is a numerical value ($0, 1, 1, 2, 3, 5, 8, \dots$) formed by adding the two preceding numbers. A Fibonacci word is a string of characters ($0, 01, 010, 01001, \dots$) formed by concatenating the two preceding strings.

How does the Golden Ratio relate to Fibonacci words?

As the sequence grows, the length of the words scales exactly like the Fibonacci sequence. Furthermore, the ratio of the number of primary symbols (like $0$s to $1$s) approaches the Golden Ratio $\phi \approx 1.61803$. Our tool calculates and displays this ratio convergence in real-time.

What are the default presets used in this tool?

We support two standard presets: "Standard Binary" which starts with $S_0 = \text{"0"}$ and $S_1 = \text{"01"}$, and "Standard Alphabetical" which starts with $S_0 = \text{"b"}$ and $S_1 = \text{"a"}$. You can also input custom letters or words for the terms.

Why is there an iteration limit of 15?

The length of Fibonacci words grows exponentially. By iteration 15, the word is $F_{17} = 1597$ characters long, but higher iterations like 20 or 25 produce strings with millions of characters, which can crash your browser's memory. To protect performance, we recommend using lower iterations or selecting the "By Target Length" limit option.