Using EM summation formula estimate $$ \sum_{k=1}^n \sqrt k $$

up to the term involving $\frac{1}{\sqrt n}$

My attempt is $$ \sum_{k=1}^n \sqrt k = \frac{2 \sqrt{n^3}}{3} -\frac{2}{3} + \frac 1 2 (\sqrt n -1)+ \frac{1}{24} (\frac{1}{\sqrt n} -1) + \int_1^n P_{2k+1}(x)f^{(2k+1)}(x)dx $$ I am not sure what can be said about the integral. Please tell me if I have made a mistake and how I can solve the integral? Have I stopped the summation at the right point?

  • $\begingroup$ This was also discussed at this MSE link, which you may find enlightening. $\endgroup$ Jun 16 '15 at 19:35

Using the Euler-Maclaurin Sum Formula, we get $$ \sum_{k=1}^n\sqrt{k}=\tfrac23n^{3/2}+\tfrac12n^{1/2}+\zeta(-\tfrac12)+\tfrac1{24}n^{-1/2}-\tfrac1{1920}n^{-5/2}+\tfrac1{9216}n^{-9/2}+O(n^{-13/2}) $$ where the constant $\zeta(-\frac12)=-0.20788622497735456602$ is explained below.

By the Euler-Maclaurin Sum Formula, we have for $\mathrm{Re}(s)\gt-1$ $$ \sum_{k=1}^nk^{-s}=\frac1{1-s}n^{1-s}+\frac12n^{-s}+\zeta_\ast(s)+O(n^{-s-1})\tag{1} $$ Define the sequence of functions $$ \zeta_n(s)=\sum_{k=1}^nk^{-s}-\frac1{1-s}n^{1-s}-\frac12n^{-s}\tag{2} $$ For all $n\ge1$, $\zeta_n(s)$ is analytic. For $\mathrm{Re}(s)\gt1$, $\lim\limits_{n\to\infty}\zeta_n(s)=\zeta(s)$. Estimate $(1)$ says that on compact subsets of $\{s\in\mathbb{C}\setminus\{1\}:\mathrm{Re(s)\gt-1}\}$, $\zeta_n(s)$ converges uniformly. Thus, for $s\in\mathbb{C}\setminus\{1\}$ and $\mathrm{Re}(s)\gt-1$, $\lim\limits_{n\to\infty}\zeta_n(s)$ is analytic, so by analytic continuation, for $\mathrm{Re}(s)\gt-1$, $$ \zeta_\ast(s)=\lim\limits_{n\to\infty}\zeta_n(s)=\zeta(s)\tag{3} $$

  • $\begingroup$ @Robjon There were typos in the first non-enumerated equation ($x$ instead of $n$). I took the liberty of editing. I hope that you don't mind. I also edited my answer and would like to hear your thoughts on this expansion to $x^{-3/2}$. $\endgroup$
    – Mark Viola
    Jun 17 '15 at 5:56
  • $\begingroup$ Hi Rob. I hope that all is well. Just to clarify … Are you applying the AC to the punctured plane since $\zeta(s)$ is meromorphic with a single simple pole at $s=1$? $\endgroup$
    – Mark Viola
    Nov 12 '18 at 18:34
  • $\begingroup$ @MarkViola: yes. I guess I should have said "compact subsets of $\{s\in\mathbb{C}\setminus\{0\}:\mathrm{Re(s)\gt-1}\}$". I have updated the post. I missed that point because I was mainly interested in the leftward extension made possible by the Euler-Maclaurin Sum Formula. $\endgroup$
    – robjohn
    Nov 12 '18 at 21:52
  • $\begingroup$ You mean $\mathbb{C}\setminus \{1\}$, I believe. $\endgroup$
    – Mark Viola
    Nov 12 '18 at 22:20
  • $\begingroup$ (+1) for the very well-written solution! $\endgroup$
    – Mark Viola
    Nov 13 '18 at 17:14

The correct expansion is given by

$$\begin{align} \sum_{i=1}^n f(i) &= \int_1^n f(x)dx + B_1 [f(n)+f(1)]\\\\ & + \sum_{k=1}^m \frac{B_{2k}}{(2k)!} \left(f^{(2k-1)}(n)-f^{(2k-1)}(1)\right)\\\\ & +\frac{1}{(2m+1)!}\int_1^n P_{2m+1}(x)f^{(2m+1)}(x) \end{align}$$

For $f(x)=x^{1/2}$ and $m=1$, we have

