# Are all Fibonacci words uniquely represented as concatenation of two palindromes?

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.

• 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.. – Berci Jan 19 at 14:56

## 1 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.