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.
Best Answer
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.