### Fibonacci word is not periodic

Fibonacci word ${\mathbf{f} = \mathtt{010010100100101001010\ldots}}$ is given as the limit of finite Fibonacci words defined by

$\displaystyle f_1 = \mathtt{1}, \qquad f_2 = \mathtt{0}, \qquad f_n = f_{n-1} f_{n-2} \quad (n\geq 3)$.

An infinite word ${\mathbf{z}}$ is called periodic if it can be written in a form ${\mathbf{z} = x^{\mathbb{N}}}$ for some finite word ${x}$.

Theorem The Fibonacci word is not periodic.

Here is an outline of three very different ways to prove the claim.

A proof using the irrationality of the golden ratio

The golden ratio ${\phi= \frac{1 + \sqrt{5}}{2}}$ is irrational and it is the limit of ${F_{n+1}/F_n}$ as ${{n \rightarrow\infty}}$. If the Fibonacci word were periodic, say ${\mathbf{f} = x^{\mathbb{N}}}$, then the frequency of its letters would exist. So, on the one hand, the frequency of the letter ${\mathtt{0}}$ is then the rational number ${|x|_{\mathtt{0}}/|x|}$, but on the other hand, it is the irrational number

$\displaystyle \lim_{n\rightarrow \infty} \frac{|f_n|_{\mathtt{0}}}{|f_n|_{\phantom{\mathtt{0}}}} = \lim_{n\rightarrow \infty}\frac{F_{n-1}}{F_n} = \frac{1}{\phi},$

a contradiction.

A proof using a divisibility property of Fibonacci numbers

One curious property of Fibonacci numbers is that, for every integer ${d \geq 1}$, infinitely many of them are divisible by ${d}$. Now, suppose that ${\mathbf{f} = x^{\mathbb{N}}}$ for some ${x \in \{\mathtt{0}, \mathtt{1}\}^*}$. There exists an integer ${k}$ such that ${F_k}$ is divisible by ${|x|}$ and ${F_k > |x|}$ holds. Thus ${f_k = x^{F_k/|x|}}$, which contradicts the fact that finite Fibonacci words are primitive.

A proof using the least period of ${f_n}$

The smallest period of a finite Fibonacci word ${f_n}$ is ${F_{n-1}}$. That is, if we write ${f_n = a_1 a_2 a_3 \cdots a_{F_n}}$ with ${a_i \in \{ \mathtt{0}, \mathtt{1}\}}$, then ${F_{n-1}}$ is the smallest integer ${p}$ such that ${a_{i+p} = a_i}$ for all ${i = 1, 2, 3, \ldots, F_{n} - p}$. This implies that Fibonacci word is not periodic, for if ${\mathbf{f} = x^{\mathbb{N}}}$, then all sufficiently long factors of ${\mathbf{f}}$ would have a period ${|x|}$.

Advertisements