Sturmian word

Example

A Sturmian word is an infinite word $s = s_0 s_1 s_2 \cdots$ over $\set{0, 1}$ that has exactly $n + 1$ distinct factors of length $n$ for every $n \ge 0$. A factor of length $n$ is a block $s_i s_{i+1} \cdots s_{i+n-1}$. Equivalently, there are an irrational number $\alpha \in (0, 1)$ and a real $\rho$ with the following property. For all $n$, $s_n = \floor{(n+1)\alpha + \rho} - \floor{n \alpha + \rho}$, or the same holds with $\ceil{\cdot}$ in place of $\floor{\cdot}$. Then $s_n = 1$ exactly when the point $n\alpha + \rho$ of the circle $\R/\Z$ lies in a fixed arc of length $\alpha$. So $s$ codes the irrational rotation by $\alpha$.

The Fibonacci word is the main instance. Define $S_0 = 0$, $S_1 = 01$ and $S_{k} = S_{k-1} S_{k-2}$ for $k \ge 2$. Each $S_{k-1}$ is a prefix of $S_k$, and the limit is $$f = 0100101001001010010100100101 \cdots .$$ Check for small $n$: the factors of length $1$ are $0, 1$, and those of length $2$ are $00, 01, 10$, since $11$ never occurs. So there are $2$ and $3$ of them, as required. For $k \ge 1$ the word $S_k$ has $F_k$ zeros and $F_{k-1}$ ones, with $F_k$ the Fibonacci numbers ($F_0 = F_1 = 1$). So the frequency of the letter $1$ is $\lim F_{k-1}/F_{k+1} = 1/\varphi^2$, where $\varphi$ is the golden ratio.