2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "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 $\endgroup$ – Did Jul 29 '15 at 7:54
  • $\begingroup$ Plotting the $a_k$ for $k\leq2000$ shows that $a_k\doteq 0.511\>k^2$ with good accuracy. $\endgroup$ – Christian Blatter Jul 29 '15 at 9:00
  • $\begingroup$ @ChristianBlatter, would you mind letting me know what program you used to generate the values? $\endgroup$ – Colin Defant Jul 29 '15 at 17:20
2
$\begingroup$

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

enter image description here

Note that the figure contains two graphs.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Colin Defant Jul 29 '15 at 18:23
0
$\begingroup$

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.

$\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.