For any integer $n\geq1$, let $\#_{1}\left(n\right)$ denote the number of $1$s digits in the binary representation of $n$. It is easy to show that the following generating function identity holds:$$\sum_{k=0}^{2^{n}-1}a^{\#_{1}\left(k\right)}x^{k}=\prod_{m=0}^{n-1}\left(1+ax^{2^{m}}\right)$$
Differentiating with respect to the parameter $a$ yields: $$\sum_{k=1}^{2^{n}-1}\#_{1}\left(k\right)a^{\#_{1}\left(k\right)-1}x^{k}=\sum_{k=0}^{n-1}\frac{x^{2^{k}}}{1+ax^{2^{k}}}\prod_{m=0}^{n-1}\left(1+ax^{2^{m}}\right)$$ and so, setting $a=x=1$, we obtain: $$\sum_{k=1}^{2^{n}-1}\#_{1}\left(k\right)=\sum_{k=0}^{n-1}\frac{1}{2}\prod_{m=0}^{n-1}2=\frac{n}{2}2^{n}$$
Being a simple fellow, when I look at this formula for the $\left(2^{n}-1\right)$th partial sum, I replace $n$ with $\log_{2}\left(n\right)$ and arrive at the guesstimate:
$$\sum_{k=1}^{n-1}\#_{1}\left(k\right)\approx\frac{n}{2}\log_{2}\left(n\right)$$
Much to my delight, this little bit naïveté actually works. Specifically, $\frac{n}{2}\log_{2}\left(n\right)$ corresponds to the “dominant” growth rate of the summatory function of $\#_{1}$. If you subtract off this dominant growth rate, and graph the leftovers: $$y=\frac{\left\lfloor x\right\rfloor}{2}\log_{2}\left(\left\lfloor x\right\rfloor\right)-\sum_{k=1}^{\left\lfloor x-1\right\rfloor }\#_{1}\left(k\right)$$ beautiful fine-scale structure emerges:
The pattern in the image is a Blancmange curve a.k.a. Takagi function, and—as was first proven by Trollope in 1968—one can obtain a closed-form expression for $\sum_{k=1}^{n}\#_{1}\left(k\right)$ in terms of the Blancmange curve and other quantities. One means of doing so is by applying Mellin transforms and Perron's Formula to the Dirichlet series: $$\sum_{n=1}^{\infty}\frac{\#_{1}\left(n\right)}{n^{s}}$$
I bring this up because, at present, I am working with sequences $\left\{ a_{n}\right\} _{n\geq0}$ of non-negative real numbers such that, while: $$\sum_{n=0}^{N-1}a_{n}$$ might not admit a nice closed-form expression, there is an integer $\rho\geq2$ so that: $$\sum_{n=0}^{\rho^{N}-1}a_{n}=A\left(N\right)$$ where $A\left(N\right)$ is a nice, simple, closed-form expression. For a wide variety of specific cases, I can computationally verify that the “replace $N$ with $\log_{\rho}N$” method actually does yield the correct dominant growth rate, in the sense that not only do we have the bound: $$\sum_{n=0}^{N-1}a_{n}\leq A\left(\log_{\rho}N\right),\textrm{ }\forall N\geq1$$ but that:$$A\left(\log_{\rho}N\right)-\sum_{n=0}^{N-1}a_{n}$$ is a non-negative function of $N\geq1$ which exhibits fractal structure like the above Blancmange curves.
My question is: under the above conditions, is there a rigorous justification for the implication:$$\sum_{n=0}^{\rho^{N}-1}a_{n}=A\left(N\right),\textrm{ }\forall N\geq1\Rightarrow\sum_{n=0}^{N-1}a_{n}\leq A\left(\log_{\rho}N\right),\textrm{ }\forall N\geq1$$ and, if so, what is it? I've tried using the integral test, the Euler-Maclaurin formula and other methods, but they all seem to require either boundedness of $A\left(x\right)$ or of $A^{\prime}\left(x\right)$ or the like in order to give an upper bound which holds for all $N$, and that condition is not satisfied in any of the cases I'm dealing with.