Simplify $S=\sum_{i=0}^{k}a_i (2n)^{2i+1}$

Question

Can someone simplify this expression (or compute its supremum)? Thanks so much. $$S=\sum_{i=0}^{k}a_i (2n)^{2i+1}$$ where $a_i>0$ and $k>1$, and $\sum_{i=0}^{k}a_i=1$.

Answer 1

Your expression has variables $a_i$ so any computational formula will take at least $\Omega(k)$ time to evaluate. And your current expressioh can be evaluated in $O(k)$ time, by rewriting as

$$S = 2n(a_0 + (2n)^2(a_1 + (2n)^2(a_2 + (2n)^2(a_3 + \ldots$$

In terms of computation, it can't get any faster/simpler than that, at least not asymptotically in terms of $k$.