# Finding the asymptotics of a summation

Let $n\in\mathbb{Z}^+$ and $T_n = 1\sqrt{1} + 2\sqrt{2} +\cdots+ n\sqrt{n}$.

Finding $\mathcal{O}(T_n)$, $\mathcal{\Omega}(T_n)$ and $\mathcal{\Theta}(T_n)$

-
thanks to J.M for editting my tag :D – qwerty89 Nov 1 '11 at 7:59
Have you had calculus? If so, you might think about $\int_0^n x\sqrt{x} dx$ – Brian M. Scott Nov 1 '11 at 8:07
Well, there's $$\sum_{k=1}^n\,k^s=n^{s+1}\sum_{k=1}^\infty \frac{1}{n}(k/n)^s\sim n^{s+1}\int_0^1x^sdx=\frac{n^{s+1}}{s+1}.$$ You're question is pretty vague though, as there's always more than one type of $O,\Omega,\Theta$ applicable for a given function. – anon Nov 1 '11 at 8:08
thanks to anon. I have a solution same with yours. And $\Theta(T_n) = \sqrt{n^5}$ – qwerty89 Nov 1 '11 at 8:13
Please start accepting answers to your earlier questions. In Math.SE, this is considered important feedback for answerers. You can accept an answer by clicking the green tick/check mark under it. – Did Nov 13 '11 at 10:46

$$T_n = \Theta(n^{5/2})$$
$$T_n = 1 \sqrt{1} + 2 \sqrt{2} + \cdots + n \sqrt{n} < n \times n \sqrt{n} = n^{5/2}$$
Also $\forall k \in \{0,1,2,\ldots,n\}$, $$\frac{k \sqrt{k} + (n-k) \sqrt{n-k}}{2} > \frac{n}{2} \sqrt{\frac{n}{2}}$$
This gives that $$T_n = 1 \sqrt{1} + 2 \sqrt{2} + \cdots + n \sqrt{n} > n \times \frac{n}{2} \sqrt{\frac{n}{2}} = \frac{n^{5/2}}{2^{3/2}}$$
In general, as anon has in his comment, $$\displaystyle \sum_{k=1}^{n} k^s - \frac{n^{s+1}}{s+1} = \mathcal{\Theta}(n^{s})$$
This is my solution $$T_n = \sum_{i = 1}^{n} k^{3/2} \geq \sum_{i = n/2}^{n} \left(\frac{n}{2}\right)^{3/2} = \left(n - \lceil{\frac{n}{2}}\rceil + 1\right)\cdot\left(\frac{n}{2} \right)^{3/2} \geq \alpha\cdot\sqrt{n^5}$$ – qwerty89 Nov 1 '11 at 8:41