# Giving an asymptotically tight bound on sum $\sum_{k=1}^n (\log_2 k)^2$

I am trying to give an asymptotically tight bound for the sum $\displaystyle\sum_{k=1}^{n} (\text{lg}k)^{2}$, where lg denotes the base 2 logarithm.

I really have no idea where to begin, and I've tried looking at consecutive ratio terms, I've tried changing the summand to $2^{2\text{lg}\text{lg}k}$, etc.

I know that $\Theta$ is linear, so really I just need an asymptotically tight bound on $(\text{lg}k)^{2}$, and I should be fine from there. But still, no luck...

Any help, hints, etc. would be greatly appreciated.

I will give two answers below -- the first one is simple, and applies if you do not care about getting the exact constant in the asymptotic (i.e., if a $\Theta(\cdot)$ result is enough). The second is a tad longer, but gives the exact leading term; and actually more (i.e., it will also give the two or three next low-order terms, in this particular case).

Method 1: Upper and lower bounds.

You have $$\sum_{k=\lfloor n/2\rfloor }^n (\log k)^2 \leq \sum_{k=1}^n (\log k)^2 \leq n (\log n)^2$$ and $$\sum_{k=\lfloor n/2\rfloor }^n (\log k)^2 \geq \frac{n}{2}\left(\log \left\lfloor\frac{n}{2}\right\rfloor\right)^2 \geq \frac{n}{2}\left(\log \frac{n}{2} - 1\right)^2 = \frac{n}{2}\left(\log n - 2\right)^2 \operatorname*{\sim}_{n\to\infty} \frac{1}{2} n(\log n)^2.$$ Putting it together, $$\sum_{k=1}^n (\log k)^2 = \Theta\left( n \log^2 n \right).$$

Method 2: Using integrals, often much easier to handle than sums.

Intuitively, a comparison series-integral would most likely do the trick. Indeed, $f\colon x > 1\mapsto (\ln x)^2$ is increasing, which is a good hint it'd work. (I am dropping the base 2 of the logarithm, since it is only a constant factor in the end result.)

Now, for every $k \geq 1$, for all $x\in[k,k+1)$ $$(\ln k)^2 \leq (\ln x)^2\leq (\ln(k+1))^2$$ so that $$\sum_{k=1}^{n-1} (\ln k)^2 \leq \sum_{k=1}^{n-1} \int_{k}^{k+1}(\ln x)^2 dx = \int_{1}^{n}(\ln x)^2 dx \leq \sum_{k=1}^{n-1} (\ln(k+1))^2=\sum_{k=2}^{n} (\ln k)^2.$$ This implies, rearranging terms (and since $\ln 1 = 0$), that $$\int_{1}^{n}(\ln x)^2 dx \leq \sum_{k=1}^{n} (\ln k)^2 \leq \int_{1}^{n}(\ln x)^2 dx+ (\ln n)^2$$ and now, it only remains to compute (e.g., by integration by parts): $$\int_{1}^{n}(\ln x)^2 dx = \big[x(\ln^2 x - 2\ln x +2)\big]^n_1 = (1+o(1) n \ln^2 n$$ in order to conclude: $$\sum_{k=1}^{n} (\ln k)^2 \operatorname*{\sim}_{n\to\infty}n \ln^2 n$$ and, actually, $$\sum_{k=1}^{n} (\ln k)^2 = n \ln^2 n -2n \ln n + 2n +o(n)$$ since the difference between the upper and lower bounding integrals is $\ln^2 n = o(n)$.

To sum up: $$\sum_{k=1}^{n} (\log_2 k)^2 = n \log_2^2 n -({2}{\ln 2})n\log_2 n + {2}{(\ln 2)^2}n +o(n)$$

• +1! For fun, the next few terms are $$\sum_{k=1}^{n} (\ln k)^2 = n (\ln n)^2 -2n \ln n + 2n + \frac{1}{2}(\ln n)^2 + \zeta''(0) + \frac{\ln n}{6n} + o\!\left(\frac{\ln n}{n}\right),$$ where $$\zeta''(0) = \frac{\gamma_0}{2} + \gamma_1 - \frac{\pi^2}{24} - \frac{(\log 2\pi)^2}{2} \doteqdot -2.00635\ 64559\ 08584.$$ – Antonio Vargas Oct 19 '15 at 23:36
• @AntonioVargas Out of curiosity, did you use the same (but refined) method to get the remaining terms? – Clement C. Oct 20 '15 at 3:07
• Yes, it's essentially done by repeated integral comparisons. We start with the asymptotic obtained in your answer, $$u_n = n (\ln n)^2 -2n \ln n + 2n,$$ and calculate $$(\ln k)^2 - u_k + u_{k-1} \sim \frac{\ln k}{k}, \qquad k \to \infty.$$ Now taking $u_{0} = 0$ we have $$\sum_{k=1}^{n} (\ln k)^2 - u_n = \sum_{k=1}^{n} \left[(\ln k)^2 - u_k + u_{k-1}\right] \sim \sum_{k=1}^{n} \frac{\ln k}{k} \sim \int_1^n \frac{\ln x}{x}\,dx = \frac{1}{2}(\ln n)^2,$$ giving us the next term in the expansion...(cont.) – Antonio Vargas Oct 20 '15 at 4:02
• Then we can define $v_n = u_n + \frac{1}{2}(\ln n)^2$, calculate $$(\ln k)^2 - v_k + v_{k-1} \sim -\frac{\ln k}{6k^2},$$ and conclude that $$\sum_{k=1}^{n} (\ln k)^2 - v_n = \sum_{k=1}^{n} \left[(\ln k)^2 - v_k + v_{k-1}\right] = C + \epsilon_n,$$ where $$C = \sum_{k=1}^{\infty} \left[(\ln k)^2 - v_k + v_{k-1}\right]$$ and $$\epsilon_n = -\sum_{k=n+1}^{\infty} \left[(\ln k)^2 - v_k + v_{k-1}\right] \sim \frac{1}{6}\sum_{k=n+1}^{\infty} \frac{\ln k}{k^2} \sim \frac{1}{6} \int_{n+1}^{\infty} \frac{\ln x}{x^2}\,dx \sim \frac{\ln n}{6n}.$$ – Antonio Vargas Oct 20 '15 at 4:14
• Thus $$\sum_{k=1}^{n} (\ln k)^2 = v_n + C + \frac{\ln n}{6n} + o\!\left(\frac{\ln n}{n}\right).$$ Showing that $C = \zeta''(0)$ can be done using an analytic continuation argument which I give an example of in my answer here. – Antonio Vargas Oct 20 '15 at 4:15