Big Omega of a Summation: $\sum_{k=1}^n\sqrt{k\log k}=\Omega\left(\sqrt{n^3\log n}\right)$

Question

I can solve the upper bound of the following series but stuck in prove this: $$\sum_{k=1}^n\sqrt{k\log k}=\Omega\left(\sqrt{n^3\log n}\right)$$

Update: Thanks all, I was looking for a simple discrete proof like this: $$ \exists c>0,n_0>0,\;\forall n\geq n_0:\;cn\sqrt{n\log n}\leq\sum_{k=1}^n\sqrt{k\log k}\\\sum_{k=\left\lfloor\frac n2\right\rfloor+1}^n\sqrt{k\log k}\geq\frac n2\sqrt{\frac n2\log\left(\frac n2\right)}=\frac n2\sqrt{\frac n2\left(\log\left(n\right)-1\right)}\geq\underbrace{\frac n2\sqrt{\frac n4\log n}}_{{\textstyle\frac14}n\sqrt{n\log n}} $$ for $c=\frac14,n_0=4$.

Answer 1

Let's aspire to do better than an $\Omega$-estimate by getting an asymptotic estimate.

Here is a very useful fact for estimating partial sums of sequences: if $\{a_n\}$ and $\{b_n\}$ are sequences of positive numbers with $a_n \sim b_n$ and either sequence of partial sums $\sum_{k \leq n} a_k$ or $\sum_{k \leq n} b_k$ tends to $\infty$, then they both tend to $\infty$ and are asymptotic: $\sum_{k \leq n} a_n \sim \sum_{k \leq n} b_k$ as $n \to \infty$. Prove that.

Next, check that $\int_n^{n+1} \sqrt{x\log x}\,dx \sim \sqrt{n\log n}$ as $n \to \infty$, so we can apply the above result with $a_n = \sqrt{n\log n}$ and $b_n = \int_n^{n+1}\sqrt{x\log x}\,dx$ to get $$ \sum_{k=1}^n \sqrt{k\log k} \sim \sum_{k=1}^n \int_k^{k+1} \sqrt{x\log x}\,dx = \int_1^{n+1}\sqrt{x\log x}\,dx. $$

Since $\log x$ grows very slowly, we expect heuristically that we can treat $\log x$ on a large interval $[1,y]$ as the right endpoint value $\log y$ for the purpose of making asymptotic estimates, which suggests that $$ \int_1^y \sqrt{x\log x}\,dx \stackrel{?}{\sim} \sqrt{\log y}\int_1^y\sqrt{x}\,dx = \frac{2}{3}y^{3/2}\sqrt{\log y}. $$ Having guessed an asymptotic estimate for $\int_1^y \sqrt{x\log x}\,dx$, meaning we guess $$ \lim_{y \to \infty} \frac{\int_1^y \sqrt{x\log x}\,dx}{(2/3)y^{3/2}\sqrt{\log y}} \stackrel{?}{=} 1, $$ you can prove it is correct by using L'Hospital's rule. Do that.

Returning to the sum, where $n$ runs over positive integers, we obtain $$ \sum_{k=1}^n \sqrt{k\log k} \sim \int_1^{n+1}\sqrt{x\log x}\,dx \sim \frac{2}{3}(n+1)^{3/2}\sqrt{\log (n+1)} \sim \frac{2}{3}n^{3/2}\sqrt{\log n}. $$

Example. The ratio of $\sum_{k=1}^n \sqrt{k\log k}$ to $(2/3)n^{3/2}\sqrt{\log n}$ at $n = 10^4$, $10^5$, $10^6$, $10^7$, and $10^8$ is $.962$, $.970$, $.975$, $.978$, and $.981$. So the convergence is slow, but steady.

For sums of the kind you asked about, it is easy in practice to get asymptotic estimates by the method outlined above, so you should never be satisfied with $\Omega$-estimates in those kinds of problems.

