How to solve the recurrence $T(n) = T(n-1) +\sqrt{n}$?

Question

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.

Answer 1

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

Answer 2

It is not possible to find a closed-form expression for the exact value of $T(n)$. However, you can find an asymptotic approximation as $n$ becomes very large by approximating the sum as a Riemann sum, which can then be calculated via a definite integral.

$$T(n) \sim \int_0^n \sqrt x dx = \frac{2}{3}n\sqrt n$$