Asymptotic Estimates for a Strange Sequence

Question

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$?

Answer 1

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.

Answer 2

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.