2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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}$. $\endgroup$ – JimmyK4542 Jun 24 '14 at 6:47
  • 1
    $\begingroup$ 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 $\endgroup$ – Henry Jun 24 '14 at 7:25
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ 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$) $\endgroup$ – Henry Jun 24 '14 at 7:36
  • $\begingroup$ @Henry : Could you please elaborate how you reached at this expression. It would really help me. $\endgroup$ – Rohit Rohela Jun 26 '14 at 10:03
  • 1
    $\begingroup$ @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 $\endgroup$ – Henry Jun 26 '14 at 16:03
  • $\begingroup$ Even better, $T(n) \sim \frac{2}{3} n^{3/2}$ $\endgroup$ – vonbrand Jun 29 '14 at 18:05
1
$\begingroup$

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$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.