# Definition:Fibonacci String

## Definition

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

## 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; $\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.

## 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$