# Does this sequence contain all positive integers?

Set $a_1 = 1$. Then $a_n$ is chosen to be 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$. 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. Is it possible to prove this one way or the other?

• This is oeis.org/A248982. Of course this is not a proof, but when seeing the logarithmic plot, a regular exponential behavior (ratio $\phi$ between every other term) is striking. – Yves Daoust Oct 27 '14 at 21:46
• Another possibility is that the sequence is infinite but it still does not contain all the positive integers. – Robert Soupe Oct 28 '14 at 3:35

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.