Definition:Fibonacci String
Definition
Consider the alphabet $\set {\text a, \text b}$.
For all $n \in \Z_{>0}$, let $S_n$ be the (finite) string formed as:
- $S_n = \begin {cases} \text a & : n = 1 \\
\text b & : n = 2 \\ S_{n - 1} S_{n - 2} & : n > 2 \end{cases}$
where $S_{n - 1} S_{n - 2}$ denotes that $S_{n - 1}$ and $S_{n - 2}$ are concatenated.
The terms of the sequence $\sequence {S_n}$ are Fibonacci strings.
Examples
Example: $S_3$
The Fibonacci string $S_3$ is $\text{ba}$.
Example: $S_4$
The Fibonacci string $S_4$ is $\text{bab}$.
Example: $S_5$
The Fibonacci string $S_5$ is $\text{babba}$.
Also defined as
The specific alphabet used is immaterial.
Different sources use different alphabets; $\set {0, 1}$ is another common one.
Different starting values are also sometimes seen, for example:
- $S_0 = 0, S_1 = 01$
$\mathsf{Pr} \infty \mathsf{fWiki}$ uses $\set {\text a, \text b}$ and the starting values given, by preference and for internal consistency.
Also known as
Some sources refer to a Fibonacci string as a Fibonacci word.
Source of Name
This entry was named for Leonardo Fibonacci.
Historical Note
The sequence of Fibonacci strings was first studied by Johann III Bernoulli in the $18$th century.
It was later studied by Andrey Andreyevich Markov in the $19$th century, and by many mathematicians since then.
Sources
- 1882: Andrey Andreyevich Markov: Sur un question de Jean Bernoulli (Math. Ann. Vol. 19: pp. 27 – 36)
- 1976: Kenneth B. Stolarsky: Beatty sequences, continued fractions, and certain shift operators (Canadian Math. Bull. Vol. 19: pp. 473 – 482)
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.8$: Fibonacci Numbers: Exercise $36$