Asymptotic bound of $\sum_{i=0}^{\log(n)} 2^{i} \sum_{k=0}^{\frac{n}{2^{i}}} (k+2)^{2} + \theta(n)$

Question

What is the asymptotic bound for $\sum_{i=0}^{\log(n)} 2^{i} \sum_{k=0}^{\frac{n}{2^{i}}} (k+2)^{2} + \theta(n)$?

Answer 1

I suggest you use big O notation. If I am not mistaken, the following does the job.

Normal[Series[Sum[2^i*(k + 2)^2, {i, 0, Log[n]}, {k, 0, n/2^i}], {n, Infinity,1}]] //FullSimplify

$$\frac{1}{9} n^3 \left(4-2^{-2 \log (n)}\right)+n^2 \left(5-5\ 2^{-\log (n)-1}\right)+\frac{37 n}{6}+\frac{37}{6} n \log (n)+2^{\log (n)+3}-4 $$

One sees the main term of the asymptotics is $\frac 4 9 n^3$.