2
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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) $$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ +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.$$ $\endgroup$ – Antonio Vargas Oct 19 '15 at 23:36
  • $\begingroup$ @AntonioVargas Out of curiosity, did you use the same (but refined) method to get the remaining terms? $\endgroup$ – Clement C. Oct 20 '15 at 3:07
  • 1
    $\begingroup$ 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.) $\endgroup$ – Antonio Vargas Oct 20 '15 at 4:02
  • 1
    $\begingroup$ 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}.$$ $\endgroup$ – Antonio Vargas Oct 20 '15 at 4:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Antonio Vargas Oct 20 '15 at 4:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.