4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.