Palindrome Fibonacci words

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.

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, $$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.

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$$

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)$$).