3
$\begingroup$

I'll start with some definitions to simplify the rest of the message.

Let's denote $f_0 = b, \ f_1 = a, \ f_n = f_{n-1} \cdot f_{n-2}$, where $\cdot$ stands for concatenation of two words. We call $f_n$ the $n$-th Fibonacci word. Let's also denote $f := \lim_{n \to \infty} f_n$ (the Fibonacci word). Let $s_{k}$ be the subword of $f$ consisting of the first $k$ letters of it. Let $w(k)$ be the $k$-th letter of a word $w$. Let $\mathrm{per}(k)$ stand for the smallest positive number such that $$ \forall i \in \{ 1, \ldots, k - \mathrm{per}(k) \}. \ s_{k}(i) = s_{k}(i + \mathrm{per}(k)) $$ In other words, $\mathrm{per}(k)$ is the smallest period in the word $s_{k}$.

During one of my lectures, my lecturer mentioned an interesting property of the Fibonacci words. If we look at the sequence $(\mathrm{per}(k))_{k \in \mathbb{Z}_{+}}$, it looks like this $$ (1, 2, 2, 3, 3, 3, 5, 5, 5, 5, 5, \ldots) $$ So, one $1$, two $2$s, three $3$s, five $5$s, and so on. It is the non-decreasing sequence consisting of Fibonacci numbers where the number $F_n$ appears exactly $F_n$ times.

I've been trying to prove it today, but with little success. I'll be glad for any kind of help – a proof, some hints, remarks, pretty much anything. I'll list what I've managed to show below:

The smallest period of $f_k$ is $F_{k-1}$

I proved it inductively: the basis is obvious – we do it by hand. Then we make the induction step: let's look at $f_n$ and let $p$ be the smallest period in it. It's obvious $F_{n-1}$ is a period in that word. We also know that anything smaller than $F_{n-2}$ cannot be a period because then it would be a period in $f_{n-1}$ too and we'd get a contradiction. Thus, $p \in [F_{n-2}, F_{n-1}]$.

To show $p$ cannot be equal to $F_{n-2}$ it's sufficient to compare the last letters of $f_{n-1}$ and $f_{n-2}$ – they're different, so $p \neq F_{n-2}$. Thus $p \in (F_{n-2}, F_{n-1}]$.

Let's assume $p \in (F_{n-2}, F_{n-1})$. Note that $f_n = f_{n-3}f_{n-4}f_{n-3}f_{n-2}$. We'll focus on the subword $f_{n-4}f_{n-3}f_{n-2}$. Note that $\lvert f_{n-4}f_{n-3} \rvert = \lvert f_{n-2} \rvert = F_{n-2}$. It's easy to also show that $f_{n-4}f_{n-3}$ is equal to $f_{n-2}$ except for the last two characters (which are swapped). So the prefix of $f_{n-4}f_{n-3}$ of length $F_{n-2} - 2$ is a prefix of $f_{n-2}$. Let's denote $w := f_{n-4}f_{n-3}f_{n-2}$. Using that and the periodicity, we have $$ \forall i \in \{ 1, \ldots, 2F_{n-2} - p \}. \ w(i) = w(i + p) $$ and $$ \forall i \in \{ 1, \ldots, F_{n-2} - 2 \}. \ w(i) = w(i + F_{n-2}) $$ Thus, after denoting $p^{\prime} := p - F_{n-2}$, $$ \forall i \in \{ 1, \ldots, F_{n-2} - p^{\prime} \}. \ f_{n-2}(i) = f_{n-2}(i + p^{\prime}) $$ Note that $p^{\prime} < F_{n-1} - F_{n-2} = F_{n-3}$ and it's a period in $f_{n-2}$. We get a contradiction because we assumed (as part of the induction proof) that the smallest period in $f_{n-2}$ is $F_{n-3}$. Thus $p = F_{n-1}$. $\Box$

PS I was reminded in my other post that I should provide the source of what I post on this forum. However, it's impossible for me to refer you to the exact place where you could find this problem as you don't have access to it, but for completeness, this is the course (in Polish) I'm taking and where I came across it.

$\endgroup$

1 Answer 1

2
$\begingroup$

What we need to prove are

  • the smallest period for $s_1$ is 1, which is trivially true.
  • the smallest period for $s_i$ is $F_{k-1}$ for all $F_k-1\le i\le F_{k+1}-2$, where $k\ge3$.

Let $k\ge3$.

You have proved that the smallest period of $f_k=s_{F_k}$ is $F_{k-1}$.

  • The smallest period of any string cannot be smaller than that of a prefix of itself.
  • $f_{k+1}=f_{k-1}f_{k-2}f_{k-1}$. Since the suffix $f_{k-2}f_{k-1}$ is the same as the prefix $f_{k-1}f_{k-2}$ except the last two characters, $|f_{k-1}|$ is a period of $f_{k+1}$ without last two characters. That is, $F_{k-1}$ is a period of $s_{F_{k+1}-2}$. Hence for any $i\le F_{k+1}-2$, the smallest period of $s_i$ is at most $F_{k-1}$.

So, the smallest period for $s_i$ is $F_{k-1}$ for all $F_k\le i\le F_{k+1}-2$, where $k\ge3$.

Looking closely, we can see that you have also proved the smallest period of $s_{F_k-1}$ is $F_{k-1}$. $\quad\Box$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.