The structure of palindromes in the Fibonacci sequence and some applications

Abstract

Let $\mathcal{P}$ be the set of palindromes occurring in the Fibonacci sequence. In this note, we establish three structures of $\mathcal{P}$ and and discuss their properties: cylinder structure, chain structure and recursive structure. Using these structures, we determine that the number of distinct palindrome occurrences in $\mathbb{F}[1,n]$ is exactly $n$, where $\mathbb{F}[1,n]$ is the prefix of the Fibonacci sequence of length $n$. Then we give an algorithm for counting the number of repeated palindrome occurrences in $\mathbb{F}[1,n]$, and get explicit expressions for some special $n$, which include the known results. We also give simpler proofs of some classical properties, such as in X.Droubay, W.F.Chuan and J.Shallit et al.

arXiv comment10 pages, 1 figure

References in corpus (1)

• Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance

Cited by in corpus (1)

• The Numbers of Distinct Squares and Cubes in the Tribonacci Sequence