The numbers of repeated palindromes in the Fibonacci and Tribonacci sequences

Abstract

The Fibonacci sequence $\mathbb{F}$ is the fixed point beginning with $a$ of morphism $\sigma (a,b)=(ab,a)$. Since $\mathbb{F}$ is uniformly recurrent, each factor $\omega$ appears infinite many times in the sequence which is arranged as ${\omega }_p$ $(p\ge 1)$. Here we distinguish ${\omega }_p\ne {\omega }_q$ if $p\ne q$. In this paper, we give algorithm for counting the number of repeated palindromes in $\mathbb{F}[1,n]$ (the prefix of $\mathbb{F}$ of length $n$). That is the number of the pairs $(\omega ,p)$, where $\omega$ is a palindrome and ${\omega }_p\prec \mathbb{F}[1,n]$. We also get explicit expressions for some special $n$ such as $n=f_m$ (the $m$-th Fibonacci number). The similar results are also given to the Tribonacci sequence, the fixed point beginning with $a$ of morphism $\tau (a,b,c)=(ab,ac,a)$.

12 pages, 2 figures. arXiv admin note: text overlap with arXiv:1601.04391