<s>[INST] How to solve the recurrence $T(n) = T(n-1) +\sqrt{n}$? While solving the recurrence of the title I come to the series 
$$T(n) = \sqrt1 + \sqrt2 + \sqrt{3} + \cdots + \sqrt n.$$
Please somebody help me how to solve this.
 [/INST] We can use left-hand and right-hand approximations of integrals via Riemann sums to obtain tight bounds on our desired sum. Since $f(x) = \sqrt{x}$ is a strictly increasing function, observe that:
\begin{align*}
\int_0^n \sqrt{x} \, dx \leq \sum_{k=1}^n \sqrt{k} &\leq \int_1^{n+1} \sqrt{x} \, dx \\
\left[ \frac{x^{3/2}}{3/2} \right]_0^n \leq T(n) &\leq \left[ \frac{x^{3/2}}{3/2} \right]_1^{n+1}  \\
\frac{2}{3}n^{3/2} \leq T(n) &\leq \frac{2}{3}[(n+1)^{3/2} - 1]  \\
\end{align*}
Thus, we conclude that $T(n) = \Theta(n^{3/2})$.
</s>