Definition:Fibonacci String

From ProofWiki
Jump to navigation Jump to search


Consider the alphabet $\left\{ {\text {a}, \text {b} }\right\}$.

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 $\left\langle{S_n}\right\rangle$ are Fibonacci strings.


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; $\left\{ {0, 1}\right\}$ 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 $\left\{ {\text {a}, \text {b} }\right\}$ 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.