# 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.

• There doesn't seem to be a nice closed form for $T(n)$, but for large $n$, $T(n) \sim \dfrac{2}{3}n\sqrt{n}$. – JimmyK4542 Jun 24 '14 at 6:47
• I would guess that $T(n) - \left( \dfrac{2}{3}n\sqrt{n} + \dfrac{1}{2}\sqrt{n} \right) \to -0.208$ to three significant figures might be closer, with the constant term estimated empirically so might be slightly wrong: I would not be surprised if $-0.207886$ was even closer – Henry Jun 24 '14 at 7:25

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})$.
• And $\frac{2}{3}[(n+\tfrac12)^{3/2} - \tfrac12]$ would give an even better approximation (the error seems to be between $0.1085$ and $0.1255$) – Henry Jun 24 '14 at 7:36
• @Rohit: $\displaystyle \int_{1/2}^{n+1/2} \sqrt{x} \, dx$ is between $\displaystyle \int_0^n \sqrt{x} \, dx$ and $\displaystyle \int_1^{n+1} \sqrt{x} \, dx$. The curve becomes close to linear for short parts with high $x$ so the midpoint is a good approximation – Henry Jun 26 '14 at 16:03
• Even better, $T(n) \sim \frac{2}{3} n^{3/2}$ – vonbrand Jun 29 '14 at 18:05
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$$