# Asymptotic Estimates for a Strange Sequence

Let $a_0=1$. For each positive integer $i$, let $a_i=a_{i-1}+b_i$, where $b_i$ is the smallest element of the set $\{a_0,a_1,\ldots,a_{i-1}\}$ that is at least $i$. The sequence $(a_i)_{i\geq0}=1,2,4,8,12,20,28,36\ldots$ is A118029 in Sloane's Online Encyclopedia. It is easy to show that $a_i$ is strictly increasing. My question is about whether there are any ways to deduce asymptotic estimates for $a_i$. Alternatively, we could define a sequence $(c_i)_{i\geq0}$ by letting $c_i$ be the largest integer $m$ such that $a_m\leq i$. For example, $c_{13}=4$ because $a_4=12\leq 13<a_5=20$. Could we find asymptotic estimates for $c_i$?

• "My question is about whether there are any ways to deduce asymptotic estimates..." If the OEIS does not provide any, this is unlikely. oeis.org/search?q=A118029 – Did Jul 29 '15 at 7:54
• Plotting the $a_k$ for $k\leq2000$ shows that $a_k\doteq 0.511\>k^2$ with good accuracy. – Christian Blatter Jul 29 '15 at 9:00
• @ChristianBlatter, would you mind letting me know what program you used to generate the values? – Colin Defant Jul 29 '15 at 17:20

Upon your request I computed the first $10\,000$ of the $a_k$ using Mathematica. Here is the output:

Note that the figure contains two graphs.

• Thank you. After using that program to find $a_n$ for larger values of $n$, I think that $a_n\sim\frac12n^2$, which makes sense. I will try proving this. – Colin Defant Jul 29 '15 at 18:23

If $b_i$ is nearly $i$ (you define it as larger, this will give a lower bound) then you have a simple recurrence:

$$a_{i + 1} - a_i = i \qquad a_0 = 0$$

so that approximately:

$$a_i = \frac{i (i + 1)}{2}$$

This tends to confirm your conjecture.