Remark. It is not always that case that treating $\log x$ on a large interval $[1,y]$ as the "constant" $\log y$ will lead to the right asymptotic estimate on an integral. For example, consider $$ \int_2^y \frac{dx}{x\sqrt{\log x}}. $$ Heuristically we expect this grows like $$ \frac{1}{\sqrt{\log y}}\int_2^y \frac{dx}{x} = \frac{1}{\sqrt{\log y}}(\log y - \log 2) \sim \sqrt{\log y}, $$ but the integrand $1/(x\sqrt{\log x})$ has antiderivative $2\sqrt{\log x}$, so $$ \int_2^y \frac{dx}{x\sqrt{\log x}} = 2\sqrt{\log y} - 2\sqrt{\log 2} \sim 2\sqrt{\log y} $$ and the heuristic guess was off by a factor of 2. But at least we got the right order of magnitude $\sqrt{\log y}$, and you can pin down the correct constant factor in the estimate (without knowing the exact antiderivative of the integrand) by computing $$ \lim_{y \to \infty} \frac{\int_2^y dx/(x\sqrt{\log x})}{\sqrt{\log y}} = 2 $$ using L'Hospital's rule.

Answer 2

A complete asymptotic expansion may be obtained as follows. First $$ \sum\limits_{k = 1}^n {\sqrt {k\log k} } \le \sqrt {n\log n} + \sum\limits_{k = 1}^{n - 1} {\int_k^{k + 1} {\sqrt {t\log t} \,{\rm d}t} } = \sqrt {n\log n} + \int_1^n {\sqrt {t\log t} \,{\rm d}t} $$ and $$ \sum\limits_{k = 1}^n {\sqrt {k\log k} } = \sum\limits_{k = 2}^n {\sqrt {k\log k} } \ge \sum\limits_{k = 2}^n {\int_{k - 1}^k {\sqrt {t\log t} \,{\rm d}t} } = \int_1^n {\sqrt {t\log t} \,{\rm d}t} $$ Therefore, $$\tag{$\star$} \sum\limits_{k = 1}^n {\sqrt {k\log k} } = \int_1^n {\sqrt {t\log t}\, {\rm d}t} + \mathcal{O}(\sqrt {n\log n} ) $$ as $n\to +\infty$. With the substitution $t = {\rm e}^{2x/3}$, $$ \int_1^n {\sqrt {t\log t}\, {\rm d}t} = \left( {\frac{2}{3}} \right)^{3/2} \int_0^{(3\log n)/2} {{\rm e}^x x^{1/2} {\rm d}x} $$ for any $n\geq 1$. Taking $x = (1 - s)z$ and using Watson's lemma yields $$ \int_0^z {{\rm e}^x x^{1/2} \,{\rm d}x} = - z^{3/2} {\rm e}^z \int_0^1 {{\rm e}^{ - zs} \sqrt {1 - s} \,{\rm d}s} \sim \sqrt z {\rm e}^z \sum\limits_{m = 0}^\infty {\frac{{(2m)!}}{{4^m (1 - 2m)m!}}\frac{1}{{z^m }}} $$ as $z\to +\infty$. Accordingly, $$ \int_1^n {\sqrt {t\log t} \,{\rm d}t} \sim \frac{2}{3}n^{3/2} \sqrt {\log n} \sum\limits_{m = 0}^\infty {\frac{{(2m)!}}{{6^m (1 - 2m)m!}}\frac{1}{{\log ^m\! n}}} $$ as $n\to +\infty$. In view of $(\star)$, we finally have $$ \sum\limits_{k = 1}^n {\sqrt {k\log k} } \sim \frac{2}{3}n^{3/2} \sqrt {\log n} \sum\limits_{m = 0}^\infty {\frac{{(2m)!}}{{6^m (1 - 2m)m!}}\frac{1}{{\log ^m\! n}}} $$ as $n\to +\infty$.

Addendum. With the aid of exponential asymptotics, one can show that $$ \sum\limits_{k = 1}^n {\sqrt {k\log k} } = \frac{2}{3}n^{3/2} \sqrt {\log n} \left( {\frac{3}{{4n}} + \sum\limits_{m = 0}^{\left\lfloor {\log (n^{3/2} )} \right\rfloor } {\frac{{(2m)!}}{{6^m (1 - 2m)m!}}\frac{1}{{\log ^m\! n}}} } \right) + \mathcal{O}(1). $$ Note that the number of terms on the right-hand side is exponentially small compared with that on the left-hand side. I omit the proof.