On the congruence properties and growth rate of a recursively defined sequence

Abstract

Let $a_1=1$ and, for $n>1$, $a_n=a_{n-1}+a_{\lfloor \frac{n}{2}\rfloor }$. In this paper we will look at congruence properties and the growth rate of this sequence. First we will show that if $x\in \{1,2,3,5,6,7\}$, then the natural density of $n$ such that $a_n\equiv x(\mathrm{mod}8)$ exists and equals $\frac{1}{6}$. Next we will prove that if $m\le 15$ is not divisible by $4$, then the lower density of $n$ such that $a_n$ is divisible by $m$, is strictly positive. To put these results in a broader context, we will then posit a general conjecture about the density of $n$ such that $a_n\equiv x(\mathrm{mod}m)$ for any given $x$ and any $m$ not divisible by $32$. Finally, we will show that there exists a function $f$ such that $n^{f(n)}<a_n<n^{f(n)+\epsilon }$ for all $\epsilon >0$ and all large enough $n$.

18 pages