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