I'm having some trouble justifying some steps in a paper.
Let $a_n$ be an increasing sequence of integers satisfying $n! \le a_n \le 2(n!)$, and let $f:\mathbb{N} \to \mathbb{N}$ be a function satisfying $$f(2a_n+1) = \frac{1}{2}(2a_n+1)(2a_n+2)+na_n-\frac{1}{2}(n-1)(n-2).$$
Let $l:=2h_n+1$. The paper claims $$f(l) \le \frac{l(l+1)+l\cdot g(l)}{2} \tag{*},$$ where $g(l) \sim \frac{\log l}{\log \log l}$ as $l \to \infty$. Moreover, $$f(l) \ge \frac{l^2 + l \cdot O\left(\frac{\log l}{\log \log l}\right)}{2}.\tag{**}$$
My attempts:
If we replace $2a_n+1$ with $l$, we have $$f(l) \le \frac{l(l+1)}{2} + na_n \le \frac{l(l+1)}{2}+\frac{l\cdot n}{2}.$$ So we need something like $n \sim g(l)$. I have an intuition for where the expression for $g$ comes from, but it is extremely imprecise. I use the symbol $\leftrightsquigarrow$ to denote similar growth. \begin{align*} l:=2a_n+1 &\leftrightsquigarrow n!\\ l &\leftrightsquigarrow n^n & \text{Stirling's approx.?}\\ \log l &\leftrightsquigarrow n \log n\\ \log \log l &\leftrightsquigarrow \log (n \log n)\\ g(l)\sim \frac{\log l}{\log \log l} &\leftrightsquigarrow n\frac{\log n}{\log (n \log n)} \sim n \end{align*}
There are several issues:
- something is lost in Stirling's approximation (it is not true that $n^n \sim n!$).
- I am not sure how to rigorously express $\leftrightsquigarrow$. In particular, there is a constant factor lurking somewhere in the work toward $g(l) \leftrightsquigarrow n$, but (*) shows no such constant.
As for the lower bound, I have no idea. The only difference from the upper bound is the change of $l+1$ to $l$ and the $\sim$ to $O(\cdot)$. This suggests that both bounds are pretty tight...
By setting $\nu = 2a_n+1$ and taking $\eta$ as the inverse map of $\theta:n\to a_n$ we have: $$f(\nu)=\frac{\nu(\nu+1)}{2}+\frac{\nu-4}{2}\eta((\nu-1)/2)-\frac{1}{2}\eta((\nu-1)/2)^2-1,$$ hence we just need tight asymptotics for the $\eta$ function. Since:$$\left(\frac{m+1}{e}\right)^{m+1}\geq 2m!\geq\theta(m)\geq m!\geq\left(\frac{m}{e}\right)^m,$$ we must have: $$\left(\frac{\eta(t)}{e}\right)^{\eta(t)}\leq t\leq \left(\frac{\eta(t)+1}{e}\right)^{\eta(t)+1},$$ so: $$ \eta(t)\left(\log\eta(t)-1\right)\leq \log t\leq (\eta(t)+1)\left(\log(\eta(t)+1)-1\right).\tag{1}$$ To estimate the root of $u(\log u-1)-\log t=0$ we can exploit the convexity of the LHS.
The Newton's method gives that the root of such equation is: $$\frac{\log t}{\log \log t}+O\left(\frac{\log t\,(\log\log\log t)}{(\log \log t)^2}\right),$$ hence $$ \eta(t)=\Theta\left(\frac{\log t}{\log \log t}\right)$$ due to $(1)$.