Suppose Fibonacci word sequence is a word sequence defined by the following relations: $$\phi_1 = «0»$$ $$\phi_2 = «01»$$ $$\forall n > 2 \text{ } \phi_n = \phi_{n - 1}\phi_{n - 2}$$

Let’s prove, that for every natural n, there exist two palindromes $\alpha_n$ and $\beta_n$, such that $\phi_n = \alpha_n\beta_n$

It is well known, that 1. The last two letters of a Fibonacci word are alternately $«01»$ and $«10»$ 2. Suppressing the last two letters of a Fibonacci word, or prefixing the complement of the last two letters, creates a palindrome

Suppose $\phi_{2n+1} = \alpha_{2n + 1}^110$ and $\phi_{2n} = \alpha_{2n}^101$. Then, if we we can take $\beta_{2(n + 1)}^1 = 01\alpha_{2n + 1}^110$ and $\beta_{2n + 1}^1 = 10\alpha_{2n}^101$.

Then, it is easy to see that $\alpha^1_n$ and $\beta_n^1$ satisfy the aforementioned conditions for every natural $n \geq 2$

However I failed to find an answer to the question: «Does there exist a natural number $n$ and two palindromes $\alpha$ and $\beta$, not equal to $\alpha_n^1$ and $\beta_n^1$ respectively, such that $\phi_n = \alpha\beta$

Any help will be appreciated.

  • 1
    $\begingroup$ I wrote a small python program to check until $n=30$, and there's always only one way to divide them to two palindromes. It might be provable by induction from all the information you already got.. $\endgroup$
    – Berci
    Jan 19 '19 at 14:56

This is not a complete proof, as there are some edge conditions to be dealt with regarding the length of the common substring $\pi$ (see below), but it covers the general case. The idea is to show that if there are two such decompositions, then there is a substring that appears four times successively, which is impossible.

Suppose $\alpha_1\beta_1 = \alpha_2\beta_2$ are two such decompositions. Then $\alpha_1$ and $\beta_2$ overlap in some string, $\pi$. Then we get two palindromic decompositions $(\delta\pi)(\gamma)$ and $(\delta)(\pi\gamma)$. Write $\pi_r$ for the reversal of $\pi$. Then: $$\phi_n = (\delta\pi)(\gamma) = (\pi_r\delta_1\pi)(\gamma) = (\pi_r\delta_1)(\pi\gamma) = (\pi_r\delta_2\pi)(\pi\gamma).$$ (The final step is justified since the first parenthesized expression is simply $\delta$, so is palindromic. This will be used multiple times below.) Then \begin{align*}\phi_n &= (\pi_r\delta_2\pi)(\pi\gamma) = (\pi_r\delta_2\pi^2)(\gamma) = (\pi_r^2\delta_2\pi^2)(\gamma) = (\pi_r^2\delta_2\pi)(\pi\gamma) = (\pi_r^2\delta_2\pi^2)(\pi\gamma)\\ &= (\pi_r^2\delta_2\pi^3)(\gamma) = (\pi_r^3\delta_3\pi^3)(\gamma) = (\pi_r^3\delta_3\pi^2)(\pi\gamma) = (\pi_r^3\delta_3\pi^3)(\pi\gamma). \end{align*} Then $\pi$ appears four times consecutively in $\phi_n$, which is impossible.

The issue with this proof, of course, is that it assumes that $\phi_n$ is long enough, and $\pi$ short enough, that none of the substrings overlap.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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