Binary sequences meet the Fibonacci sequence

Abstract

We introduce a new family of meta-Fibonacci sequences $(f(n){)}_{n\in \mathbb{N}}$, governed by the recurrence relation $$f(n)=af(n-u_n-1)+bf(n-u_n-2),$$ where $\mathbf{u}=(u_n{)}_{n\in \mathbb{N}}$ is a sequence with values $0,1$. Our study focuses on the properties of the sequence of quotients $h(n)=f(n+1)/f(n)$ and its set of values $\mathcal{V}(f)=\{h(n):n\in \mathbb{N}\}$ for various $\mathbf{u}$. We give a sufficient condition for finiteness of $\mathcal{V}(f)$ and automaticity of $(h(n){)}_{n\in \mathbb{N}}$, which holds in particular when $\mathbf{u}$ is the famous Prouhet-Thue-Morse sequence. In the automatic case, a constructive approach is used, with the help of the software \texttt{Walnut}. On the other hand, we prove that the set $\mathcal{V}(f)$ is infinite for other special binary sequences $\mathbf{u}$, and obtain a trichotomy in its topological type when $\mathbf{u}$ is eventually periodic.

20 pages, 3 figures