Ttyjukl

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 $ngeq{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 $2leq 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, ngeq 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 $kinmathbb{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)$).