The number of distinct and repeated squares and cubes in the Fibonacci sequence

Abstract

The Fibonacci sequence $\mathbb{F}$ is the fixed point beginning with $a$ of morphism $\sigma (a,b)=(ab,a)$. In this paper, we get the explicit expressions of all squares and cubes, then we determine the number of distinct squares and cubes in $\mathbb{F}[1,n]$ for all $n$, where $\mathbb{F}[1,n]$ is the prefix of $\mathbb{F}$ of length $n$. By establishing and discussing the recursive structure of squares and cubes, we give algorithms for counting the number of repeated squares and cubes in $\mathbb{F}[1,n]$ for all $n$, and get explicit expressions for some special $n$ such as $n=f_m$ (the Fibonacci number) etc., which including some known results such as in A.S.Fraenkel and J.Simpson, J.Shallit et al.

14 pages, 4 figures