Palindrome Fibonacci words

Question

Let Fibonacci words over the alphabet $\{0,1\}$ be recursively defined by $\omega_0=0$, $\omega_1=01$, and $\omega_n=\omega_{n-1}\omega_{n-2}$ for $n\geq{2}$. I am trying to show that the word created by removing the last two letters of $\omega_n$ is a palindrome. I am not sure how to go about proving this. I think that induction might work but I'm not sure what my statement would be.

Answer 1

Not an answer, but I feel I was close to proving it and got stuck near the end $$0,01,010,01001,01001010,0100101001001,...$$ Removing the two end characters (sequence now starting at the third term) $$0,010,010010,01001010010,...$$

Assume that two consecutive terms $T_k$ and $T_{k+1}$ are palindromic when the last two characters are removed for some $k\in\mathbb{N}$. These terms can be written as $$T_k=a_0a_1...a_1a_0a_{n-1}a_n$$ $$T_{k+1}=b_0b_1...b_1b_0b_{m-1}b_m$$ Where $a_i, b_i \in \{0,1\}$ and each term has $n$ and $m$ characters respectively. The term after both of these terms will be $$T_{k+2}=b_0b_1...b_1b_0b_{m-1}b_ma_0a_1...a_1a_0a_{n-1}a_n$$ Now for this term to be a palindrome when the last two characters are removed we need all of $a_i$ to be equal to $b_i$ (i.e. $a_0=b_0, a_1=b_1,...$) because the string formed would be $$b_0b_1...b_1b_0b_{m-1}b_ma_0a_1...a_1a_0$$ and we know that all of $a_i$ equal their corresponding $b_i$ becuase of the way in which the terms are defined: $$T_{k+1}=T_kT_{k-1}=a_0a_1...a_1a_0a_{n-1}a_nT_{k-1}=b_0b_1...b_1b_0b_{m-1}b_m$$ This means that we only need to ensure that the central terms are palindromic.

For large enough $k$ we can see that the initial two characters of any term will be $01$ and that the final two characters are $01$ or $10$ intermittently. This is because the final two characters are determined by the term previous to the previous term. As the terms $01$ and $010$ end in $01$ and $10$ respectively, this will cause the next term to end in $01$ and then $10$ etc.

If the number of characters in $T_{k+2}$ is even this means that the term can be written as $$T_{k+2}=01b_2...b_2101001a_2...a_21001$$ or $$T_{k+2}=01b_2...b_2100101a_2...a_21010$$

Answer 2

Well, the inductive formulation itself is pretty simple. Let's denote by $a_n$ the word you get by removing the last two letters of $w_n.$

First, check the base cases: $w_2 = 010$, $w_3 =01001$ and so $a_1 = 0$, $a_2 = 010$ are indeed palindromes.

Since, $a_n$ depends on all of the previous terms, it is probably better to use strong induction. That is, assume that for all $2\leq k<n$, $a_k$ are palindromes. Then, we need to prove that: $$a_n = w_{n-1}a_{n-2}$$ is a palindrome. But look at it closely, $$a_n = w_{n-1}a_{n-2} = a_{n-1}(xy)a_{n-2} = w_{n-2}a_{n-3}(xy)a_{n-2}=$$ $$a_{n-2}(zt)a_{n-3}(xy)a_{n-2},$$ which is a palindrome iff $z = y$ and $x = t,$ because our inductive hypothesis says $a_{n-3}$ is a palindrome. However, $xy$ is the last two digits of $w_{n-1}$, while $zt$ is the last two digits of $w_{n-2}.$ If you look at only the last two digits of the sequence $w_n, n\geq 2:$ $$10,01,10,01,...$$ This is very easily checked by an induction and so it's clear that $z = y$ and $x = t,$ which means we are done.

Answer 3

My first thought on how to tackle this is perhaps not as elegant as dezdichado's, but I hope it will be more illuminating for some people.

We start by observing that $\omega_i$ is a prefix of $\omega_{i+1}$, so if we take the limit there's an infinite word $\Omega$ of which they are all prefixes. We then prove (by induction, if you like) that the word lengths are the Fibonacci numbers (specifically, $|\omega_i| = F(i+2)$). Now we can restate the recurrence: $$\forall i > 2: \forall F(i) \le j < F(i+1): \Omega[j] = \Omega[j - F(i)]$$ and the goal: $$\forall i: \forall j < F(i+2) - 2: \Omega[j] = \Omega[F(i+2) - 3 - j]$$

Now, the rephrasing of the recurrence points us strongly at the Zeckendorf representation: every natural number has a unique representation in non-consecutive Fibonacci numbers, which can be obtained greedily by removing the largest one. E.g. we can write $30 = 21 + 8 + 1$ as $1010001_Z$. So what we have to prove is that if $j + k = F(i+2) - 3$ then either both of their Zeckendorf representations end in $1$ or neither does.

For the actual top level proof I think contradiction is the obvious strategy: suppose wlog that $j = \ldots 01_Z$ and $k = \ldots 0_Z$. We observe that $F(i+2)-3$ has a representation of the form $(10)^*00_Z$ or $(10)^*010_Z$. Unfortunately the case analysis branches quite a bit and gets messy because of "backwards carries" when adding in Zeckendorf representation ($F(n) + F(n) = F(n+1) + F(n-2)$).