$$\begin{align} \sum_{i=1}^n\sqrt{i}&=\frac23 (n^{3/2}-1)+\frac12 (n^{1/2}+1)+\frac{1}{24}(n^{-1/2}-1)+\frac{1}{3!}\int_1^n P_3(x)f^{(3)}(x)dx\\\\ &=\frac23x^{3/2}+\frac12n^{1/2}+\left(-\frac23+\frac12-\frac{1}{24}\right)+\frac{1}{24}n^{-1/2}+\frac{1}{3!}\int_1^n P_3(x)f^{(3)}(x)dx \end{align}$$

The next task is to determine an estimate for the remainder $R$ where $R$ is the integral

$$R\equiv \frac{1}{3!}\int_1^n P_3(x)f^{(3)}(x)dx$$

We can find an estimate for the integral term

$$\int_1^n P_{3}(x)f^{(3)}(x)dx \tag1$$

using the well-known expression for the Bernoulli Polynomial

$$B_3(x)=x^3-\frac32 x^2+\frac12 x$$

We can easily verify that


for $x\in [0,1]$. Since $P_{2k+1}(x)=B_{2k+1}(x-\lfloor x\rfloor)$ then we see immediately that for $1<x<n$

$$-\frac{1}{12\sqrt{3}}< P_{3}(x) < \frac{1}{12\sqrt{3}}\tag 2$$

Now, we note that for $f(x)=x^{1/2}$, $f^{3}(x)=\frac38 x^{-5/2}>0$ for $x\in [1,n]$. Now, we use $(2)$ in the estimate of $(1)$ to reveal

$$\begin{align} -\frac{1}{48\sqrt{3}}\left(1-n^{-3/2}\right)<\int_1^n P_{3}(x)f^{(3)}(x)dx \le \frac{1}{48\sqrt{3}}\left(1-n^{-3/2}\right) \end{align}$$

Finally, we have the upper and lower bounds

$$\bbox[5px,border:2px solid #C0A000]{\sum_{k=1}^n\sqrt{k}\le \frac23n^{3/2}+\frac12n^{1/2}+\left(-\frac{5}{24}+\frac{1}{288\sqrt{3}}\right)+\frac{1}{24}n^{-1/2}-\frac{1}{288\sqrt{3}}n^{-3/2}}$$

$$\bbox[5px,border:2px solid #C0A000]{\sum_{k=1}^n\sqrt{k}\ge \frac23n^{3/2}+\frac12n^{1/2}+\left(-\frac{5}{24}-\frac{1}{288\sqrt{3}}\right)+\frac{1}{24}n^{-1/2}+\frac{1}{288\sqrt{3}}n^{-3/2}}$$

  • $\begingroup$ The difference of the upper and lower bounds is $\frac1{144\sqrt3}$ which is bigger than $\frac1{24}n^{-1/2}$ for $n\gt108$. However, computing the actual values, both formulas on the right are over-estimates for the sum. $\endgroup$
    – robjohn
    Jun 17 '15 at 11:27
  • $\begingroup$ @robjohn Well, I found the error. I added $-2/3 +1/2-1/24$ and incorrectly got $-1/8$ (this is the reason to forgo doing arithmetic in my head late at night) edited version. The sum is actually $-5/24\approx. 0.20833$. The bounds are now correct. I do really want to thank you for all of the comments! $\endgroup$
    – Mark Viola
    Jun 17 '15 at 16:35
  • $\begingroup$ Now the bounds do bracket the sum. (+1) However for $n\gt108$, the difference in the bounds makes the last two terms insignificant. One point of the Euler-Maclaurin Sum Formula is that there is a constant that can replace $\left(-\frac5{24}+\frac1{288\sqrt3}\right)$ and $\left(-\frac5{24}-\frac1{288\sqrt3}\right)$. Even if it can't be determined symbolically, it can be evaluated numerically. Using the terms in my answer, and $n=1000$, we can compute $23$ places of the constant, since the next term is $-\frac{11}{163840}n^{-13/2}$. $\endgroup$
    – robjohn
    Jun 17 '15 at 18:03
  • $\begingroup$ @robjohn Yes, I understand that your approach is the better way. It is really pretty cool! But, rather than duplicate, I wanted to provide the OP with a more "brute force" way forward. $\endgroup$
    – Mark Viola
    Jun 17 '15 at 18:09
  • $\begingroup$ Yes, you are doing things using the integration by parts development. There is nothing wrong with that and it does give concrete bounds. Although I was concentrating on its numerical limitations, I didn't mean to deprecate your work (I did upvote :-). I simply wanted to point out that, in most cases, it is possible to compute the constant fairly accurately. $\endgroup$
    – robjohn
    Jun 17 '15 at 18:34

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.