Does this sequence contain all positive integers?

Question

Let $a_1 = 1$. Then $a_n$ is the smallest distinct positive integer such that $$\frac{\sum_{i = 1}^n a_i}{n}$$ is a Fibonacci number. If my calculations are correct, the sequence starts out $1, 3, 2, 6, 13, 5, 26, 8, 53, 93, 21, \ldots$. From the definition I would think this sequence does contain all integers. But I can't rule out the possibility that for some $n$ there might be no possible available value with which to continue the sequence. Does there exist a (dis)proof?

Answer 1

The sequence can always be continued but it does not contain all positive integers.

Let $F_n$ denote the $n$th Fibonacci number, $F_0=0,F_1=F_2=1$.

Let $s_n = \sum_{i=1}^n a_n$, and according to the definition of the sequence that $s_n/n = F_{k(n)}$ is a Fibonacci number, let $k(n)$ be the index of the Fibonacci number that is the average of $a_1,\ldots,a_n$.

To see that the sequence can always be continued, let $n\ge 4$ and $A=\max_{i=1}^n a_i\ge 6$, then $F_A>A$, $s_n< nA$ and $$ a = (n+1)F_A-s_n>F_A>A $$ is a possible continuation; it has not yet appeared and would give a Fibonacci number $F_A$ as the average of the first $n+1$ terms if $a_{n+1}=a$.

To show that not all positive integers appear we can show that $k(n)$ is nondecreasing, so $a_n$ has exponential growth and omits most values.

Looking at rough growth rates $$ \frac{F_{i+1}}{F_i} > \frac{3}{2} \quad \text{for }i>3\\ 1<\frac{i+1}{i} < \frac{3}{2} \quad \text{for }i>2 $$ it follows that if $n>2$ and $k(n)>3$ then $$ (n+1)F_{k(n+1)} = s_{n+1}>s_n = nF_{k(n)}\\ \frac{F_{k(n)}}{F_{k(n+1)}} < \frac{n+1}{n} \implies k(n)\le k(n+1) $$

Since $s_1=1$, by convention say $k(1)=2$, then we need only check $k(2)=k(3)=3,k(4)=4$ to show that $k(n)$ is always nondecreasing in $n$.

If $k(n+1)=k(n)$ then $$ s_{n+1} = (n+1)F_{k(n)} = s_n+F_{k(n)}\implies a_{n+1} = F_{k(n)} $$ Otherwise $k(n+1)\ge k(n)+1$ and $$ s_{n+1} \ge (n+1)F_{k(n)+1} = s_n + nF_{k(n)-1}+F_{k(n)+1} \implies a_{n+1} \ge nF_{k(n)-1}+F_{k(n)+1}>F_{k(n)} $$

Thus $a_{n+1}\ge F_{k(n)}$. Since $k(n)$ is nondecreasing we will have for example $a_n>21$ for all $n>11$. Thus the sequence omits 4,7,9,etc.

We can say a bit more. Define the sequences $$ G_{d,n} = (2n-d)F_n+F_{n-1}\\ G_{0,n} = 2,5,13,26,53,101,\ldots \\ G_{1,n} = 1,4,11,23,48,93,177,328,599,\ldots $$ then we can observe that $$ a_5=G_{0,3} \quad a_7=G_{0,4} \quad a_9=G_{0,5} \\ a_6 = F_5 \quad a_8 = F_6 \\ $$ but since $F_7=G_{0,3}=a_5=13$ had already appeared, the pattern changes with $a_10$. Thereafter $$ a_{10} = G_{1,6} \quad a_{12}=G_{1,7} \quad a_{2n} = G_{1,n+1} \\ a_{11} = F_8 \quad a_{13} = F_9 \quad a_{2n+1} = F_{n+3} $$ This pattern holds for quite a while. If it is the case that $G_{1,n}$ contains no Fibonacci numbers for $n>1$ then the pattern will hold forever, and that will confirm the conjectures on the OEIS page for this sequence, namely that $$ a_{2n+1}=F_{n+3} \quad \text{for }n>4 \\ $$ and $$ a_{n} = 2a_{n-2}+a_{n-4}-2a_{n-6}-a_{n-8} \quad \text{for }n>17 $$ since the recursive relation $$ T_n = 2T_{n-1}+T_{n-2}-2T_{n-3}-T_{n-4} $$ is satisfied by both $F_n$ and $G_{d,n}$ (and in fact by any sequence of the form $T_n = uF_n + vF_{n-1}$).

Unfortunately, at the moment I cannot rule out the possibility that $G_{1,n+1} = F_{m+3}$ for some $n>2$ and $m$, in which case $a_{2n}=F_{m+3}$ and these patterns will be broken when $a_{2m+1}=G_{2,m+1}\ne F_{m+3}$, and a different pattern will emerge.