Fibonacci word is not periodic

by fibophilia

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