4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yves Daoust Oct 27 '14 at 21:46
  • 2
    $\begingroup$ Another possibility is that the sequence is infinite but it still does not contain all the positive integers. $\endgroup$ – Robert Soupe Oct 28 '14 at 3:35
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.