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